[C] Warum Skaliert mein Programm nicht

[Tabletop-Player]

Die Aufgabe ist folgender Massen:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Und das ist mein Ansatz es zu lösen:

Spoiler: 

int main(void) 
{
    int Ergebnis = 0;
    int ZahlZumRechnen;
    
    ZahlZumRechnen = 3;
    while(ZahlZumRechnen < 1000)
    {
          Ergebnis = Ergebnis + ZahlZumRechnen;
          ZahlZumRechnen = ZahlZumRechnen + 3;             
    }
    
    ZahlZumRechnen = 5;
    while(ZahlZumRechnen < 1000)
    {
          Ergebnis = Ergebnis + ZahlZumRechnen;
          ZahlZumRechnen = ZahlZumRechnen + 5;             
    }   
    printf("Die loesung ist %d\n", Ergebnis);
    system("PAUSE");
}

Das Problem ist wenn ich anstelle von 1000 die Zahl 10 nehmen Funktioniert das ganze, mit 1000 allerdings nicht und ich sehe den Fehler einfach nicht und wäre dankbar über einen Tipp, eigentlich sogar lieber als gleich die Lösung.

[flooooorian]

Hmm... schwer dir einen Tipp zu geben ohne alles zu verraten...
Aber ich Versuchs mal:

Was ist mit Zahlen, die 3 UND 5 als Teiler haben?

[mopmopen]

Da ich nun nicht genau weiß, was nicht funktioniert, würde ich einfach mal schätzen, das der Wertebereich von der Variable "Ergebnis" nicht groß genug für diese Berechnung ist.
Weiche einfach mal auf long aus, das dürfte das Problem beheben.

[Tabletop-Player]

Autsch
Ich glaube ich sag schon mal danke flooooorian.

[Finntastisch]

In C ist ein int definiert mit nur -32.767 bis 32.767, du bekommst einen Überlauf in Ergebnis.

Edit: mopmopen war schneller.

[toredo]

Auf einem 16Bit-System schon, jedoch nehme ich an, dass der TS ein 32bit-System oder ein 64Bit-System hat. Der int entspricht jeweils der Bus-Breite.

Der Wertebereich ist daher:
−2.147.483.648 bis 2.147.483.647

Der sollte eigentlich genügen. Das Programm könnte des Weiteren durch das Verwenden von Arithmetische Reihen einiges an Performance gewinnen. Dann ist es egal ob du als Obergrenze 100000 oder 100 eingibst, es dauert dann immer gleich lang/kurz.

mfG

[Tabletop-Player]

Mir ist durchaus bewusst das das was ihr sagt seine Berechtigung hat, ich habe vielleicht auch zu unklar gesagt das es definitiv nicht an der Größe der Variable liegt den das Ergebnis ist so oder so kleiner als 32.767.
Mein Problem war das was flooooorian gesagt hat das beispielsweise 15 ein Vielfaches von 3 und 5 ist, und es deshalb nur einmal dazu gerechnet werden muss. Da es bis 10 aber keine Vielfachen von 3 und 5 hat funktionierte es Dort.

Der fertige Code wäre so:

Spoiler: 

int main(void) 
{
    int Ergebnis = 0;
    int ZahlZumRechnen;
    
    ZahlZumRechnen = 3;
    while(ZahlZumRechnen < 1000)
    {
          Ergebnis = Ergebnis + ZahlZumRechnen;
          ZahlZumRechnen = ZahlZumRechnen + 3;             
    }
    
    ZahlZumRechnen = 5;
    while(ZahlZumRechnen < 1000)
    {
          if(ZahlZumRechnen % 3 != 0)
          {
             Ergebnis = Ergebnis + ZahlZumRechnen;
          }  
          ZahlZumRechnen = ZahlZumRechnen + 5;         
    }   
    printf("Die loesung ist %d\n", Ergebnis);
    system("PAUSE");
}

Aber ich weiss das er noch nicht ganz optimiert ist. Kommt bei Gelegenheit mal nach.

So ich habs nochmal etwas verkürzt. Code mässig.

Spoiler: 

int main(void) 
{
    int Ergebnis = 0;
    int Divided  = 0;
    
    while(Divided  < 1000)
    {
          if(Divided  % 3 == 0 || Divided % 5 == 0)
          {
             Ergebnis = Ergebnis + Divided ;
          }
          Divided++;
    }
            
    printf("Die loesung ist %d\n", Ergebnis);
    system("PAUSE");
}

Ich hab gewusst das es eine Mathematischen weg gibt aber leider versehe ich von vorne bis hinten nicht wie das geht, wenn jemand Lust hat es zu erklären, würde ich Toll finden da es mich Interessiert.

