Rechnen mit mehrstelligen Zahlen
-
(Achtung, bin noch Anfänger :))
Und zwar möchte ich 2 mehrstellige Zahlen multiplizieren.. Der Knackpunkt dabei ist, dass die beiden Zahlen bis zu 30 Stellen und mehr haben können! (Anzahl wird über eine Konstante definiert)..
Wie soll ich das ganze angehen?
Im Prinzip erstell ich ja mal zwei char Arrays für das einlesen der "Zahlen"..
(da die normalen int, double.. nicht 30+ Stellen ausgeben könnten..)char ErsteZahl[31]; char ZweiteZahl[31]; char Resultat[166];Ich müsste mir evt irgendwie die schriftliche Multiplikationsweise zur Hilfe nehmen, ne FoR-Schleife..., doch ich hab kein Plan wie ich das umsetzen soll
Ich hoffe ihr könnt mir helfen
MfG
-
eMaNu3L schrieb:
Ich müsste mir evt irgendwie die schriftliche Multiplikationsweise zur Hilfe nehmen, ne FoR-Schleife..., doch ich hab kein Plan wie ich das umsetzen soll
Nimm einen Zettel und 2 Zahlen (3-stellige) und rechne. Merke dir was du machst.
Du kannst die Zahlen auch von hinten nach vorne durchgehen oder erst zum Schluss umdrehen.
Wenn die Zahlen als Text vorliegen, bedenke das 0 was anderes ist als '0'.
-
Danke für den Tipp Dirk,
Sieht im Moment so aus:
#define MAXSTELLEN 31 #define RESULTATMAXSTELLEN 166 int main() { /* VARIABLEN (lokal) --------- */ char ErsteZahl[MAXSTELLEN]; char ZweiteZahl[MAXSTELLEN]; int Resultat[RESULTATMAXSTELLEN]; int i, j = 0; /* Intro --------------------- */ printf("Dieses Programm multipliziertz zwei %i-Stellige Zahlen\n", MAXSTELLEN-1); printf("------------------------------------------------------\n\n\n"); printf("Geben Sie ihre erste Zahl ein: "); scanf("%s", &ErsteZahl); printf("Geben Sie ihre zweite Zahl ein: "); scanf("%s", &ZweiteZahl); /* Berechnung ---------------- */ for (i = 0; i < strlen(ErsteZahl); i++) { for (j = 0; j < strlen(ZweiteZahl); j++) { Resultat[i + j] += ErsteZahl[i] * ZweiteZahl[j]; if (Resultat[i + j] > 9) { Resultat[i + j + 1] = Resultat[i + j] / 10; Resultat[i + j] = Resultat[i + j] % 10; } } } printf("\nResultat: %d\n", Resultat); system("PAUSE"); return 0; }Doch er gibt immer das falsche Ergebnis aus??
-
Es sagte DirkB vorausahnend:
DirkB schrieb:
Wenn die Zahlen als Text vorliegen, bedenke das 0 was anderes ist als '0'.
//Vielleicht so Resultat[i + j] += (ErsteZahl[i]-'\0') * (ZweiteZahl[j]-'0') if (Resultat[i + j] > '9') { Resultat[i + j + 1] = (Resultat[i + j]-'0') / 10 + '0'; Resultat[i + j] = (Resultat[i + j]-'0') % 10 + '0';Aber ich würde das nicht machen, sondern eine Funktion fürs Einlesen und eine für's Anzeigen machen, und dafür die Zahlen nicht als ASCII ablegen, also mit 0='\0' und nicht 0='0'.
-
DirkB schrieb:
... bedenke das 0 was anderes ist als '0'.
Ich habe den Algorythmus jetzt nicht durchgesehen aber:
In deinen Arrays ErsteZahl und ZweiteZahl stehen Texte drin und da ist '0' was anderes als 0.printf(" mit': %d ;ohne': %d\n",'0',0);Darum musst du bei deinen Zahlen immer '0' abziehen oder dazurechnen.
Du musst das Array Result initialisieren.
Am Ende muß eine '\0' hin.Und bei printf("\nResultat: %d\n", Resultat); funktioniert %d sicher nicht (das gibt int aus).
-
Auch wenn das nur eine Übung ist; gewöhne dir an, eine Struktur für die einzelnen Zahlen zu erstellen (die vllt. nur ein Array enthält) und eine Funktion fürs Einlesen und Multiplizieren zu schreiben. Es ist nicht nur für uns ästhetischer, es hilft auch dir beim Denken.
Nur so nebenbei: wenn du es wirklich performant haben willst, musst du mit der Fourier-Transformation arbeiten. Dann kannst du die Zahlen in O(n·log(n)) anstatt O(n2) wie jetzt multiplizieren. Aber so wie du fragst, wird dich das nicht kümmern.
-
Furie schrieb:
Nur so nebenbei: wenn du es wirklich performant haben willst, musst du mit der Fourier-Transformation arbeiten. Dann kannst du die Zahlen in O(n·log(n)) anstatt O(n2) wie jetzt multiplizieren. Aber so wie du fragst, wird dich das nicht kümmern.
eMaNu3L schrieb:
Der Knackpunkt dabei ist, dass die beiden Zahlen bis zu 30 Stellen und mehr haben können!
-
-
Also im Moment siehts so aus:
#include <stdio.h> #include <stdlib.h> #define MAXSTELLEN 31 #define RESULTATMAXSTELLEN 166 int main() { /* VARIABLEN (lokal) --------- */ char ErsteZahl[MAXSTELLEN]; char ZweiteZahl[MAXSTELLEN]; char Resultat[RESULTATMAXSTELLEN]; int i, j = 0; /* Intro --------------------- */ printf("Dieses Programm multipliziertz zwei %i-Stellige Zahlen\n", MAXSTELLEN-1); printf("------------------------------------------------------\n\n\n"); printf("Geben Sie ihre erste Zahl ein: "); scanf("%s", &ErsteZahl); printf("Geben Sie ihre zweite Zahl ein: "); scanf("%s", &ZweiteZahl); /* Berechnung ---------------- */ for (i = 0; i < strlen(ErsteZahl); i++) { for (j = 0; j < strlen(ZweiteZahl); j++) { Resultat[i + j] += (ErsteZahl[i]-'\0') * (ZweiteZahl[j]-'0'); if (Resultat[i + j] > '9') { Resultat[i + j + 1] = (Resultat[i + j]-'0') / 10 + '0'; Resultat[i + j] = (Resultat[i + j]-'0') % 10 + '0'; } } } } /* Ausgabe ------------------- */ printf("\nResultat: %s\n", Resultat); system("PAUSE"); return 0; }leider funzts immer noch nicht :(( (Kann es nicht starten..) Irgendein Conflicting Type printf und noch ne andere Fehlermeldung spuckt er aus
Was hab ich den falsch? Hab echt kein Plant
Hoffe ihr könnt mir helfen
MfG
-
ok debuggen klappt.. (ne klammer zuviel gehabt :D), doch ergebnis immer wieder falsch.. gibt immer welche smileys oder sonstiges aus
-
Du solltest schon bei den Einerstellen anfangen zu rechnen. Im Augenblick fängst du bei der höchsten Stelle an (ganz links).
Du musst die Strings irgendwie umdrehen oder von rechts nach links rechnen.
Das betrifft auch das Ergebnis. (Habe ich aber schon in meinem ersten Post erwähnt )Einmal hast du '\0' statt '0' stehen.
Resultat sollte mit "000000000.....000" vorbesetzt sein, sonst klappt die Zeile 30 nicht.. (Mach eine Schleife).
Bei der Eingabe von Strings brauchst du bei scanf kein &
!
-
Ich arbeite grade an was Ähnlichem (allerdings mit linked lists und integern, was aber im Endeffekt aufs gleiche rauskommen sollte).
Addition funktioniert, aber mir ist noch kein Ansatz eingefallen um bei Multiplikation nen overflow zu vermeiden. Wenn ich zum Beispiel 999999... mit 99999999.... multipliziere könnte der Übertrag ziemlich groß werden (wenn man das schriftliche Multiplikationsverfahren benutzt).
Ich hab mir mal den Wikipedia-Artikel zu Fourier-Transformation angesehen, aber außer kryptischen Zeichen sehe ich da nicht viel.
Hat jemand vielleicht nen anderen Ansatz oder kann das mit der Fourier-Transformation erklären?
-
Wenn du ein N-stellige mal M-stellige Zahl multiplizierst hat das Ergebnis max. N+M Stellen (min. N+M-1 Stellen) . Egal ob schriftlich oder sonst wie multipliziert.
Den Überlauf kannst du vermeiden, wenn du für das Ergebnis N+M Stellen reservierst.
-
Beim Multiplizieren zweier Ziffern hast du maximal den Übertrag 8 (9*9=81), das ist noch leicht zu verarbeiten. Daher müsstest du die Multiplikation in mehrere Teilschritte zerlegen:
zahl mult(zahl a,zahl b) { zahl result; for(int i=0;i<a.length;++i) { zahl subresult = multziffer(a[i],b); verschiebe(subresult,i);// Multiplikation mit 10^i -> i Nullen an den Anfang anhängen result = add(result,subresult); } return result; } zahl multziffer(int z, zahl b) { int carry=0; assert(ziffer<10); zahl result; for(int i=0;i<b.length;++i) { int value = b[i]*z + carry; result[i] = value%10; carry = value/10; } if(carry>0) result[b.length]=carry; return result; }(ist natürlich alles nur Pseudocode und ungetestet)
-
ahja stimmt
ich dachte, dass ich carry nocheinmal mit 9 multiplizieren müsste, aber das ist natürlich schwachsinn
Vielen Dank
