Informatiker Board | Theoretische Informatik | Beweis - Zahl mit logarithmisch vielen ziffern kodieren

Informatiker Board » Themengebiete » Theoretische Informatik » Beweis - Zahl mit logarithmisch vielen ziffern kodieren

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Beweis - Zahl mit logarithmisch vielen ziffern kodieren
Beiträge zu diesem Thema	Autor	Datum
Beweis - Zahl mit logarithmisch vielen ziffern kodieren	ka	24.10.2013 00:15
RE: Beweis - Zahl mit logarithmisch vielen ziffern kodieren	eulerscheZahl	24.10.2013 06:04
RE: Beweis - Zahl mit logarithmisch vielen ziffern kodieren	ka	24.10.2013 12:51
RE: Beweis - Zahl mit logarithmisch vielen ziffern kodieren	eulerscheZahl	25.10.2013 05:29
RE: Beweis - Zahl mit logarithmisch vielen ziffern kodieren	ka	05.11.2013 16:52

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

ka
unregistriert

Beweis - Zahl mit logarithmisch vielen ziffern kodieren

Zitatantwort auf diesen Beitrag erstellen

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 (:

24.10.2013 00:15

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

24.10.2013 06:04

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

ka
unregistriert

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.

24.10.2013 12:51

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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).

__________________
Syntax Highlighting fürs Board (Link)

25.10.2013 05:29

ka
unregistriert

Danke für die Hilfe (:

05.11.2013 16:52

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Beweis - Zahl mit logarithmisch vielen ziffern kodieren