Informatiker Board | Druckvorschau: Beweis - Zahl mit logarithmisch vielen ziffern kodieren

Geschrieben von ka am 24.10.2013 um 00:15:

Beweis - Zahl mit logarithmisch vielen ziffern kodieren

Meine Frage:
Hallo, ich hab ein Frage zu folgender Aufgabe:

Sei eine natürliche Zahl b>1 (Basis) sowie b Zahlzeichen (Ziffern) z0,...,zb-1 für die natürlichen Zahlen 0=w(z0),....,b-1=w(zn-1) gegeben. xn-1,...,x0 kodiert die natürliche Zahl
(SUMMENZEICHEN i=0 bis n-1) w(xi)b^i.
Zeige, dass jede natürliche Zahl k so mit O(log zur Basis b von k) Ziffern kodiert werden kann.

Meine Ideen:
Mir ist aufjedenfall klar was eine Basis ist und das sie b-1 Ziffern besitzt.Mit dem Satz "xn-1,...,x0 kodiert die natürliche Zahl" kann ich leider wenig anfangen.
Wenn man das ganze für zB Basis 10 testet und die Zahl 10 als k, muss ich dann bei der Summenfunktion n=10 setzen, dann kommen enorm hohe Zahlen raus? und bei der log kommt Funktion 1 raus, was aber ja nicht stimmt weil man sie im dezimalsystem mit 2Ziffern darstellt.
Danke schonmal im voraus und sorry für die vielleicht unübersichtliche Darstellung meines Problems (:

Geschrieben von eulerscheZahl am 24.10.2013 um 06:04:

Etwas leserlicher:
Sei eine natürliche Zahl b>1 (Basis) sowie b Zahlzeichen (Ziffern) $[latex]z_0,\dots ,z_{b-1}[/latex]$ für die natürlichen Zahlen $[latex]0=w(z_0),....,b-1=w(z_{{\color{red}b}-1})[/latex]$ gegeben.
$[latex]x_{n-1},\dots ,x_0[/latex]$ kodiert die natürliche Zahl $[latex]\sum\limits_{i=0}^{n-1}{w(x_i)\cdot b^i}[/latex]$ .
Zeige, dass jede natürliche Zahl k so mit [latex]O(log_bk)[/latex]

Ziffern kodiert werden kann.

Zitat:

Wenn man das ganze für zB Basis 10 testet und die Zahl 10 als k, muss ich dann bei der Summenfunktion n=10 setzen

10 hat zwei Ziffern, daher ist n=2.

Geschrieben von ka am 24.10.2013 um 12:51:

Okay Danke, aber mir ist es leider immer noch nicht klar.

Wenn ich b=10 wähle und k=10 dann kommt bei der Summenformel doch folgendes raus:
n=1

0 * $[latex] 10^{1} [/latex]$ + 1 * $[latex] 10^{1} [/latex]$ = 10

oder was ist mit dem w( $[latex] x_{i} [/latex]$ ) genau gemeint?

Weil bei der log-Funktion kommt ja 1 raus aber obens sind es 2 Stellen.

Geschrieben von eulerscheZahl am 25.10.2013 um 05:29:

x0 ist die letzte Ziffer, [latex]x_i[/latex]

die i-te Ziffer von hinten.
10 hat zwei Ziffern x1=1 und x0=0.
$[latex]k = 10 = 1\cdot 10^1+0\cdot 10^0[/latex]$
Die Formel ist falsch, wie das Beispiel der 10 zeigt.
Wenn ich mich nicht irre, hat eine Zahl k $[latex]\log_b{\lceil k+1 \rceil}[/latex]$ Ziffern. Die Klammern bedeuten ceil (aufrunden).