Datentyp long ist zu klein...

Dobi

@geruetzel: Yeah, Project Euler.
Lange wird es übrigens nicht mehr dauern, bis da Aufgaben kommen, bei denen du auch mit Zahlen bis 2^64 nicht mehr hinkommst.

geruetzel

@ Shade Of Mine - Danke

@ [Rewind] - Danke dir auch, ja das ist natürlich ein gravierender Denkfehler

geruetzel

wäre es hier besser mit einer do while schleife zu arbeiten?

*Rewind*

Ja, wäre auf jeden Fall eleganter.

geruetzel

edit: unnötiger post

*Rewind*

while ( fibonacci < 4000000) {
        fibonacci = zahl1 + zahl2;

        [...]

    }

Allerdings musst du fibonacci vorher initialisieren (z.B. mit 0).

geruetzel

int main()
{

    int zahl1 = 1;
    int zahl2 = 2;
    long fibonacci = 0;
    long sum = 2; //2 wird in die summe miteinbezogen, in der schleife wird sie aber nicht errechnet, 2 ist gerade

    while ( fibonacci <= 4000000 )
    {
        fibonacci = zahl1 + zahl2;

        if ( fibonacci % 2 == 0 )
        {
            sum = sum + fibonacci;
            cout << fibonacci << endl;
        }

        zahl1 = zahl2;
        zahl2 = fibonacci;

    }

    cout << sum;

    return 0;
}

So sieht der Code jetzt aus

Allerdings wird der zahl sum noch eine Zahl über 4 Mio. hinzugefügt...
Ich sehe den Fehler einfach nicht...

Michael E.

geruetzel schrieb:

Allerdings wird der zahl sum noch eine Zahl über 4 Mio. hinzugefügt...
Ich sehe den Fehler einfach nicht...

Gehe den Code mal Schritt für Schritt durch: Solange fibonacci höchstens 4 Mio. ist, vergrößere fibonacci (wie groß kann fibonacci jetzt sein?) und addiere es zur Summe, falls es gerade ist.

geruetzel

Ups, ich habe gerade bemerkt, dass die über 4 Millionen große Zahl die ausgegebene Summe ist

Michael E.

Dann hast du lediglich Glück, dass die erste Fibonaccizahl > 4 Mio. ungerade ist.

camper

geruetzel schrieb:

Ups, ich habe gerade bemerkt, dass die über 4 Millionen große Zahl die ausgegebene Summe ist

So ein Zufall

Obligatorischer Einwurf: Mathematik! \o/

#include <cmath>
#include <iostream>

double const phi = (1 + std::sqrt(5)) / 2;

int fib(int n) {
  return static_cast<int>(std::pow(phi, n) / std::sqrt(5) + .5);
}

int main(void) {
  int const N = 4000000;
  double const phi = (1 + std::sqrt(5)) / 2;

  int n = static_cast<int>(std::log(std::sqrt(5) * N) / std::log(phi));

  std::cout << n << "te Fib-Zahl (" << fib(n) << ") ist die letzte < " << N << '\n';

  int sum = (fib(n) + fib(n + 1) - 1) / 2;

  std::cout << "Summe der geraden Fib-Zahlen kleiner " << N << ": " << sum << '\n';
}

Beweis:

Definiere S(n) = Summe aller geraden Fibonacci-Zahlen unter den ersten n. Behauptung: S(n) = (f(n) + f(n + 1) - 1) / 2

f(0) = S(0) = (f(0) + f(1) - 1) / 2 = (0 + 1 - 1) / 2 ist trivial.

Induktion:

Sei S(n) = (f(n) + f(n + 1) - 1) / 2 vorausgesetzt, so ist

S(n + 3) = (f(n + 3) + f(n + 4) - 1) / 2

zu zeigen. Da

f(n + 3) = f(n) + 2 * f(n + 1)
f(n + 4) = 2 * f(n) + 3 * f(n + 1)

ist

(f(n + 3) + f(n + 4) - 1) / 2 = (3 * f(n) + 4 * f(n + 1) - 1) / 2 = (2 * f(n) + 4 * f(n)) / 2 + S(n) = f(n) + 2 * f(n) + S(n) = f(n + 3) + S(n) = S(n + 3)

q.e.d.

*Rewind*

seldon schrieb:

Obligatorischer Einwurf: Mathematik! \o/

#include <cmath>
#include <iostream>

double const phi = (1 + std::sqrt(5)) / 2;

int fib(int n) {
  return static_cast<int>(std::pow(phi, n) / std::sqrt(5) + .5);
}

int main(void) {
  int const N = 4000000;
  double const phi = (1 + std::sqrt(5)) / 2;

  int n = static_cast<int>(std::log(std::sqrt(5) * N) / std::log(phi));

  std::cout << n << "te Fib-Zahl (" << fib(n) << ") ist die letzte < " << N << '\n';

  int sum = (fib(n) + fib(n + 1) - 1) / 2;

  std::cout << "Summe der geraden Fib-Zahlen kleiner " << N << ": " << sum << '\n';
}

Ein schöner Ansatz. Ich will nicht überkritisch sein, aber die globale Variable ist überflüssig. Die gibt's ja einzig und allein für die Funktion, die die Variable aber auch als Übergabeparameter bekommen kann, da sie ja nochmals in der main deklariert wird. Sonst

Das ist eine Konstante, keine Variable. Globale Konstanten sind idR unproblematisch. Dass sie in der main nochmal definiert wird, ist ein Versehen.

Allerdings fällt mir grad noch auf, dass das nur funktioniert, wenn n = die Zahl der größten geraden Fibo-Zahl kleiner N ist, und dass ich das nirgendwo prüfe. In diesem Fall ist f(33) gerade, also funktioniert das, aber für andere Grenzen müsste man das noch reincoden.

Das sei als Übungsaufgabe interessierten Lesern vorbehalten.