[Finntastisch]

@toredo: in ANSI C ist int halt so definiert, maschinenunabhängig.

@TS:

das Ergebnis ist so oder so kleiner als 32.767

999 + 996 + 993 + 990 + 987 .. da komme ich aber ganz schnell auf > 32.767 - und das sind nur ein paar der 3er Potenzen.

[Finntastisch]

Also ich komme auf 234.168 als Ergebnis..

[Tabletop-Player]

@Finntastisch ich glaub du verwechselst was den ich habe jetzt gerade nach geschaut und festgestellt das du recht hättest allerdings ist das was du meinst ein Short und kein int .
Quelle: http://www.peacesoftware.de/ckurs3.html

Edit: ja 233'168 ist richtig.

[flooooorian]

Aber gern

Zur Performance:
Wenn du nur eine for-schleife von 1 bis 999 machst, brauchst du dich nicht um die doppelten Vielfachen kümmern. Dürfte allerdings von der Performance her ziemlich mies sein, denke der Modulo-Operator braucht recht viel Rechenzeit.
Könntest in deinem Fall mal ausprobieren, ob es sinnvoller ist, jedes Vielfache von 5 darauf zu überprüfen ob es auch ein Vielfaches von 3 ist (so wie du es machst), oder am Ende einfach alle Vielfachen von 15 wieder abzuziehen.

Ansonsten das was toredo gesagt hat. Denke aber, dass es bei deiner Aufgabe eher um das Programmieren als um die Mathematik dahinter gehen sollte, oder?

[Finntastisch]

@Finntastisch ich glaub du verwechselst was den ich habe jetzt gerade nach geschaut und festgestellt das du recht hättest allerdings ist das was du meinst ein Short und kein int .
Quelle: http://www.peacesoftware.de/ckurs3.html

hmm, ich hatte das mal so gelernt. Ist aber auch schon knapp 20 Jahre her

Edit: ja 233'168 ist richtig.

sauber

[Tabletop-Player]

Denke aber, dass es bei deiner Aufgabe eher um das Programmieren als um die Mathematik dahinter gehen sollte, oder?

Eigentlich geht es einerseits um das Richtige Resultat egal wie , und anderer seit mach ich das Freiwillig als geht es Darum möglichst viel zu lernen was mich interessiert. All so wenn jemand den Mathematischen weg verständlich Erklärer kann, nur zu.

[flooooorian]

Im Prinzip geht das in deinem Fall genauso wie bei der Gaußschen Summenformel, die alle aufeinander folgenden Zahlen bis "n" addiert:

Der gute Herr Gauß hat da einfach festgestellt, dass sich bei jeder dieser Folgen (Zahlen von 1 bis 1000 z.B.) immer Paare bilden lassen, die die gleiche Summe ergeben:
1+1000 = 1001, 2+999 = 1001, 3+998... Du wirst das Prinzip verstanden haben
Dann muss man sich noch überlegen, wie viele dieser Summanden es gibt, nämlich 1000/2=500.

Das gleiche kannst du mit etwas überlegen einfach auf andere, also auch deine Folgen übertragen. Somit kannst du eine komplette Summe in einer simplen Rechnung berechnen, ohne irgendwelche Schleifen. Ist natürlich mit großem Abstand der performanteste Weg

[toredo]

Da flooooorian die mathematische Grundlage so schön erklärt hat habe ich gleich mal dazu nen einfachen Code geschrieben.

Ein halbwegs guter Compiler sollte den, so wie er hiersteht, eigentlich direkt so optimieren, dass zur Laufzeit keine Berechnungen mehr durchgeführt werden müssen:

#include <stdio.h>

/*
  s = Start
  d = Differenz
  n = Anzahl Elemente
*/
#define ARITH_REIHE(s, d, n)                    ((int)(((n) + 1) * ((s) + (d) * (double)(n) / 2)))

/*
  t = Max
  n = Differenz/Zahl
*/
#define ELEMENT_SUM(t, n)                       ARITH_REIHE(0, (n), ((t) - 1) / (n))

int main(int argc, char **argv) {
        int max = 1000;
        int d1 = 5;
        int d2 = 3;

        /* Summe von allen 3'er plus Summe von allen 5'er minus die Summe aller 15'er, da die sonst doppelt gezählt werden. */
        printf("%d\n", ELEMENT_SUM(max, d1) + ELEMENT_SUM(max, d2) - ELEMENT_SUM(max, d1 * d2));
        return 0;
} 

mfG

[Mikeatweb]

edit

Hatte einen Denkfehler.