# Das Schachbrett - Reis Problem



## PHens (6. Dez 2013)

Hallo liebe Community,

Es geht um die alte Geschichte mit den Reiskörnern auf dem Schachbrett. In Kurzform:

Auf dem ersten Feld soll ein Reiskorn liegen, auf jedem weiteren wird die Anzahl Verdoppelt, und die Summe am Ende ausgegeben. Die Zahlen auf dem 64. Feld (8x8 Schachbrett) übersteigt leider die Speicherreichweite des Typs long. Mein Programm läuft theoretisch, bis auf das letzte Feld. Und hier stellt sich sicherlich auch der Schwerpunkt des Programmes dar. 

Ich darf die Klasse BigInteger nicht benutzen, muss also selbst ein Int Array entwickeln. In diesem Array soll quasi eine Schriftliche Addition stattfinden. Also: Ist die Zahl 0-9, soll diese Zahl am letzten Platz im Array gespeichert werden, ist die Zahl zweistellig, soll bei der 10, 20, 30 jeweils ein Übertrag in das nächste Arrayfeld von 1, 2, 3 passieren. So sollen alle Zahlen addiert und am Ende ausgegeben werden. 

Mein Grundprogramm sieht wie folgt aus: (Total simpel :bahnhof

Ausgegeben werden soll die Nummer des Feldes, die Anzahl der Körner auf diesem Feld und die Summe aller Körner.


```
public class ReisKoerner
{
   public static void main(String args[]) {
       
       long koerner=1;
       long summe=0;
              
       System.out.println("Felder       Körner     Summe Körner");
       for(int i=1;i<65;i++){
           
           summe = summe + koerner;
           System.out.println(i + "           " + koerner + "          "+summe) ;
           
           koerner += koerner; 
           
        
        }
    }
}
```

Um das Problem zu verdeutlichen, hier die letzten zwei Zeilen der Ausgabe:


```
Felder       Körner                      Summe Körner

63            4611686018427387904          9223372036854775807
64           -9223372036854775808          -1
```

Eine erste Idee war, eine for-Schleife rückwärts laufen zu lassen (ist das möglich?)


```
int [] reiskornsumme;
int [] reiskorn;

for(int i = reiskornsumme.length; i < 1; i--) 
for(int j = reiskorn.length; i < 1; i--)
```

und so Schritt für Schritt die in koerner und summe berechneten Werte zu übertragen. Leider gehen mir die Ideen, bzw. die Kenntnisse aus so eine Rechnung innerhalb eines Arrays zu realisieren, und hoffe auf Denkanstöße und Vorschläge.

(Ich habe vor 3 Semestern mal "Ingenieurinformatik" gehört, wo die Grundlagen der Javaprogrammierung vermittelt wurden. Nun helfe ich mit meinem Halbwissen meiner Freundin, sie lernt auch Grundlagen, nur im ET/IT Studium. Leider haben die schon nach 2 Monaten meinen Wissensstand überholt ;( Mit der Zeit ist auch einiges meiner Kenntnisse verloren gegangen :rtfm

Ich freue mich auf gemeinsame Lösung des Problems 

Liebe Grüße 

Philipp


----------



## Gucky (6. Dez 2013)

Dürft ihr Double verwenden? Ich weiß jetzt nicht, wie viel 2 hoch 63 ist aber double kann eine Zahl mit mehr als 300 Ziffern + Nachkommastellen speichern.

Die for-Schleife rückwärts laufen zu lassen ist kein Problem.

Zum fehlenden BigInteger:
Den kannst du dir relativ leicht selber schreiben. Ein Arry vom Typ byte (spart Speicher) mit bspw. 500 Stellen und da kommen dann die Zahlen rein. In Pseudocode sähe die Addition so aus:


```
public void addiere(großInt summand1, großInt summand2){
   int übertrag = 0;
   for (int i=0;i<summand1.length;i++){
      addiere Zahlen im selben Index+übertrag;
      Ist das Ergebnis größer als 10, speichere den Übertrag ab;
   }
}
```


----------



## PHens (7. Dez 2013)

Hi, danke erstmal für deinen Ansatz.

Double verwenden, ja. Grundlegend nicht verboten, jedoch werden double in solchen Dimensionen in der Form: Faktor * E^Exponent angegeben, wenn ich mich nicht Irre. Also total lange, krumme Dezimalzahlen.

Der Prof hat in einem Tip durchsickern lassen, dass die Zahlen in der Lösung so in etwa aussehen:


```
Feld      Körner        Summe 
2          000000002  000000002
```

Demnach ist das ja schon die Grundstruktur eines Arrays, logisch wären 20 Felder da die gößte Zahl 18 Billionen annimmt.
Zurück zu meiner Rückwärts-Schleife. Theoretisch könnte ich doch mit einer if-else Abfrage prüfen, ob die neue Zahl mehr als eine Stelle hat, und dann diese Zahl auf die Stellen _, [i-1], [i-2] ... übertragen ? Könnte man das umsetzen?  
Puuh, ich habe das gefühl, dass selbst das zu kompliziert gedacht ist. Solche "Rechenschritte" habe wir definitiv nicht gemacht, und ob die Elektrotechniker bei den Grundlagen so tiefgehen ... ? 

Wahrscheinlich ist die Lösung wieder mal so simpel, dass man von allein nicht drauf kommt :bahnhof:_


----------



## knilch (7. Dez 2013)

Hi,
Frage: Müssen die variablen koerner und summe vom Typ long sein?

Mit double wird der wert von 63 und 64 nicht negativ. Einzig die Anzeige muss dann noch formatiert werden...

ops. war wohl zu spät mit meinem Ansatz...

So kann das "Problem" mit der Ausgabe in exponential- Format umgehen werden:

```
import java.text.DecimalFormat;
import java.text.NumberFormat;


public class ReisKoerner {
	public static void main(String args[]) {
		double koerner=1;
		double summe=0;
		NumberFormat formater =  new DecimalFormat("");  
		System.out.println("Felder       Körner     Summe Körner");
		for(int i=1;i<65;i++){
			summe = summe + koerner;
			koerner += koerner;
			System.out.println(i + "           " + formater.format(koerner) + "          "+formater.format(summe)) ;
		}
	}
}
```


----------



## PHens (7. Dez 2013)

Hey, 
Danke für den weiteren Ansatz  

Ich befürchte nur leider, dass die Umformung des Formats  leider noch nicht behandelt wurde, und so vom Prof als unbekannt vorrausgesetzt wird. (auch wenn der Code so recht verständlich und einfach wirkt)


Themenfluss war halt nach den wirklichen Grundlagen dann Schleifen, for, while, if-else Abfragen, und nun Arrays und Datenstrukturen. Mit weiteren Java Paketen (bis auf eine vom Prof geschriebene Möglichkeit über die Console Eingaben zu tätigen) wurde noch gar nicht gearbeitet.


----------



## nOeX (7. Dez 2013)

Hmm Also bei uns in der Uni ist es so das selbständiges Experimentieren vorausgesetzt ist .
Solange du alles begründen kannst und auch dein Code verstehst wird dir der Prof sicherlich nichts sagen, wäre ja auch ein wenig blöd, so bekommst ja nie das außen rum raus. 

Abgesehen davon wurde ja gesagt bigInt darfst du nicht verwenden und von anderen Datentypen oder Methoden war keine rede .

Machs dir nicht schwerer als es ist, der schwierige Part kommt noch *gl*


----------



## DrZoidberg (7. Dez 2013)

So könnte es gehen


```
public class Koerner {
    final static int maxLaenge = 20;
    
    static int[] plus(int[] z1, int[] z2) {
        int[] ergebnis = new int[maxLaenge];
        int uebertrag = 0;
        for(int i = maxLaenge-1; i >= 0; i--) {
            int ziffer = z1[i] + z2[i] + uebertrag;
            uebertrag = ziffer/10;
            ergebnis[i] = ziffer%10;
        }
        return ergebnis;
    }
    
    static void printZahl(int[] z) {
        for(int i = 0; i < z.length; i++) System.out.print(z[i]);
    }
    
    public static void main(String[] args) {
        int[] koerner = new int[maxLaenge];
        koerner[maxLaenge-1] = 1;
        for(int i = 0; i < 64; i++) {
            koerner = plus(koerner, koerner);
        }
        printZahl(koerner);
    }
}
```


----------



## PHens (8. Dez 2013)

Hi,
danke erstmal an DrZoidberg für die Mühe. Ich bin dabei dein Programm so umzuschreiben, dass in jeder Zeile die Summe der bisher gesammelten Reiskörner ausgegeben wird. Habe den Rechenschritt mit der "Schriftlichen Addition innerhalb des Arrays" raus, und werde das nachher auch nochmal hier zur Schau stellen. 

@nOeX: Ja, ich finde auch, dass man sich bei so einem Thema lieber selbst durch experimentieren EINE von vielen Lösungen aneignen sollte. Schließlich muss man hinterher auch Probleme mit eigenen Methoden lösen. 
Nur leider ist dieser Professor ein arroganter A**e, der sich für den größten Streich der Programmiergeschichte hält. Als ich in der Aufgabenstellung gelesen habe, wofür er alles Punkte abzieht .. unglaublich. Spielraum für Freigeister ist da nicht gelassen, es muss alles so sein, wie er es haben will. 

Vielleicht hat der eine oder andere schonmal ein Buch des hochachtungsvollen Herrn Balzert gelesen, oder eines seiner Programme verwendet. 

Ich selbst habe damals bei einem echt lockeren Prof gehört, in dessen Übung wir darum gebeten wurden unsere eigenen Ideen umzusetzen, deswegen finde ichs auch recht schwer meiner Freundin da zu helfen, und mich an den Plan zu halten. :rtfm:


----------



## PHens (9. Dez 2013)

Falls sich das noch jemand anschauen will, hier ist das Schachbrett - Reiskorn Problem mit "Int Arrays", ohne BigInteger oder double Formatumformung gelöst. Natürlich kommt man mit den beiden anderen Wegen viel schneller, kürzer, verständlicher und vor allem Einfacher ans Ziel. 
Aber solange man den Prof damit glücklich macht  


```
package inout;

public class Schachbrett1
{
    public static void main(){
        int koerner[][]= new int [21][1];
        int summe[][]= new int [21][1];
        int uebertrag[][]= new int [21][1];

        for(int i=0; i<summe.length; i++){
            summe[i][0]= 0;
        }
        for(int i=0; i<koerner.length; i++){
            koerner[i][0]= 0;
        }
        koerner[koerner.length-1][0]=1;
        for(int i=0; i<uebertrag.length; i++){
            uebertrag[i][0]= 0;
        }

        
        anfang(koerner, summe, uebertrag);
        
            zaehler(koerner,koerner, uebertrag);
            zaehler(koerner, summe, uebertrag);

            visualisierung(koerner, summe, i);
        }
    }

    public static void zaehler(int [][] koerner,int [][]summand2, int [][] uebertrag){
        int x=0;
        uebertragsberechner(koerner, summand2, uebertrag);
        for(int k=1;k<koerner.length;k++){
            x=koerner[koerner.length-k][0];
            if((koerner[koerner.length-k][0]+summand2[koerner.length-k][0]+uebertrag[koerner.length-k][0])> 9){
                x=(koerner[koerner.length-k][0]+summand2[koerner.length-k][0]+uebertrag[koerner.length-k][0])%10;
                summand2[koerner.length-k][0]=x;
            }else{
                summand2[koerner.length-k][0]= koerner[koerner.length-k][0]+summand2[koerner.length-k][0]+uebertrag[koerner.length-k][0];
            }
        }

    }

    public static void uebertragsberechner(int [][] koerner,int [][]summand2, int [][] uebertrag){
        int laenge= koerner.length;
        for(int i=0; i<uebertrag.length; i++){
            uebertrag[i][0]= 0;
        }
        for(int l=1; l<koerner.length-1; l++){
            if((koerner[laenge-l][0]+summand2[laenge-l][0]+uebertrag[laenge-l][0])> 9){
                uebertrag[laenge-l-1][0]=1;
            }
        }
    }

    public static void anfang(int koerner[][], int [][] summe, int [][] uebertrag){//Visualisierung
        
        zaehler(koerner, summe, uebertrag);
        System.out.println("");
        System.out.println("Schachfeldzaehler\t\t\t Koerner\t\t\t Summe der Koerner");
        System.out.print("1\t\t\t ");
        for(int i=0;i<koerner.length; i++){
            System.out.print(koerner[i][0]);
        }
        System.out.print("\t\t\t ");
        for(int i=0;i<koerner.length; i++){
            System.out.print(koerner[i][0]);
        }
    }

    public static void visualisierung(int[][]koerner, int [][] summe,int i){
        System.out.println();
        System.out.print(i+"\t\t\t ");
        for(int j=0;j<koerner.length; j++){
            System.out.print(koerner[j][0]);
        }
        System.out.print("\t\t\t ");
        for(int j=0;j<summe.length; j++){
            System.out.print(summe[j][0]);
        }
    }

}
```


Ich hoffe, dass diese Lösung nochmal jemandem bei der Bearbeitung des Problemes hilft. :toll:


----------



## Leroot (1. Feb 2016)

Das Programm läuft bei mir nicht. Ab Zeile: 22 (anfang) zeigt meine IDE den Fehler: "Cannot find symbol" an. Woran liegt das? Was muss ich anpassen? Was ist "package inout;"?


----------



## JStein52 (1. Feb 2016)

In der geposteten "Lösung" sind aber gleich mehrere Fehler drin. Die kompiliert ja noch nicht mal fehlerfrei.
Schau dir das noch mal an !



Leroot hat gesagt.:


> "Cannot find symbol"


Das bezieht sich wohl auf den dritten Parameter der Methode visualisierung(). Dieses i ist an der Stelle nicht bekannt. Und mit den Klammern stimmt auch was nicht. Da ist eine } zuviel.


----------



## kneitzel (1. Feb 2016)

Die "Lösung" ist auch in meinen Augen vom Ansatz her etwas "dubios". Da wird ein zweidimensionales Array definiert, aber die eine Dimension ist 1 und es wird nur das Element 0 verwendet?

Also statt Lösung würde ich dazu eher Anregungen zur Lösungsfindung sagen  Aber ist auch recht lange her, so dass die Frage im Raum steht, in wie weit diese Thematik wirklich noch aktuell behandelt werden sollte.


----------



## JStein52 (1. Feb 2016)

kneitzel hat gesagt.:


> in wie weit diese Thematik wirklich noch aktuell behandelt werden sollte


Ich denke @Leroot wird aktuell dieses Problem ebenfalls bearbeiten und ist auf die Fehler gestoßen.


----------



## Leroot (1. Feb 2016)

kneitzel hat gesagt.:


> Aber ist auch recht lange her, so dass die Frage im Raum steht, in wie weit diese Thematik wirklich noch aktuell behandelt werden sollte.



Die Aufgabe ist nach wie vor aktuell, da sie noch immer in der neuesten Ausgabe des Buches "Java: Der Einstieg in die Programmierung" (Helmut Balzert, 4. Auflage) behandelt wird. In der Aufgabe geht es darum das Addieren innerhalb von Arrays zu begreifen, nur wird dies leider nicht näher erläutert.

Meine Hoffnung war es, dass jemand die gegebene Lösung von PHens aufgreifen, korrigieren und ggf. noch erläutern kann. Ich habe nicht gefragt, in wie weit es Sinn macht "diese Thematik wirklich noch aktuell" zu behandeln. Dennoch Danke für den Einwand @kneitzel.


----------



## JStein52 (1. Feb 2016)

Hast du dir die Loesung weiter oben von DrZoidberg  angesehen ? Meines Erachtens ist die richtig und funktioniert.


----------



## kneitzel (1. Feb 2016)

Also eine Lösung würde ich objektorientiert aufbauen. BigInteger ist nicht erlaubt, daher würde ich eine neue Klasse erstellen. Diese kann man ja BigInteger oder MyBigInteger nennen.

Ich habe das jetzt so verstanden, dass man die Zahl in einem Array speichern soll und jeder Feld genau eine Ziffer der Zahl enthalten soll. Also die Zahl 123 wäre dann in einem Array { 3, 2, 1 } zu speichern.

Und das schöne ist, dass wir jetzt nur die Addition betrachten müssen. Bei der Addition gehe ich dann das Array durch von 0 bis length -1 und addiere die beiden Felder. 
Ist das Übertragflag gesetzt addiere ich noch 1 dazu und lösche das Übertragflag.
Ist der Wert größer 10, dann setze ich das ÜbertragFlag und speichere den Wert - 10 in dem Zielfeld.
Wenn ich durch alle Felder durch bin prüfe ich noch, ob das Übertragflag gesetzt ist. In dem Fall habe ich einen Überlauf gehabt und werfe eine Exception.

Der Code kann dann evtl. so aussehen (Nur als kleiner Anfang):

```
/**
* Storing big Integers
*/
public class MyBigInteger {

    /**
     * How many digits can our big integer hold?
     */
    public static final int MAX_DIGITS = 30;

    /**
     * Our digits
     */
    private short digits[] = new short[MAX_DIGITS];

    /**
     * Add a MyBigInteger to this MyBigInteger.
     * @param summand MyBigInteger instance to add.
     * @return New MyBigInteger instance with result.
     */
    public MyBigInteger add(MyBigInteger summand) {
        MyBigInteger result = new MyBigInteger();

        boolean overrun = false;
        for (int digit = 0; digit < MAX_DIGITS; digit++) {
            result.digits[digit] = (short)(digits[digit] + summand.digits[digit]);
            if (overrun) {
                result.digits[digit]++;
                overrun = false;
            }
            if (result.digits[digit] > 9) {
                result.digits[digit] -= 10;
                overrun = true;
            }
        }
        if (overrun) {
            throw new ArithmeticException("Overrun when adding numbers.");
        }

        return result;
    }

    /**
     * Add an integer to this MyBigInteger.
     * @param number Integer to add.
     * @return New MyBigInteger instance with result.
     */
    public MyBigInteger add(int number) {
        MyBigInteger result = new MyBigInteger();

        boolean overrun = false;
        int digit = 0;
        while (digit < MAX_DIGITS && number > 0) {
            int currentDigit = number % 10;
            number = number / 10;
            result.digits[digit] = (short)(digits[digit] + currentDigit);
            if (overrun) {
                result.digits[digit]++;
                overrun = false;
            }
            if (result.digits[digit] > 9) {
                result.digits[digit] -= 10;
                overrun = true;
            }
            digit++;
        }

        if (overrun) {
            throw new ArithmeticException("Overrun when adding numbers.");
        }

        return result;
    }

    /**
     * String representative of this MyBigInteger instance.
     * @return String that represents this Integer.
     */
    public String toString() {
        StringBuilder result = new StringBuilder();
        for (int digit = MAX_DIGITS -1 ; digit >= 0; digit--) {
            result.append(digits[digit]);
        }
        return result.toString();
    }

    /**
     * Small test of this class - should not be part of this class!
     * @param args Commandline arguments - not used!
     */
    public static void main (String args[]) {
        MyBigInteger number1 = new MyBigInteger();
        number1 = number1.add(123456789);
        System.out.println(number1);

        MyBigInteger number2 = new MyBigInteger();
        number2 = number2.add(9999);
        System.out.println(number2);

        MyBigInteger number3 = number1.add(number2);
        System.out.println(number3);
    }
}
```

Wenn es nicht objerktorientiert sein soll, dann ist es auch so verwendbar. Statt MyBigInteger wird dann halt immer ein Array übergeben und die Funktionen arbeiten dann halt auf Basis der Arrays. Dann sollte aber noch am Anfang immer geprüft werden, ob die Arrays gleich groß sind.

Ist natürlich noch erweiterbar. So kann man Konstruktoren hinzu fügen, die einen Integer oder einen String nehmen und dann wird der entsprechend als Initialisierung verwendet. hashCode und equals müssten auch noch implementiert werden ...

Konrad


----------



## JStein52 (1. Feb 2016)

PHens hat gesagt.:


> Spielraum für Freigeister ist da nicht gelassen, es muss alles so sein, wie er es haben will.


Wir reden von Hrn. Prof. Balzert. Keep it simple. Sonst gibts Punktabzug.
Und vergleiche mal deine Lösung mit der von DrZoidberg. Da kannst du dir schon vorstellen dass du 0 Punkte kriegst.


----------



## Leroot (1. Feb 2016)

Vielen Dank für den zeitnahen Lösungsansatz Konrad. Mir scheint das allerdings etwas zu kompliziert zu werden. Um kurz zu verdeutlichen worum es hier eigentlich nur geht, hier die Aufgabe und der Lösungshinsweis:



> *Aufgabenstellung*
> Der Sage nach war der indische König Shehram vom Schachspiel so begeistert, dass er dem Erfinder Sessa Ebn Daher jeden Wunsch zu erfüllen versprach. Um so überraschter war er, als der Erfinder die bescheidene Bitte äußerte, der König möge ihm so viele Weizenkörner schenken, wie sich zusammen ergeben, wenn man auf das erste der 64 Felder des Schachbretts ein Weizenkorn legt, auf das zweite zwei, auf das dritte vier, auf das vierte acht und so fort, d.h. auf das nächste Feld immer die doppelte Anzahl von Körnern wie auf das vorhergehende.
> *
> Schreiben Sie ein Java-Programm »Schachbrett«, das es ermöglicht, das Problem Schachbrett zu lösen. Das Programm muss in der Lage sein, längere Zahlen zu verarbeiten, als in einer Java-Speicherzelle »long« darstellbar sind (siehe Lösungschablone). Die Anzahl der Körner pro Schachfeld und die jeweilige Summe sollen in einer Tabelle wie folgt ausgegeben werden:*
> ...



Den Lösungsansatz von @DrZoidberg (weiter oben) kann ich leider nicht mit der geforderten Tabelle in Verbindung bringen.


----------



## JStein52 (1. Feb 2016)

wieso nicht ? du musst nur die Ausgabe ein wenig anders gestalten


----------



## kneitzel (1. Feb 2016)

Also Java ist eine objektorientierte Sprache und da ist es in meinen Augen extrem sinnvoll, eben so mit Klassen zu arbeiten. Die erstellte Klasse kann dann auch bei anderen Projekten genutzt werden.

Diese ganzen nicht objektorientierten Lösungen sind in meinen Augen kontraproduktiv. Aber da kommen wir dann zu einer Diskussion a.la. "C lernen, ehe man c++ lernen soll". Aber Java nicht objektorientiert zu nutzen tut schon fast weh ...

Aber zu der Applikation von DrZoidberg: Er gibt nur das Endergebnis aus. Aber das kann man ja gerne noch erweitern:


```
public static void main(String[] args){
       int[] koerner = new int[maxLaenge];
       int[] summe = new int[maxLaenge];
       koerner[maxLaenge-1]=1;
       summe[maxLaenge-1]=1;
       int feld = 1;
       while (feld <= 64) {
            // Ausgabe
            System.out.print(feld);
            System.out.print("\t");
            printzahl(koerner);
            System.out.print("\t");
            printzahl(koerner);
            System.out.println();
            if (feld < 64) {
                // Get values for next field
                koerner = plus(koerner, koerner);
                summe = plus(summe, koerner);
            }
            feld++;
       }
   }
```

Ist jetzt aus dem Kopf geschrieben - das sollte nun die Ausgabe machen. Und dann wird immer neu gerechnet, so lange wir noch nicht beim 64ten Feld sind.


----------



## JStein52 (1. Feb 2016)

Sollte da nicht einmal summe stehen ?

```
printzahl(koerner);
            System.out.print("\t");
            printzahl(koerner);
```


----------



## kneitzel (1. Feb 2016)

Was hat mein Lehrer bei solchen Fehlern immer gesagt? Ich wollte nur prüfen, ob Ihr auch genau lest, was ich da schreibe 

Das schreiben von Code direkt hier im Editor ist etwas blöd - wenn man das nicht erst in der IDE schreibt und dann per copy & paste einfügt, dann kommt sowas ...

Aber klar - am Ende sollte die summe ausgegeben werden.


----------

