Schachbrettproblem

wolli123

Mitglied
Ahoi,
ich muss für die Uni das sog. Schachbrettproblem lösen, habe auch bereits ein Programm geschrieben.
Nun habe ich jedoch ein Syntax-Fehler drin, den ich selber nicht beheben kann, kann mir jemand helfen diesen zu beheben bzw. die Fehlerquelle ausfindig zu machen ?

Hier eine kurze Zusammenfassung des Problems und der Aufgabenstellung:
Auf jedes Feld des Schachbretts wird ein Reiskorn gelegt und pro weiteres Feld wird die vorherige Zahl verdoppelt.

"Schreiben Sie ein Programm Schachbrett, das es ermöglicht, die Anzahl der Körner zu berechnen, die der Erfinder erhalten würde. Das Programm muss in der Lage sein, sehr lange Ganzzahlen zu verarbeiten."

Man darf kein BigInteger benutzen.

Mein Programmcode sieht wiefolgt aus :

Java:
import inout.*;
import java.util.Arrays;

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]);
        }
    }
}
 

Androbin

Bekanntes Mitglied
1. Fehler - Zeil 1: "import inout.*;" - Package "inout" kann nicht gefunden werden
2. Fehler - Zeil 29: "visualisierung(koerner, summe, i);" - Variable "i" kann nicht gefunden werden
 

minzee

Bekanntes Mitglied
Ich kenn in Verbindung mit dem Schachbrett nur das 8-Damen-Problem. Worum geht es bei deiner Aufgabe denn eigentlich wirklich? Stellen sich Rundungsfehler ein, wenn man einfach immer nur * 2 rechnen würde?

1. Fehler - Zeil 1: "import inout.*;" - Package "inout" kann nicht gefunden werden
Ich vermute, das ist wieder so ein typischen UNI-Framework. UNI Stuttgart?
 
Zuletzt bearbeitet:

stg

Top Contributor
Mein Vorschlag:

Java:
public class Schachbrett {  
  public static void main(String ... args){
    for(int i=1; i<=64; i++)
    a(i);
  }
  public static void a(int no) {
    Long l = (1l << no) - (no>63 ? 2:1);
    System.out.println(Long.toUnsignedString(l,10));
  }
}

Ausgabe:
Code:
1
3
7
15
31
63
127
255
511
1023
2047
4095
8191
16383
32767
65535
131071
262143
524287
1048575
2097151
4194303
8388607
16777215
33554431
67108863
134217727
268435455
536870911
1073741823
2147483647
4294967295
8589934591
17179869183
34359738367
68719476735
137438953471
274877906943
549755813887
1099511627775
2199023255551
4398046511103
8796093022207
17592186044415
35184372088831
70368744177663
140737488355327
281474976710655
562949953421311
1125899906842623
2251799813685247
4503599627370495
9007199254740991
18014398509481983
36028797018963967
72057594037927935
144115188075855871
288230376151711743
576460752303423487
1152921504606846975
2305843009213693951
4611686018427387903
9223372036854775807
18446744073709551615
 

wolli123

Mitglied
ok, das verkürzt meinen code um einiges..., danke schonmal für diese praktische antwort.
der code von stg ist nur die summe der koerner.
ich soll tabellarisch anzeigen lassen :
feld 1
koerner 1
summe 1

feld 2
koerner 2
summe 3

feld 3
koerner 4
summe 7

usw.

das problem bei meinem anfänglichen quellcode ist die variable i bei der "visualisierung", wie kann ich das fixen, ich denke dann sollte das eig auch funktionieren
 
Zuletzt bearbeitet:

stg

Top Contributor
Na, da kannst du obigen Code doch leicht anpassen...

Java:
public class Schachbrett {
  public static void main(String ... args){
   for(int i=1; i<=64; i++)
    a(i);
  }
  public static void a(int no) {
   System.out.println("Feld: "+no);
   System.out.println("Koerner: "+Long.toUnsignedString((1l << no-1),10));
   System.out.println("Summe: "+Long.toUnsignedString((1l << no) - (no>63 ? 2:1),10));
 }
}

Ausgabe:

