Problem mit Schleife



  • Hey,

    wir haben folgende Hausaufgabe aufbekommen :

    1. Der indische König Schehram verlangte, dass Sessa, der Erfinder des Schach-
      spiels, sich eine Belohnung wählen solle. Dieser erbat sich die Summe
      Weizenkörner, die sich ergibt, wenn für das 1. Feld des Schachbrettes 1 Korn,
      für das 2. Feld 2 Körner, für das 3. Feld 4 Körner usw. gerechnet werden.
      a) Schreiben Sie ein Programm, das für alle 64 Felder die Gesamtsumme der Körner
      berechnet.
      b) Geben Sie auch das Gewicht der Körner an, wenn 200 Körner 1 g wiegen.
      c) Errechnen Sie im Programm, wie viele Eisenbahnwaggons man zum Transport des
      Reises bräuchte und wie lang der Zug wäre, wenn ein Eisenbahnwaggon 30 t
      fasst und 15 m lang ist.

    Und der will bei mir einfach nur die Anzahl der Reiskörner ausrechnen. Hier ist mein Versuch :

    #include <iostream>
    using namespace std;
    
    int main () {
    
      long long int reiskorn = 1;
      short int felder;
    
      do {
        reiskorn = reiskorn * 2;  
        felder = felder + 1;
      } while (felder != 63);
    
      cout << reiskorn ;
      system("PAUSE");
    }
    


  • Du solltest auch irgendwo felder einen Wert zuweisen.



  • Naja dann kommt da eine negative Zahl raus was eigentlich nicht sein kann.


  • Mod

    Was ist bei dir denn sizeof(long long int) ? Wenn das 8 ist, solltest du unsigned long long int nehmen. Wenn es weniger als 8 ist, hast du ein Problem.



  • Wenn ich das richtig sehe, addierst du ja auch nirgends die Anzahlen der einzelnen Felder. Alles was du tust ist, wenn ich es einfach ausdrücke, in einer Schleife 2^x mit x++ in jedem Durchlauf zu rechnen. Du willst aber die Summe, also musst du die einzelnen Produkte noch addieren.

    BTW du hast meinen Vorredner nicht richtig verstanden. Mit short int felder; hat "felder" nicht zwingend den Wert 0! Es ist halt noch mit keinem Wert belegt. Probiere am besten mal eine for-Schleife. Die ist viel einfacher 😉



  • Da braucht man kein Programm für. Die Gesamtsumme der Reiskörner auf den ersten n Feldern ist 2^n - 1, der Beweis dafür ist induktiv trivial:

    Def. S(n + 1) = S(n) + 2^n, S(1) = 1

    Für n = 1 gilt S(n) = 1 = 2^1 - 1.
    S(n) = 2^n - 1 => S(n + 1) = S(n) + 2^n = 2^n - 1 + 2^n = 2 * 2^n - 1 = 2^(n+1) - 1 q.e.d.

    Für 64 Felder bedeutet das 2^64 - 1, und das kriegst du in einen vorzeichenbehafteten 64-bit-Integer nicht rein. Benutz unsigned long long.

    @SeppJ: Der C-Standard verlangt, dass long long mindestens den Wertebereich eines 64-bit-Integers aufnehmen kann (C99 5.2.4.2.1). Das ist zwar für C++ streng genommen nicht bindend, aber es sollte mich doch sehr wundern, wenn ein C++-Compiler, der long long unterstützt, diese Regel bräche.



  • SeppJ schrieb:

    Was ist bei dir denn sizeof(long long int) ? Wenn das 8 ist, solltest du unsigned long long int nehmen. Wenn es weniger als 8 ist, hast du ein Problem.

    Im Notfall gibt es ja noch double. Nur typischerweise kann bei so riesigen Zahlen nicht mehr exakt gerechnet werden. Aber der Fehler sollte hier nicht wirklich ins gewicht Fallen. Ob man hier drei Milliarden Eisenbahnwagons oder drei Milliarden und einen benötigt... 😉


  • Mod

    Ja, war zu faul, nachzugucken, was die Mindestgröße von long long ist. Bei negativem Ergebnis lag ein Überlauf nahe. Und tut es immer noch: 2^64-1 passt nicht mehr in signed long long, wenn dieser nur die Mindestlänge hat. Bei unsigned long long würde es genau passen.

    Und double wäre eher unschön, da double precission normalerweise eine 53 Bit Mantisse bedeutet, wo das erst recht nicht (genau) reinpasst.



  • Also zusammengefasst:

    #include <iostream>
    using namespace std;
    
    int main () {
    
      long long int reiskorn = 1; // Zahlenbereich anpassen
      short int felder; // felder -> initialisieren
    
      do {
        reiskorn = reiskorn * 2; // das ist ein Korn zu viel -> korrigieren
        felder = felder + 1;
      } while (felder != 63); // wie viele Felder hat ein Schachspiel?
    
      cout << reiskorn ;
      system("PAUSE");
    }
    

    Der gcc 4.4.? gibt eine Warnung long long ist noch nicht genormt.
    Das Ergebnis zeigt aber keine Auffälligkeiten.



  • Auf meinem System unterscheidet sich die Zahl der Kilometer beim Vergleich unsigned long long und double um eins.
    Es ist zwar ein Fehler, aber dennoch mMn vernachlässigbar.


  • Mod

    Vicious Falcon schrieb:

    Auf meinem System unterscheidet sich die Zahl der Kilometer beim Vergleich unsigned long long und double um eins.
    Es ist zwar ein Fehler, aber dennoch mMn vernachlässigbar.

    Wie hast du das gemessen? Das mag ich irgendwie nicht glauben.



  • Zwei Aufrufe einer Templatefunktion, ich hatte aber /=15 statt *=15 geschrieben. Da lag die Differenz der Kilometer bei 1.

    Es ist mir aber gerade erst aufgefallen, als ich meinen Code anhand der Aufgabenstellung noch einmal kontrolliert habe.


  • Mod

    Vicious Falcon schrieb:

    Zwei Aufrufe einer Templatefunktion, ich hatte aber /=15 statt *=15 geschrieben. Da lag die Differenz der Kilometer bei 1.

    Es ist mir aber gerade erst aufgefallen, als ich meinen Code anhand der Aufgabenstellung noch einmal kontrolliert habe.

    Beim ersten Mal habe ich ja noch gedacht, dass du versehentlich "Kilometer" statt Körner geschrieben hättest, aber nun bin ich komplett verwirrt.



  • Vicious Falcon bezieht sich wohl auf die Länge des Zuges(letze Teilaufgabe).
    Die Abweichung der Körneranzahl bei int zu double beträgt 385. Dabei wurde der double-wert aufgerundet.



  • Wieso, die Reihenfolge ist doch

    Körner -> Gramm -> Tonnen -> Wagen -> Länge (m) -> Länge (km)
    

    Zwischen Wagen und Länge (m) hat sich der Fehler eingeschlichen.



  • do {
        reiskorn = reiskorn * 2;  
        felder = felder + 1;
      } while (felder != 63);
    

    Auch wenn die Anzahl der Multiplikationen *2 stimmen mag (63), berechnet es die Anzahl der Reiskörner auf dem aktuellen Feld. Das dürfte von der Gesamtsumme ein wenig abweichen und somit den armen Fahrdienstleiter dann doch etwas ins Schwitzen bringen...

    Wenn man das Ganze mal binär und "von Hand" betrachtet, ist das recht einfach zu verstehen (entspricht in etwa der bereits genannten Formel):

    1. Feld:          1 Reiskorn
    2. Feld:         10
    3. Feld:        100
    ...
    -------------------
    Summe  ...111111111
    

    Da bei jeder Multiplikation *2 im Prinzip ja nur ein Bitshift der 1 stattfindet, ist leicht ersichtlich, dass die 1 nach 63 Bitshifts, also auf dem 64. Feld, im obersten Bit des unsigned long long angekommen ist. Jetzt müssen nur eben alle Bits addiert werden. Sollte die schöne Zahl 0xFFFFFFFFFFFFFFFF ergeben.

    Ergänzung: Wenn man tatsächlich ein 2^64 -1 versucht, wird klar, dass 2^64 = 0 ergibt (zumindest wenn unsigned long long 64 Bit groß ist.). Das Ergebnis ist dann als unsigned ausgedrückt -1 bzw. als signed die genannte Zahl. Die -1 rettet alles...

    Edit: ein paarmal die 63 und 64 verwechselt...


Anmelden zum Antworten