Langzahl mit Array

[Tipp Ex]

Hallo,
ich habe mit Java vor 4 Wochen angefangen und komme bei einer Übungsaufgabe nicht weiter.
Man stelle sich ein Schachbrett vor und auf das erste der 64 Felder des Schachbretts wird ein Weizenkorn gelegt, auf das zweite zwei, auf das dritte vier usw.
Auf das nächste Feld kommt immer die doppelte Anzahl von Körnern.
Maximal gibt es 2^63 Körner.
Der größte Datentyp in Java,den ich bis jetzt gelernt habe ist long.
Allerdings geht bei long genau da der Speicher aus,denn da sind nur 2^63-1 möglich.
Also muss man sich was ausdenken.
Mein Ansatz:
Man nehme ein Array,welches 19 Stellen lang ist.
Jedes Feldelement stellt eine Ziffern dar, addiert wird Ziffernweise mit Übertrag.
So weit so gut,mein bisher geschriebener Code:

 public static void main(String args[])    
    {
        int [] langzahl = new int [19];                
        int laengeZahl;
        laengeZahl = langzahl.length; 
        
        langzahl[laengeZahl-1] = 1;
        
        for (int i = 2; i < 64; i++)
            {
                System.out.println("\nFeld: " + i);           
                addieren(langzahl);
            }
    }  
    
    public static void addieren(int[] zahl1)
    {
        int ziffer1, ziffer2, tempZiffer, ziffersumme, uebertrag;
        int[] koerner = new int[19];        
        int[] zahl2 = new int[19];
        uebertrag = 0;
        
        //Weizenkörner bzw. Zahl2 bestimmten; Zahl 2 ist das Doppelte wie Zahl 1       
        
        for (int i = zahl1.length-1; i >= 0; i--)
        {
            ziffer1 = zahl2[i];            
            tempZiffer = 2 * zahl1[i];
            if (ziffer1 + tempZiffer + uebertrag > 10)
                {
                    ziffersumme = (ziffer1 + tempZiffer + uebertrag) / 10;
                    uebertrag = 1;
                    //zahl2[i] = ziffersumme;
                    zahl1[i] = ziffersumme;
                }
            else if (tempZiffer + ziffer1 + uebertrag == 10)
                {
                    ziffersumme = 0;
                    uebertrag = 1;
                    //zahl2[i] = ziffersumme;
                    zahl1[i] = ziffersumme;
                }                    
            else
                {
                    ziffersumme = ziffer1 + tempZiffer + uebertrag;
                    uebertrag = 0;
                    //zahl2[i] = ziffersumme;
                    zahl1[i] = ziffersumme;
                }                
        }
        
        // Zahl 2 bzw. Weizenkörneranzahl ausgeben
        System.out.println("Weizenkörner : ");
        for (int j = 0; j < zahl1.length; j++)
             System.out.print(zahl1[j]);         
    }

Für die ersten vier Felder scheints richtig zu sein,ab dem fünften ist es falsch.
Nun meine Frage,ob ich mit dem Ansatz auf dem richtigem Weg bin und wo ich nochmal ansetzen muss.
Gesucht nach diesem Problem habe ich bereits.
Gestoßen bin ich auf Lösungen mit big integer (kenn ich noch nicht und darf ich so nicht benutzen) und arrays mit int und string,die ich aber nicht nachvollziehen kann (zumal ich inttostr bzw. strtoint auch noch nicht kenne und nicht benutzen darf).

Danke für's Lesen!

 

[TKausL]

Oder man nehme BigInteger (Java 2 Platform SE v1.4.2)

 

[Ark]

Es wurde doch gesagt, dass BigInteger nicht erlaubt ist …

Ark

 

[Bernd Hohmann]

Es wurde doch gesagt, dass BigInteger nicht erlaubt ist …

Da würde ich mir aber gerne doch mal die Aufgabenstellung dazu anschauen wollen ob wirklich eine "zu fuss" Multiplikation angesagt ist.

Bernd

 

[TKausL]

Es wurde doch gesagt, dass BigInteger nicht erlaubt ist …

Ark

Oh, hab das wohl überlesen...
Kannst du mal bitte die komplette Aufgabenstellung posten?

 

[Spacerat]

Eines vorweg, wie kommst du auf 2 ^ 63? Das sind gerade mal die Anzahl der Weizenkörner auf dem letzten Feld, aber egal.
Natürlich lässt sich diese Berechnung ganz simpel mit charArrays berechnen (obwohl mit ints ists noch simpler *).

