Summe und Produkt von zwei Feldern ( arrays)

[Andi2342]

Hallo,
Um mit beliebig großen natürlichen Zahlen rechnen zu können, sollen in dieser Aufgabe natürliche
Zahlen als Arrays von int-Werten aus dem Intervall [0,9] in natürlicher Weise repräsentiert
werden. Die Zahl 12345 wird also durch das Array [1] [2] [3] [4] [5] dargestellt.


Ich möchte ein Programm schreiben, dass zwei Zahlen als String einliest, auf oben beschriebene
Art repräsentiert und die Summe bzw Produkt der eingelesenen Zahlen ausgibt.

Also z.B. 4 5 6 + 5 8 7 = 1 0 4 3

Wobei dann [6] + [7] = [3] ergibt und +1 zum [i-1] Feld addiert werden muss.

Wie kann ich dass am besten umsetzen?

Jmd. einen Lösungvorschlag.

Mfg

Andi

 

[Wildcard]

Um mit beliebig großen natürlichen Zahlen zu rechnen nimmt man BigInteger.

 

[Marco13]

Lösungsvorschlagt? Nun, keinen der "detaillierter" ist, als das, was du in der ... zweiten Klasse gelernt hast.

1. Addiere die letzten Stellen.
2. Wenn der neue Übertrag 0 is, bist du fertig.
3. Andernfalls addiere die nächstletzten Stellen und den Übertrag, und gehe zu 2.

 

[Andi2342]

Und was sollte ich bei der Multiplikation machen ?

Wie kann ich das Feld dann ausgeben, dann müsste ich es ja eigentlich wieder zurück in ein String wandeln?

mfg

 

[Tharsonius]

Was Du auf alle Fälle bedenken musst ist, dass das Ergebnis Array eventuell größer ist als die beiden einzelnen Summanden.

Wenn Du die Addition fertig hast, dann ist eine Multiplikation letztendlich nichts anderes als eine vielfache Addition. Wobei das ganze bei großen zahlen schon ein ganzes weilchen dauert.

ich würde eine Multiplikation aufsplitten in mehrfache Additionen.

[x1] [x2] * [y1] [y2]

=> ([x1] [x2] *10) * [y1] + [x1] [x2] * [y2]

In einem weiteren schritt lässt Du einfach für jede teilmultiplikation eine Schleife laufen, die entsprechend oft die zahl auf sich selbst aufaddiert.

[x1] [x2] * 3

=> [x1] [x2] + [x1] [x2] + [x1] [x2]

Wobei gerade *10 auch recht einfach gelöst werden kann, im dem Du einfach eine 0 anhängst.

 

[Marco13]

Sowas wie x * 5 zu implementieren als x+x+x+x+x würde ich nicht empfehlen. Stattdessen sollte die Mutliplikation erstmal auch so ablaufen, wie man sie schriftlich eben macht. (Über Optimierungen haben sich die Prozessorbauer schon viele Gedanken gemacht - da kann man sich weitere Inspiration holen). Für das Ergebnis kannst du genug Speicher bereitstellen: Bei der Addition kann das Ergebnis höchstens eine Stelle mehr haben, als der größere Summand. Bei einer Multiplikation ist die Anzahl der Stellen höchstens die Summe der Stellen der Faktoren.

 

[Andi2342]

Hallo,

Das ist bislang mein Code:

MiniJava benutzen wir in der UNI:

public class natzahl extends MiniJava {
public static void main(String[] args) {

String zahl1 = readString();
String zahl2 = readString();


int[] a; // Deklaration
int n1 = zahl1.length();
a = new int[n1];
// Anlegen des Felds
int i = 0;
while (i < n1) {
a[i] = (int)(zahl1.charAt(i)) - (int)'0';
i = i+1;
}     //jetzt sind alle Werte von Zahl1 im Feld1 a gespeichert

int[] b; // Deklaration
int n2 = zahl2.length();
b = new int[n2];
// Anlegen des Felds
i = 0;
while (i < n2) {
b[i] = (int)(zahl2.charAt(i)) - (int)'0';
i = i+1;
}     //jetzt sind alle Werte von Zahl1 im Feld2 b gespeichert

// NUN HABEN WIR DIE BEIDEN ARRAYS


if (n1 >= n2){
int zaehler = n2;
i = 0;
int[] c;
c = new int[n1+1]; // +1 da bei Addition höchstens eine Stelle dazukommen kann
int n3 = c.length;
while (i < n1){
i = i + 1;
if (i <= zaehler){
c[n3] = a[n1] + b[n2];
n2 = n2 - 1;
}
else {
c[n3] = b[n2];
}
n1 = n1 - 1;
n3 = n3 - 1;
}
}
else
{
int zaehler = n1;
i = 0;
int[] c;
c = new int[n2+1]; // +1 da bei Addition höchstens eine Stelle dazukommen kann
int n3 = c.length;
while (i < n2){
i = i + 1;

if (i <= zaehler){
c[n3] = b[n2] + a[n1];
n1 = n1 - 1;
}
else {
c[n3] = b[n2];
}
n2 = n2 - 1;
n3 = n3 - 1;
}
return c;
}

// JETZT MUESSEN WIR NOCH DAFUER SORGEN, DASS ES KEINE ZWEISTELLIGEN ZAHLEN IN EINEM FELD GIBT

int zaehler =  c.lenght;      //evtl. wird zur Laenger die c[0] nicht addiert
i = 0;
while (i < zaehler){
if (c[n3] >= 10){
c[n3] = c[n3] - 10;
c[n3-1] = c[n3-1] + 1;
}
n3 = n3 - 1;
i = i + 1;
}
// Nun muss der Array noch in ein String umgewandelt werden

String res = "";

for(int i=0; i<a.length; i++)
  res += c[i]; // entspricht b = b + a[i];

write(res);

}
}

