Hilfe bei Algorithmus
Verfasst: 15.08.2013, 17:50
Hallo Leute,
hier tummeln sich einige helle Köpfe. Ich brauche einen gewissen Lösungsalgorithmus für ein spezielles Problem und komm gerade einfach nicht drauf. Vielleicht kann mir da ja jemand weiter helfen.
Grundlage:
Es existieren 4 Variablen. Nennen wir sie mal a, b, c und d, die einen bestimmten Wertebereich haben und somit durch eine bestimmte Anzahl von Bits dargestellt werden. Der Wertebereich und die Bitlänge sind für a und c fest, bei b hängt beides vom Wert in a ab und bei d hängt beides vom Wert in c ab, allerdings nicht in dem Sinne, dass der Wert direkt den Wertebereich oder direkt die Bitlänge angibt, sondern wie folgt:
Die Variable a wird immer mit 2 Bits ausgedrückt. Der Wertebereich geht von 3 bis 6. Diese Zahl entspricht der Bitanzahl von b.
Die Variable c wird immer mit 3 Bits ausgedrückt. Der Wertebereich geht von 3 bis 10. Diese Zahl entspricht der Bitanzahl von d.
Die Wertebereiche von b sind:
- bei 3 Bits: 3 ~ 10
- bei 4 Bits: 11 ~ 26
- bei 5 Bits: 27 ~ 58
- bei 6 Bits: 59 ~ 122
Die Wertebereiche von d sind:
- bei 3 Bits: 0 ~ 7
- bei 4 Bits: 8 ~ 23
- bei 5 Bits: 24 ~ 55
- bei 6 Bits: 56 ~ 119
- bei 7 Bits: 120 ~ 247
- bei 8 Bits: 248 ~ 503
- bei 9 Bits: 504 ~ 1015
- bei 10 Bits: 1016 ~ 2039
Weiterhin gibt es 2 Input-Werte (vorzeichenlos und ganzzahlig), x und y. Dabei gilt immer y > x oder hier explizit y >= (x + 1).
x liegt innerhalb des maximalen Gesamt-Wertebereichs von b, sprich innerhalb von 3 bis 112. Je nach Wert von x wird für b der passende Wertebereich rausgesucht und davon abhängig die Bitanzahl für b und somit auch der Wert von a bestimmt.
Bei y ist dies ähnlich. Da y aber immer größer als x sein muss, wird zunächst (x + 1) von y abgezogen. Das Ergebnis nennen wir mal yy.
yy liegt nun innerhalb des maximalen Gesamt-Wertebereichs von d, sprich innerhalb von 0 bis 2029. Je nach Wert von yy wird für d der passende Wertebereich rausgesucht und davon abhängig die Bitanzahl für d und somit auch der Wert von c bestimmt.
Daraus ergibt sich eine Gesamtbitanzahl.
Ziel:
Das Ziel des Algorithmus, der nur x als Eingabe erhält und die Grundlagen kennt (ok, nur ich kenne sie :) ), ist es nun abhängig von x ein maximales y zu bestimmen, sodass gilt:
NötigeGesamtbitanzahl <= x * 4
Ich steh grad echt auf dem Schlauch. Schon allein die nötige Bitanzahl für b, abhängig von x zu berechnen, will mir nicht glücken. Habt ihr da Ideen?
hier tummeln sich einige helle Köpfe. Ich brauche einen gewissen Lösungsalgorithmus für ein spezielles Problem und komm gerade einfach nicht drauf. Vielleicht kann mir da ja jemand weiter helfen.
Grundlage:
Es existieren 4 Variablen. Nennen wir sie mal a, b, c und d, die einen bestimmten Wertebereich haben und somit durch eine bestimmte Anzahl von Bits dargestellt werden. Der Wertebereich und die Bitlänge sind für a und c fest, bei b hängt beides vom Wert in a ab und bei d hängt beides vom Wert in c ab, allerdings nicht in dem Sinne, dass der Wert direkt den Wertebereich oder direkt die Bitlänge angibt, sondern wie folgt:
Die Variable a wird immer mit 2 Bits ausgedrückt. Der Wertebereich geht von 3 bis 6. Diese Zahl entspricht der Bitanzahl von b.
Die Variable c wird immer mit 3 Bits ausgedrückt. Der Wertebereich geht von 3 bis 10. Diese Zahl entspricht der Bitanzahl von d.
Die Wertebereiche von b sind:
- bei 3 Bits: 3 ~ 10
- bei 4 Bits: 11 ~ 26
- bei 5 Bits: 27 ~ 58
- bei 6 Bits: 59 ~ 122
Die Wertebereiche von d sind:
- bei 3 Bits: 0 ~ 7
- bei 4 Bits: 8 ~ 23
- bei 5 Bits: 24 ~ 55
- bei 6 Bits: 56 ~ 119
- bei 7 Bits: 120 ~ 247
- bei 8 Bits: 248 ~ 503
- bei 9 Bits: 504 ~ 1015
- bei 10 Bits: 1016 ~ 2039
Weiterhin gibt es 2 Input-Werte (vorzeichenlos und ganzzahlig), x und y. Dabei gilt immer y > x oder hier explizit y >= (x + 1).
x liegt innerhalb des maximalen Gesamt-Wertebereichs von b, sprich innerhalb von 3 bis 112. Je nach Wert von x wird für b der passende Wertebereich rausgesucht und davon abhängig die Bitanzahl für b und somit auch der Wert von a bestimmt.
Bei y ist dies ähnlich. Da y aber immer größer als x sein muss, wird zunächst (x + 1) von y abgezogen. Das Ergebnis nennen wir mal yy.
yy liegt nun innerhalb des maximalen Gesamt-Wertebereichs von d, sprich innerhalb von 0 bis 2029. Je nach Wert von yy wird für d der passende Wertebereich rausgesucht und davon abhängig die Bitanzahl für d und somit auch der Wert von c bestimmt.
Daraus ergibt sich eine Gesamtbitanzahl.
Ziel:
Das Ziel des Algorithmus, der nur x als Eingabe erhält und die Grundlagen kennt (ok, nur ich kenne sie :) ), ist es nun abhängig von x ein maximales y zu bestimmen, sodass gilt:
NötigeGesamtbitanzahl <= x * 4
Ich steh grad echt auf dem Schlauch. Schon allein die nötige Bitanzahl für b, abhängig von x zu berechnen, will mir nicht glücken. Habt ihr da Ideen?