Hallo,
Ich zerbrech mir jetzt schon seit einer Stunde den Kopf über ein (denke
ich) simples Problem:
Ich möchte aus dem Wertebereich 0x0 - 0xFF einen Wert suchen, aber die
Funktion die ich zum Vergleichen benutze liefert mir nur True bei
kleiner gleich und False bei größer.
Nun möchte ich natürlich mit möglichst wenig vergleichen zum Ziel kommen
da die Vergleiche auf einem Embedded System (langsam) ablaufen.
Ich wollte die Binäre Suche Einsetzen, aber komm ums verrecken nicht auf
eine Abbruchbedingung ohne einen Vergleich auf Gleichheit :(
Währe nett wenn mir da schnell jemand unter die Arme greifen könnte :)
Danke schon mal für die Antworten! :)
Aber ich habe gerade einen Fehler in meiner Beschreibung entdeckt.
Ich kann nur folgenden Vergleich durchführen versuchter Wert < gesuchter
Wert
Das heißt ich kann nur folgendes feststellen:
versuchter Wert < gesuchter Wert und versuchter Wert >= gesuchter Wert
Damit scheiden leider die obigen Vorschläge aus :(
Tja eigentlich schon aber in diesem Fall macht den Vergleich ein
externes Gerät auf das ich keinen Zugriff habe :(
Ich möchte Daten auslesen, weiß aber nicht wie lang sie sind. Der
Auslesevorgang kann beliebig wiederholt werden. Ich kann mit einem
Kommando n bytes auslesen, aber wenn ich zu mehr auslesen will als
vorhanden ist kommt ein Fehler. Jetzt möchte ich auf dem schnellsten Weg
wissen wieviele Datenbytes vorhanden sind :)
Ich denke nicht das es da viele Möglichkeiten gibt.
einfach mit Maximum anfangen und denn weils entscheiden ob jeweil ok
oder nicht. Dann wieder halbieren usw.
Aber der Ansatz oben war doch gut.
Nur das er eben nicht mit <= sondern mit < ausgeführt werden muss
(a==b) : !((b<a) || (a<b))
wobei ! die Negation sein soll.
Das ist wie in der boolschen Logik. Mit einer Verknüpfung und der
Negation kannst Du alle anderen zusammensetzen.
Man könnte einen vergleich auch so machen:
if(!(a-b))
{
}
Wenn a == b ist das Ergebnis der Subraktion null, null negiert ist Wahr,
sind sie ungleich ist das ergebnis ungleich null, und das negiert ist
falsch.
@Logiker und M.H.
Das Problem bei diesen Ansätzen ist das ich die Werte für a und b nicht
kenne. Mein Problem ist eher so: Ich stell mir eine Zahl vor zwischen 0
und 255, du musst sie erraten, ich sag dir aber nur ob deine Zahl größer
ist als die die ich mir denke.
Hab den Code noch ändern müssen, er hat unter bestimmten Umständen
Endlosschleifen produziert.
Es liegt nun mal in der Natur von Vergleichen, dass es drei
Möglichkeiten ("<", "=" oder ">")gibt.
Willst Du also alle erfassen, so brauchst Du zwei Vergleiche.
Kannst Du zwei Möglichkeiten zusammenfassen ("<=" oder ">=") so reicht
natürlich ein Vergleich.
verzweifler schrieb:> Hab den Code noch ändern müssen, er hat unter bestimmten Umständen> Endlosschleifen produziert.
Du musst aber right mit 0x100 statt mit 0xFF initialisieren, sonst
funktioniert dein Code nicht für x=255.
Folgendes ginge ebenfalls, ist kürzer aber nicht ganz so flexibel wie
dein Code, da die mittlere Anzahl der benötigten Versuche nur dann
minimal ist, wenn die Größe des Suchraums eine Zweierpotenz ist:
verzweifler schrieb:> @Logiker und M.H.> Das Problem bei diesen Ansätzen ist ...
Oh. Das habe ich überlesen,
Nun, Du scheinst ja eine Lösung zu haben. Aber etwas würde mich doch
neugierhalber interessieren.
1. Wenn Du einen Wert unterhalb der gesuchten Länge versuchst, liefert
die Gegenstelle einfach die Daten oder ist das ein gesonderter Befehl.
(Deine Beschreibung hört sich nach ersterem an).
2. Sammeln sich in der Gegenstelle zu irgendwelchen Zeitpunkten immer
mehr Daten an, oder löst Du das über einen dritten Befehl irgendwie aus?
3. Gibt es irgendwelche statistischen Auswertungen wieviele Daten über
einen gewissen Zeitraum zur Verfügung stehen?
Ich meine es gäbe vielleicht effektivere Strategien. Aber wiegesagt,
hauptsächlich bin ich neugierig.
Reinhard Kern schrieb:> Hallo,>> wenn v < g und v+1 >= g dann v == g>> Gruss Reinhard
WHAT? v < g ergibt nach diversem Zauber (v+1 >= g) plötzlich g? Also
irgendwas stimmt da nicht ;-).
Entweder so, wie Reinhard das geschrieben hat, oder
1
wenn nicht( ( v < g ) oder ( g < v ) )
2
dann sind sie gleich
(in anderen Worten: wenn keiner kleiner als der andere ist, dann müssen
sie gleich sein)
oder
1
wenn (( v >= g ) und ( g >= v ) )
2
dann sind sie gleich
(in anderen Worten: wenn sowohl v größer/gleich g ist, als auch g
größer/gleich v, dann ist keiner tatsächlich größer, sondern beide sind
gleich).
Mit den genannten Vergleichen gibt es immer eine Möglichkeit, wie man
'sind gleich' ausdrücken kann. Gegebenenfalls muss man eben 2 Vergleiche
machen und die beiden kombinieren, um daraus seine Schüsse zu ziehen.
Karl Heinz schrieb:> wenn nicht( ( v < g ) oder ( g < v ) )> dann sind sie gleich> ...> oder wenn (( v >= g ) und ( g >= v ) )> dann sind sie gleich
Das Problem ist, dass man weder v<g noch v>=g hat. Im vorliegenden Fall
gibt es nur v<=g und die Negation davon, nämlich v>g (g ist dabei die
gesuchte Variable, auf die nicht direkt zugegriffen werden kann, und v
ist ein beliebiger Ausdruck). Siehe hier:
verzweifler schrieb:> Ich möchte Daten auslesen, weiß aber nicht wie lang sie sind. Der> Auslesevorgang kann beliebig wiederholt werden. Ich kann mit einem> Kommando n bytes auslesen, aber wenn ich zu mehr auslesen will als> vorhanden ist kommt ein Fehler.
Nach dem Muster von Reinhard kann man also die Gleichheit von v und g
mit v<=g && v+1>g feststellen, eine andere Möglichkeit gibt es nicht.
Dies wird in der vom verzweifler gefundenen Lösung implizit auch so
gemacht.
Wäre g übrigens keine ganze, sondern eine gebrochene Zahl mit unendlich
feiner oder unbekannter Auflösung, könnte man den nächstgrößeren
Nachfolger von v nicht bestimmen, so dass auch Reinhards Methode
versagt. Damit könnte in diesem Fall die Gleichheit mit den gegebenen
Operationen überhaupt nicht entschieden werden.
Ich habe dein Problem nicht genau verstanden aber vllt. könnte eine
Lösung sein den Algorithnus des successive approximation ADCs in dein
Programm einzubauen.
Stefan schrieb:> aber vllt. könnte eine Lösung sein den Algorithnus des successive> approximation ADCs in dein Programm einzubauen.
Das ist im Prinzip genau das, was der verzweifler hier gemacht hat:
Beitrag "Re: Binäre Suche ohne ohne Istgleich"
Etwas deutlicher wird die Analogie vielleicht, wenn man in diesem Code
Beitrag "Re: Binäre Suche ohne ohne Istgleich"
die arithmetischen Operationen durch entsprechende Bit-Operationen
ersetzt und die Namen entsprechend der Anwendung im ADC ändert:
1
intadcErgebnis=0,bit,dacWert;
2
3
for(bit=0x80;bit;bit>>=1){// alle 8 Bits nacheinander durchgehen
4
dacWert=adcErgebnis|bit;// Bit versuchsweise setzen
5
if(messwertIstGroesserOderGleich(dacWert))// Mess- mit DAC-Spannung vergleichen
6
adcErgebnis=dacWert;// ggf. Bit ins Ergebnis übernehmen
7
}
8
returnadcErgebnis;
Genau so wird der ADC auch in Hardware realisiert. Im DAC-Register
(dacWert) werden – getrieben durch das Taktsignal und beginnend mit dem
höchstwertigen Bit – nacheinander alle Bits versuchsweise gesetzt und
die zu messende Spannung durch einen Analogkomparator mit der
Ausgangsspannung des DAC verglichen (messwertIstGroesserOderGleich). Je
nach Ergebnis des Vergleichs wird der Wert mit gesetztem Bit übernommen
(adcErgebnis = dacWert) oder der alte Wert mit nicht gesetztem Bit
stehen gelassen.
Yalu X. schrieb:> Du musst aber right mit 0x100 statt mit 0xFF initialisieren, sonst> funktioniert dein Code nicht für x=255.
Danke, ist in der Tat bei mir falsch