Leider lässt er sich nicht kompilieren, da anscheinend das Feld c[] nur für eine Operation gespeichert wird.
Kann mir jemand einen Tipp geben, wie ich das lösen kann?

 

[Andi2342]

Die Klasse MiniJava hier zum Download:
http://www2.in.tum.de/lehre/vorlesungen/WS07/info1/MiniJava.java

 

[Marco13]

Jo, jetzt ist es compilierbar. Den/die übrigen Fehler mußt du selbst finden...

public class natzahl extends MiniJava
{
    public static void main(String[] args)
    {

        String zahl1 = "123"; //readString();
        String zahl2 = "456"; //readString();

        int[] a; // Deklaration
        int n1 = zahl1.length();
        a = new int[n1];
// Anlegen des Felds
        int i = 0;
        while (i < n1)
        {
            a[i] = (int) (zahl1.charAt(i)) - (int) '0';
            i = i + 1;
        } //jetzt sind alle Werte von Zahl1 im Feld1 a gespeichert

        int[] b; // Deklaration
        int n2 = zahl2.length();
        b = new int[n2];
// Anlegen des Felds
        i = 0;
        while (i < n2)
        {
            b[i] = (int) (zahl2.charAt(i)) - (int) '0';
            i = i + 1;
        } //jetzt sind alle Werte von Zahl1 im Feld2 b gespeichert

// NUN HABEN WIR DIE BEIDEN ARRAYS

        int[] c;
        int n3;
        if (n1 >= n2)
        {
            int zaehler = n2;
            i = 0;
            c = new int[n1 + 1]; // +1 da bei Addition höchstens eine Stelle dazukommen kann
            n3 = c.length;
            while (i < n1)
            {
                i = i + 1;
                if (i <= zaehler)
                {
                    c[n3] = a[n1] + b[n2];
                    n2 = n2 - 1;
                }
                else
                {
                    c[n3] = b[n2];
                }
                n1 = n1 - 1;
                n3 = n3 - 1;
            }
        }
        else
        {
            int zaehler = n1;
            i = 0;
            c = new int[n2 + 1]; // +1 da bei Addition höchstens eine Stelle dazukommen kann
            n3 = c.length;
            while (i < n2)
            {
                i = i + 1;

                if (i <= zaehler)
                {
                    c[n3] = b[n2] + a[n1];
                    n1 = n1 - 1;
                }
                else
                {
                    c[n3] = b[n2];
                }
                n2 = n2 - 1;
                n3 = n3 - 1;
            }
            //return c;
        }

// JETZT MUESSEN WIR NOCH DAFUER SORGEN, DASS ES KEINE ZWEISTELLIGEN ZAHLEN IN EINEM FELD GIBT

        int zaehler = c.length; //evtl. wird zur Laenger die c[0] nicht addiert
        i = 0;
        while (i < zaehler)
        {
            if (c[n3] >= 10)
            {
                c[n3] = c[n3] - 10;
                c[n3 - 1] = c[n3 - 1] + 1;
            }
            n3 = n3 - 1;
            i = i + 1;
        }
// Nun muss der Array noch in ein String umgewandelt werden

        String res = "";

        for (i = 0; i < a.length; i++)
            res += c[i]; // entspricht b = b + a[i];

        write(res);

    }
}

 

[ANdi2342]

Kann den Fehler einfach nicht finden warum es ein ARRAYINDEXOUTOFBOUNDS gibt in Zeile 46?

Für mich macht alles Sinn ?
Kann mir jmd. weiterhelfen?