Algorithmus zur Darstellung einer ganzen Zahl mit Basis B

[BlackDevil]

Sers

Aufgabe in Informatik ist die Darstellung einer ganzen Zahl zu einer Basis B.
Basis: 1-10
Zahl: 1-10

So jetz hab ich nich genau gewusst was der Kerl von mir will und hab gegoogelt. Bin dabei auf das PDF im Anhang gestoßen. Macht soweit auch sinn.

1012³ = 1*3³+0*3²+1*3^1+2*3^0 = 32
passt.

Aber 32 bekommt man egal zu welcher Basis mit dieser Methode zur 1012.
In dem PDF steht Ferner die Variante die Zahl durch die Basis zu Teilen und den Rest zu nehmen.

Das is alles Hübsch. In C++ funktioniert das auch allerdings nur für die 32.

Ich bin da echt mal Ratlos... Die Summenformel wär das einfachste darzustellen. Aber: Wie bekomme ich raus wieviele Stellen meine Zahl hat...

Wenn da jemand ne Idee hat wie ich das am besten gestalten kann wäre ich sehr sehr dankbar!

[Netbird]

Schau mal unter dem Stichwort Euklidischer Algorithmus nach ...
Das ist eine sehr gängige Methode mit Division und Rest-Verarbeitung ...

[BlackDevil]

Soweit so hübsch aber wie übersetz ich das? Der Pseudocode is fürn Po

Edit: Hätte inzwischen eine Lösung

#include <iostream>
using namespace std;

void main()
{
int zahl, basis;
int mod;
cout << "Eingabe: ";
cin >> zahl;
cin >> basis;
int i=basis;

for(int i=basis; i>=1; i--){
mod=zahl%basis;
cout << mod;
zahl=zahl/basis;
}

cout << endl;
system("PAUSE");
}

Das einzig blöde is das ich nich ganz weis wieso das funktioniert und vor allen schiebt der mir jenach basis nullen ein (davor oder dahinter)...
Das Problem bekomme ich irgendwie nich ganz behoben :(

grüße

ps: hab mit
http://www.umrechnung.org/zahlensystem-umrechnen/zahlensystem-basis-bin-hex-dez.htm
verglichen

[mare_crisium]

BlackDevil,

ich erkläre mir das immer so:

Wenn Du eine positive ganze Zahl Z mit einer Basis B darstellen willst, dann sieht das Endergebnis immer so aus:

Z = z0 +z1*B^1 + z2*B^2 + z3*B^3 + ... + zk*B^k

die Zahlen z0, z1, z2 usw. bis zk sind zunächst unbekannt. Du weisst nur, dass alle zi ganze Zahlen zwischen 0 und B-1 sind.

Die Formel kannst Du umschreiben, indem Du B jeweils als Faktor vor eine geschachtelte Folge von Klammern schreibst:

Z = z0 + B*(z1 + B*(z2 + B*(z3+ ... +zk*B))...)))

Das musst Du Dir an einem Beispiel mal hinschreiben, dann siehst Du's auch: Nämlich, dass die Zahl Z bis auf den Rest z0 durch B ganzzahlig teilbar ist:

Z-z0 = B*(z1 + B*(z2 + B*(z3+ ... +zk*B))...)))

Du kannst die Zahl Z also aufteilen in

1. z0 = Z mod B
und
2. Z' = Z div B = z1 + B*(z2 + B*(z3 + ... +zk*B))...)))

Der Witz daran ist, dass durch diese Aufteilung die Summe auf der rechten Seite um ein Glied kürzer geworden ist. Also machst Du immer so weiter

1. zi = Z' mod B
2. Z' = Z' div B

bis auf der rechte Seite nix mehr übrig ist, also Z' = 0. Dann hast du alle gesuchten zi berechnet. Und wenn Du daraus wieder die ursprüngliche Zahl Z zusammenbasteln willst, dann gehst Du einfach genau umgekehrt vor:

1. Schritt:
Z' = zk
2. Schritt:
Z' = zk-1 +B*Z'
3. Schritt
Z' = zk-2 + B*Z'
usw. bis
k. Schritt
Z = z0 +B*Z'