public class StringCalc {
	public static void main(String[] args) {
/*		char[] number = new char[(int) Math.log10(Math.pow(2, 64))]; // OMG... tatsaechlich 19...
		long l = 1;
		for(int n = 1; n < 64; n++) {
			add(number, reverse(Long.toString(l).toCharArray()));
			l <<= 1; // ooops... l *= 2 natuerlich, sorry ;)
		}
		System.out.println(String.valueOf(reverse(number)));*/
		char[] number = new char[(int) Math.ceil(Math.log10(Math.pow(2, 64) - 1))]; // nu sinds 20
		long l = 1;
		for(int n = 1; n <= 64; n++) {
			if(l < 0) {
				// zum Behelf mit 64 Bits... darüber geht's nicht (isch denk')
				l = Long.MAX_VALUE;
				add(number, reverse(Long.toString(l).toCharArray()));
				l = 1;
				add(number, reverse(Long.toString(l).toCharArray()));
			} else {
				add(number, reverse(Long.toString(l).toCharArray()));
				l *= 2;
			}
		}
		System.out.println(String.valueOf(reverse(number)));
	}

	private static char[] reverse(char[] number) {
		for(int n = 0; n < number.length / 2; n++) {
			int back = number.length - 1 - n;
			char tmp = number[back];
			number[back] = number[n];
			number[n] = tmp;
		}
		return number;
	}

	private static void add(char[] a, char[] b) {
		int l = Math.min(a.length, b.length);
		int c;
		for(int n = 0; n < l; n++) {
			b[n] &= ~'0';
			if(b[n] > 9) {
				throw new NumberFormatException();
			}
			a[n] &= ~'0';
			if((c = a[n] + b[n]) > 9) {
				a[n + 1] &= ~'0';
				a[n + 1] += (c / 10);
				a[n + 1] |= '0';
			}
			a[n] = (char) (c % 10);
			a[n] |= '0';
		}
	}
}

* Da spart man sich nämlich das ständige hin und her gewandle zwischen Zeichen und Zahl .
[EDIT]Okay, da muss ich wohl noch mal ran...
1. Es muss "<= 64" heissen.
2. Dadurch wird der Longwert negativ.
3. Dadurch schmeisst "add()" 'ne Exception.[/EDIT]
[EDIT]Soo, mit dem kleinen Behelf für den (in diesem Fall einen) Fall, dass der Longwert negativ wird, funktioniert das soweit.[/EDIT]

 

[Tipp Ex]

Vielen lieben Dank für eure Antworten!
Hier mal die Aufgabe mit nem Hinweis:

Das Programm soll längere Zahlen verarbeiten können, als in "long" darstellbar sind.
Anzahl der Körner pro Schachfeld und die jeweilige Summe sollen in wie folgt ausgegeben werden:

Schachfeld Körner Summe der Körner
2 00000000002 00000000003

Strukturieren Sie Ihr Programm durch geeignete Methoden.

Lösungshinweis:
Um zu einer Problemlösung zu gelangen, wird zunächst eine Addition im Dezimalsystem durchgeführt.
Eine Langzahl kann durch n int-Zahlen dargestellt werden.Bei der Langzahladdition wird elementweise addiert,ein möglicher Übertrag ermittelt und bei der Addition berücksichtigt.

BigInteger hatten wir noch nicht und selbst deklarierte Funktionen auch nicht.
Spacerat,vielen Dank für deine Mühen aber ich verstehe nur die Hälfte und habe genausoviele Sachen noch nie gesehen. :O

 

[no0b]

Mach's für den Anfang so:

    public static void main(String[] args) {
        int[] zahl = new int[1000]; // int macht am wenigsten Probleme, ist aber nicht am platzsparendsten
        zahl[999] = 2;
        for (int i = 0; i < 62; i++) {
            mul(zahl, 2);
        }
        System.out.println("zahl = " + Arrays.toString(zahl));
    }

    private static void mul(int[] zahl, int wert) {
        int ü = 0;
        for (int i = zahl.length - 1; i >= 0; i--) {
            ü = zahl[i] * wert + ü;
            zahl[i] = ü % 10;
            ü /= 10;
        }
        if (ü != 0) {
            throw new ArithmeticException("Überlauf: " + ü);
        }
    }

Voilà (so viele auf dem 64. Feld):

..., 9, 2, 2, 3, 3, 7, 2, 0, 3, 6, 8, 5, 4, 7, 7, 5, 8, 0, 8]

Eine Methode, eine vernünftige Zahl auszugeben, kannst du ja wohl:

        System.out.println("zahl = " + zahlToString(zahl));
    }

    private static String zahlToString(int[] zahl) {
        StringBuilder b = new StringBuilder(zahl.length);
        int i = 0;
        while (i < zahl.length && zahl[i] == 0) {
            i++;
        }
        while (i < zahl.length) {
            b.append(zahl[i++]);
        }
        return b.toString();
    }

gn8!

 

[Spacerat]

    public static void addieren(int[] zahl1)
    {
        // readaktionell gekuerzt
    }

Wie, ihr hattet noch keine selbst deklarierten Funktionen? Okay... in Java gibt's so etwas ohnehin nicht, da gibt es nur Methoden. Aber wie auch immer, eine solche hast du mindestens schon deklariert.
Und ganz Ehrlich... ganz ohne Methoden wirst du es nicht machen wollen.

 

[Tipp Ex]

