Überprüfen, ob Zahl in unregelmäßigen Bereichen

[bigg]

huch, :shock:

ich glaube ich habe dein Problem nun verstanden. Wobei sich dann eine Liste mit Zeigern verknüpft mit einer Liste mit Integern besser machen würde, imho. Die Liste wird anschließend sortiert und auf Konsistenz geprüft.

[xZise]

Zitat:

Zitat von bigg

Wobei sich dann eine Liste mit Zeigern verknüpft mit einer Liste mit Integern besser machen würde, imho. Die Liste wird anschließend sortiert und auf Konsistenz geprüft.

:D Ähn ja... Ich versteh fast nix :D

[negaH]

Ist auch nicht so wichtig da es besseres gibt.

1. Frage: welche Zahlen kommen vor und wie viele Bereiche gibt es ? Ich frage weil wenn das Set der Zahlen klein ist, zb. eben 1 bis 9 dann ist mein Vorschlag der effizienteste. Es ist eine einfach und direkte Lookup Tabelle und hat Komplexität O(1) !!

2. falls der Zahlenbereich zu groß ist so wird auch die Lockup Tabelle enorm groß und unpraktikabel. In diesem Moment benutzt du einen sortierten binären Baum deiner Bereiche. Bei der Suche in welchem Bereich deine Zahl nun liegt gehst du defakto per binärer Suche vor. Alle bisherigen Vorschläge gehen iterativ und sequientiell durch deine Bereichsliste durch. Dies ist bei vielen Bereichen wesentlich ineffizienter als eine binäre Suche, sei es als Binärer Baum (Trie) oder eine sortierte Liste die per binärer Suche durchsucht wird.

Gruß Hagen

[xZise]

Also die Zahl kann so groß wie ein Int sein und die Berieche zwischen 1 und 10.

[negaH]

bei max. 10 Bereichen lohnt keine aufwendige binäre Suche/Baum.

Delphi-Quellcode:

var
  Bereich: array[0..10] of Integer = (10,100,1000,234567,87654321, MaxInt, 0, 0, 0); // MaxInt als End-Marker
begin
  BereichIndex := Low(Bereich);
  while Zahl > Bereich[BereichIndex] do
    Inc(BereichIndex);
end;

Gruß Hagen