Code:
Feld: 1
Koerner: 1
Summe: 1
Feld: 2
Koerner: 2
Summe: 3
Feld: 3
Koerner: 4
Summe: 7
Feld: 4
Koerner: 8
Summe: 15
Feld: 5
Koerner: 16
Summe: 31
Feld: 6
Koerner: 32
Summe: 63
Feld: 7
Koerner: 64
Summe: 127
Feld: 8
Koerner: 128
Summe: 255
Feld: 9
Koerner: 256
Summe: 511
Feld: 10
Koerner: 512
Summe: 1023
Feld: 11
Koerner: 1024
Summe: 2047
Feld: 12
Koerner: 2048
Summe: 4095
Feld: 13
Koerner: 4096
Summe: 8191
Feld: 14
Koerner: 8192
Summe: 16383
Feld: 15
Koerner: 16384
Summe: 32767
Feld: 16
Koerner: 32768
Summe: 65535
Feld: 17
Koerner: 65536
Summe: 131071
Feld: 18
Koerner: 131072
Summe: 262143
Feld: 19
Koerner: 262144
Summe: 524287
Feld: 20
Koerner: 524288
Summe: 1048575
Feld: 21
Koerner: 1048576
Summe: 2097151
Feld: 22
Koerner: 2097152
Summe: 4194303
Feld: 23
Koerner: 4194304
Summe: 8388607
Feld: 24
Koerner: 8388608
Summe: 16777215
Feld: 25
Koerner: 16777216
Summe: 33554431
Feld: 26
Koerner: 33554432
Summe: 67108863
Feld: 27
Koerner: 67108864
Summe: 134217727
Feld: 28
Koerner: 134217728
Summe: 268435455
Feld: 29
Koerner: 268435456
Summe: 536870911
Feld: 30
Koerner: 536870912
Summe: 1073741823
Feld: 31
Koerner: 1073741824
Summe: 2147483647
Feld: 32
Koerner: 2147483648
Summe: 4294967295
Feld: 33
Koerner: 4294967296
Summe: 8589934591
Feld: 34
Koerner: 8589934592
Summe: 17179869183
Feld: 35
Koerner: 17179869184
Summe: 34359738367
Feld: 36
Koerner: 34359738368
Summe: 68719476735
Feld: 37
Koerner: 68719476736
Summe: 137438953471
Feld: 38
Koerner: 137438953472
Summe: 274877906943
Feld: 39
Koerner: 274877906944
Summe: 549755813887
Feld: 40
Koerner: 549755813888
Summe: 1099511627775
Feld: 41
Koerner: 1099511627776
Summe: 2199023255551
Feld: 42
Koerner: 2199023255552
Summe: 4398046511103
Feld: 43
Koerner: 4398046511104
Summe: 8796093022207
Feld: 44
Koerner: 8796093022208
Summe: 17592186044415
Feld: 45
Koerner: 17592186044416
Summe: 35184372088831
Feld: 46
Koerner: 35184372088832
Summe: 70368744177663
Feld: 47
Koerner: 70368744177664
Summe: 140737488355327
Feld: 48
Koerner: 140737488355328
Summe: 281474976710655
Feld: 49
Koerner: 281474976710656
Summe: 562949953421311
Feld: 50
Koerner: 562949953421312
Summe: 1125899906842623
Feld: 51
Koerner: 1125899906842624
Summe: 2251799813685247
Feld: 52
Koerner: 2251799813685248
Summe: 4503599627370495
Feld: 53
Koerner: 4503599627370496
Summe: 9007199254740991
Feld: 54
Koerner: 9007199254740992
Summe: 18014398509481983
Feld: 55
Koerner: 18014398509481984
Summe: 36028797018963967
Feld: 56
Koerner: 36028797018963968
Summe: 72057594037927935
Feld: 57
Koerner: 72057594037927936
Summe: 144115188075855871
Feld: 58
Koerner: 144115188075855872
Summe: 288230376151711743
Feld: 59
Koerner: 288230376151711744
Summe: 576460752303423487
Feld: 60
Koerner: 576460752303423488
Summe: 1152921504606846975
Feld: 61
Koerner: 1152921504606846976
Summe: 2305843009213693951
Feld: 62
Koerner: 2305843009213693952
Summe: 4611686018427387903
Feld: 63
Koerner: 4611686018427387904
Summe: 9223372036854775807
Feld: 64
Koerner: 9223372036854775808
Summe: 18446744073709551615
 

wolli123

Mitglied
@stg
eine frage hätte ich da noch, was bedeutet
Java:
(1l << no)
?
ganz explizit das <<
 
Zuletzt bearbeitet:

stg

Top Contributor
Bit-shift der 1 um "no" (number) viele stellen. Hier werden also einfach nur Potenzen von 2 ausgerechnet.

