Einzelnen Beitrag anzeigen

TiGü

Registriert seit: 6. Apr 2011
Ort: Berlin
2.835 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#8

AW: Schneller Algorithmus für eine Zahl in mehren Bereichen?

  Alt 4. Aug 2021, 10:01
Ich habe das jetzt ganz simpel mit einem TDictionary umgesetzt, so das suchen einer Zahl ein Array mit den Bereichen zurückgibt mit O(1).
Verwende hier die Array-Verknüpfungssyntax ab XE7, müsste man für Delphi 2010 noch zurück stricken mit SetLength-Rumgehampel.

Deine Beispielzahlen passen übrigens nicht.

Delphi-Quellcode:
900 NIL
1000 A
1030 A, B
1055 A, B, C
1100 A, C // < --- passt auch in B mit 1020-1160
1155 NIL // < --- passt auch in A (1000-1200) und B (1020-1160) mit
1500 NIL
1525 D

Delphi-Quellcode:
program Project6;

{$APPTYPE CONSOLE}
{$R *.res}

uses
    System.SysUtils,
    System.Math,
    System.Generics.Collections;

type
    TRange = record
        StartValue: Integer;
        EndValue: Integer;
        RangeName: string;
    end;

    TRanges = TArray<TRange>;

const
    RangeA: TRange = (StartValue: 1000; EndValue: 1200; RangeName: 'A');
    RangeB: TRange = (StartValue: 1020; EndValue: 1160; RangeName: 'B');
    RangeC: TRange = (StartValue: 1050; EndValue: 1150; RangeName: 'C');
    RangeD: TRange = (StartValue: 1510; EndValue: 1550; RangeName: 'D');

    FirstNumber = 0;
    LastNumber = 2000;

    TestNumbers: array[0..7] of Integer = (900, 1000, 1030, 1055, 1100, 1155, 1500, 1525);

procedure Main;
var
    NumberToRangeMap: TDictionary<Integer, TRanges>;
    CurrentRange: TRange;
    CurrentRanges: TRanges;
    I: Integer;
    AllRanges: TRanges;
    JustAText: string;
    LastChar: Integer;
begin
    // Initialisieren, macht man eimal
    AllRanges := [RangeA, RangeB, RangeC, RangeD];
    NumberToRangeMap := TDictionary<Integer, TRanges>.Create;
    try
        for I := FirstNumber to LastNumber do
        begin
            for CurrentRange in AllRanges do
            begin
                if InRange(I, CurrentRange.StartValue, CurrentRange.EndValue) then
                begin
                    NumberToRangeMap.TryGetValue(I, CurrentRanges);
                    CurrentRanges := CurrentRanges + [CurrentRange];
                    NumberToRangeMap.AddOrSetValue(I, CurrentRanges);
                end;
            end;
        end;

        // Nummern Testen mit O(1)
        for I in TestNumbers do
        begin
            if NumberToRangeMap.TryGetValue(I, CurrentRanges) then
            begin
                JustAText := '';
                for CurrentRange in CurrentRanges do
                begin
                    JustAText := JustAText + CurrentRange.RangeName + ', ';
                end;

                LastChar := Length(JustAText) - 1;
                if JustAText[LastChar] = ',then
                    JustAText[LastChar] := ' ';

                Writeln(I, ' ', JustAText);
            end else
            begin
                Writeln(I, ' NIL');
            end;
        end;
    finally
        NumberToRangeMap.Free;
    end;
end;

begin
    try
        Main;
    except
        on E: Exception do
            Writeln(E.ClassName, ': ', E.Message);
    end;
    Readln;
end.

Geändert von TiGü ( 4. Aug 2021 um 10:05 Uhr)
  Mit Zitat antworten Zitat