Ist das verständlich?

mare_crisium

Edit1: Die Basis B wurde zu verschiedenen Zeiten und in verschiedenen Kulturen unterschiedlich gewählt. Manche Kulturen nahmen die Zahl 12, weil es einerseits die Faktoren 1,2,3 (die ersten drei Primzahlen) enthält und es andererseits mit der Anzahl der Monate im Jahr zusammenfällt. Ausserdem kann man auch an einer Hand bis 12 zählen, wenn man die Fingerglieder ausser derer des Daumens zählt. - Das babylonische Zahlensystem hatte die Basis 60, enthielt also die 4 ersten Primzahlen als Faktoren. Deshalb hat die Stunde noch heute 60 Minuten ...

[BlackDevil]

das war soweit Verständlich. Ich habs zwar Mathematisch nich so aufgedröselt aber die Formel

http://img519.imageshack.us/img519/1466/sumum7.jpg
gab da den selben Aufschluss.

Eigentlich kann man Summenformeln immer wunderbar in eine While/For/DoWhile Schleife umbasteln nur bei der Stellt sich mir die Frage nach der Anzahl der Glieder (n). Ok jetz weis ich das ich nur zu Prüfen hab wann die Zahl null wird...

DU BIST EIN GOTT!

Wieso bin ich nich drauf gekommen das einfach ma zu probieren?


#include <iostream>
using namespace std;

void main()
{
int zahl, basis;
int mod;
cout << "Eingabe: ";
cin >> zahl;
cin >> basis;
int i=basis;

do{
mod=zahl%basis;
cout << mod;
zahl=zahl/basis;

}while(zahl!=0);

cout << endl;
system("PAUSE");
}


Tuts einwandfrei!

Vielen vielen dank! Ich hab das noch gar nich Probiert :D macht aber sinn ^^ Zahl/basis gibt mir dann damit die anzahl n der stellen an!

DANKE!

DANKE DANKE DANKE!

GRÜßE!

[Phantomix]

Wie wärs damit?

es gibt auch ne C-Funktion die ziemlich das gleiche macht, siehe itoa()


int IntToChars (char* buffer, int value, int spaceonbuffer, int countbase)
{
int workvalue = value;
int i;
int valuetowrite;
int end_i = 0;

if (value < 0)
{
workvalue = -value;
end_i = 1;
buffer[0] = '-';
}

for (i = spaceonbuffer - 1; i >= end_i; i--)
{
valuetowrite = (workvalue % countbase);
if (workvalue == 0)
{
if (i == (spaceonbuffer - 1))
{
buffer[i] = 48; // ASCII 0
} else {
buffer[i] = 32; // ASCII SPACE
}
} else {
if (valuetowrite > 9)
{
buffer[i] = valuetowrite + 55; // ASCII A-Z
} else {
buffer[i] = valuetowrite + 48; // ASCII of that character
}
};
workvalue = (workvalue - valuetowrite) / countbase;
}
return (workvalue); //this should be zero if enough space on buffer!
//otherwise it contains the digits not printed out
}

[BlackDevil]

ai das is ein wenig umfangreich, da hab ich ja nen theoretischen schlanken dreizeiler *g*

[Phantomix]

Korrekt, im Prinzip mache ich das gleiche wie du:

valuetowrite = (workvalue % countbase);

...

workvalue = (workvalue - valuetowrite) / countbase;


nur dass bei mir noch viel mehr konvertierung drumrum ist... negative Zahlen werden unterstützt, und - achja, am ende liegt alles in einem char* buffer

[BlackDevil]

Ja gut ich hab sachen wie workvalue und krempel noch nich einma gesehen in C++ Codes.... das machts nich leichter;)

[Phantomix]

ok da sind meine Namenskonventionen bissl mies... war eben ein quick&dirty weil ich so ne funktion brauchte. und einen tag später auf itoa() gestoßen bin...

achja der code ist C und compiliert mit dem avr-gcc

[BlackDevil]

Ach ein Fehler hat der code, meiner:
Er gibt bei 7 zur Basis 4 31 aus... nich 13