Beispiel:
aus: 1 << 3 wird zu 8 (2 hoch 3)
Warum?
Schauen wir uns die eins binär an:
...000001
dann bitshift um 3 stellen:
...001000 (was der 8 entspricht)
 

lucien

Mitglied
Sag mal fehlen bei der for-Schleife nicht die Syntaxklammern? Oder geht das, weil es nur ein Befehl ist? Ich persönlich hätte es so gemacht:
Java:
public class Schachbrett
{
    
    int x=0;
    int y;
    int z;
    public Schachbrett()
    {
       
        while(x<65){
           y=2^x;
           z=z+y;
           System.out.println("Feld: "+(x+1));
           System.out.println("Körner: "+y);
           System.out.println("Summe: "+z);
           x++;
     }
    }
}

kommt das selbe bei rum ist aber nicht so kompliziert.
 

lucien

Mitglied
Ich war mir nicht sicher ob das geht. Der Code funktioniert und es kommt die selbe Ausgabe also kommt das selbe bei rum. Was soll daran falsch sein?
 

stg

Top Contributor
Ich war mir nicht sicher ob das geht. Der Code funktioniert und es kommt die selbe Ausgabe also kommt das selbe bei rum. Was soll daran falsch sein?

Es kommt nicht die selbe Ausgabe, behaupte doch nicht so einen Mist.
Hättest du den Code auch nur ein einziges Mal ausgeführt, so wüsstest du das.

Lt. Java Standard: Primitive Datentypen geht der Datentyp long nur bis:
9.223.372.036.854.775.807

Bei euch geht es aber bis:
18.446.744.073.709.551.615

Wie ist denn das möglich?

Das verrät ein Blick in die Java API, wenn man sich dort die verwendete Methode toUnsignedString anschaut.
https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html
Ein long in Java hat 64bit, interpretiert man die Zahl als unsigned Ganzzahl, so ist die größte Zahl, die man darstellen kann nunmal 2^64-1 = 18.446.744.073.709.551.615, passt also ganz genau.
 

minzee

Bekanntes Mitglied
Dann funktioniert dieser unsigned-Trick nur, weil mit dem << gearbeitet wird, richtig? Und mit einem * 2 funktioniert das dann gar nicht, weil ein Überlauf entsteht, stimmts?

Und weil man auf diesen << - Trick kommen muss, nennt das die Uni das "Schachbrettproblem"?

Auch wenn das Problem hier echt elegant gelöst wurde, habe ich dennoch das Gefühl, dass sich die Uni ein etwas anderes Programm erwartet. Wenn es die Anforderung gibt, dass kein BigInteger verwendet werden darf, wollte die Uni wohl ganz bewusst einen Überlauf bei den Berechnungen provozieren.
 
Zuletzt bearbeitet:

stg

Top Contributor
Dann funktioniert dieser unsigned-Trick nur, weil mit dem << gearbeitet wird, richtig? Und mit einem * 2 funktioniert das dann gar nicht, weil ein Überlauf entsteht, stimmts?
Da entsteht so oder so ein Überlauf, man muss nur wissen, wie man damit umzugehen hat. Wenn es dich interessiert, dann geh doch mal mit nem Debugger durch den Code und lass dir die Zwischenzustände alle ausgeben.

Und weil man auf diesen << - Trick kommen muss, nennt das die Uni das "Schachbrettproblem"?

Nö, das eine hat mit dem anderen nix zu tun. Das "Problem" ist einfach schon Uralt. Siehe z.B. hier: Sissa ibn Dahir

Auch wenn das Problem hier echt elegant gelöst wurde, habe ich dennoch das Gefühl, dass sich die Uni ein etwas anderes Programm erwartet. Wenn es die Anforderung gibt, dass kein BigInteger verwendet werden darf, wollte die Uni wohl ganz bewusst einen Überlauf bei den Berechnungen provozieren.

Was der Aufgabensteller beabsichtigte, wird man wohl nur mit Sicherheit erfahren, wenn man ihn persönlich fragt :)

Und weil man auf diesen << - Trick kommen muss,

Weder ist das ein Trick, noch muss man es verwenden. Das ist einfach die mMn bequemste und zudem eine sehr effiziente Möglichkeit, um Potenzen von 2 zu berechnen.
 
Zuletzt bearbeitet:


Schreibe deine Antwort... und nutze den </> Button, wenn du Code posten möchtest...

Neue Themen


Oben