Soweit wie mein Verständnis reicht,sind Funktion Methoden,die einen Rückgabewert geben und Prozeduren halt nicht.
Danke für eure Vorschläge,habe die Aufgabe jetzt lösen können.
Ich frage mich,ob es von alleine kommt(Erfahrung),dass man solche Probleme gezielt und kurz lösen kann ohne unnötigen Ballast.
Schönen Abend noch!

 

[Spacerat]

Herzlichen Glückwunsch...
1. Funktionen sind in Gegensatz zu Methoden klassenlos. In Java bekäme man das nicht hin, weil man hier immer mit 'ner Klasse arbeitet, sogar statiche Methoden müssen in einer Klasse deklariert werden. (merken: Methoden haben "Klasse"! ).
2. Stimmt. Prozeduren sind Funktionen oder Methoden ohne bzw. mit Rückgabetyp "void". Ändert aber nichts an der Tatsache, wie man Funktionen von Methoden unterscheidet.
3. Natürlich kommt das "von allein" rtfm. Mit der Zeit geht alles besser. Gerade in Java (ähnlich wie in C#) hat man relativ wenig von Dingen, die man sich merken muss, kurz, wenig Ballast und damit eine recht gute (steil, flach? Wie auch immer... gehört für mich zu den Dingen, die man sich nicht merken muss :lol Lernkurve.

 

[no0b]

Methode, Funktion, Prozedur, (Sub)-Routine bedeuten alle das gleiche, nur wer unbedingt etwas dazuerfinden will, erfindet etwas dazu.

Schöne Grüße, no0b

 

[no0b]

Meine Quelle dazu: Hörensagen und Subroutine - Wikipedia, the free encyclopedia

PS. Sorry wegen Doppelpost.

 

[Spacerat]

[OT]

Meine Quelle dazu: Hörensagen und Subroutine - Wikipedia, the free encyclopedia

PS. Sorry wegen Doppelpost.

Das ist wirklich OT aber egal...
Sicher, prinzipiell ist's alles das selbe. Bei Wikipedia ist aber auch zu Lesen:

Je nach Programmiersprache und Programmierparadigma gibt es Unterschiede in der Abgrenzung zwischen den Begriffen Funktion und Prozedur.

Ansonsten galt für mich immer: Prozedur = (Wiederverwendbarer) Programmabschnitt ohne Rückgabewert, Funktion = (Wiederverwendbarer) Programmabschnitt mit Rückgabewert, Methode = Operation auf einer Klasse (gekapselte Daten). Eine solche Unterscheidung macht auch durchaus Sinn.[/OT]

 

[no0b]

[OT]Im Zweifel gilt die Jls [/OT]

 

[masterofpuppets]

Hallo,
Es soll ja zum Schluss der Aufgabe noch die Summe der felder ausrechnet werden. Wie funktioniert das?
So siehts bisher aus, komm aber nicht drauf wie man die jeweils aktuellen Summen dazu berechnet:

public class Schachbrett {

//berechnet Zahl über Langzahlarithmetik
private static void mul(int[] zahl, int wert) {
int ü = 0;
for (int i = zahl.length - 1; i >= 0; i--) {
ü = zahl * wert + ü;
zahl = ü % 10;
ü /= 10;
}
if (ü != 0) {
throw new ArithmeticException("Überlauf: " + ü);
}
}

//bildet aus Zahl String im richtigen Format, hier weiter
private static String zahlToString(int[] zahl) {
StringBuilder b = new StringBuilder(zahl.length);
int i = 0;
while (i < zahl.length-19 && zahl == 0) { //-19 da nur letzten 19 stellen der zahl zurückgegeben werden sollen
i++;
}
while (i < zahl.length) {
b.append(zahl[i++]);
}
return b.toString();
}

//bildet aktuelle Summe
private static String summeZahlen(int[] zahl) {
StringBuilder a = new StringBuilder(zahl.length);
int i = 0;
while (i < zahl.length-19 && zahl == 0) { //-10 da nur letzten 19 stellen der zahl zurückgegeben werden sollen
i++;
}
while (i < zahl.length) {
a.append(zahl[i++]+zahl[i++]/2);
}
return a.toString();
}

public static void main(String args[]) {
System.out.println("Schachfeldzaehler"+ " " +"Koerner" + " " +"Summe der Koerner");
System.out.println(1 + " " + "0000000000000000001" +" " + "0000000000000000001"); //erstes Feld
System.out.println(2 + " " + "0000000000000000002" +" " + "0000000000000000003"); //zweites Feld
int[] zahl = new int[1000]; // int macht am wenigsten Probleme, ist aber nicht am platzsparendsten
zahl[999] = 2;
for (int i = 0; i < 62; i++) {
mul(zahl, 2);
//System.out.println("zahl = " + zahlToString(zahl));
int Feld=i+3;
System.out.println(Feld + " " + zahlToString(zahl));
// System.out.println(summeZahlen(zahl));
//2 00000000002 00000000003
}

}

}