Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution:

How I got the formulae

#include <stdio.h>
#include <stdlib.h>

void print_answer(int limit){

    int a = 1; //1st term
    int b = 2; //2nd term
    int even_fibbonaci = 0; //start as zero,because of the loop
    int sum = 2;//sum of even up to 2nd term
    int steps_taken = 0;
    do{
        sum += even_fibbonaci;
        even_fibbonaci = 2*a + 3*b; //even fibbonaci
        a += 2*b; //fibbonaci just before even fibbonaci
        b = even_fibbonaci;
        steps_taken++;
    }while(even_fibbonaci<limit);

    printf("Sum of the even-valued fibbonaci below %d\n",limit);
    printf("Answer = %d, Steps Taken = %d\n",sum,steps_taken);

}

int main(int argc, char ** argv){

    if(argc!=2){
        printf("Invalid number of arguments\n");
        printf("Usage a.exe [limit]\n");
        return -1;
    }

    int limit = atoi(argv[1]);

    if(limit < 3){
        printf("Invalid input\n");
        printf("Enter a limit of 3 or more\n");
        return -1;      
    }

    print_answer(limit);

    return 0;
}

For limit = 4000000

Execute as {executable} [limit]

Sum of the even-valued fibbonaci below 4000000

answer = 4613732, steps taken = 11

Compiler:

Compiler

share|improve this question
    
Spredsheet : here –  JaDogg Aug 11 at 4:33
    
Letting the question breathe, Will accept an answer in a while –  JaDogg Aug 14 at 4:38

1 Answer 1

up vote 12 down vote accepted

I'd suggest a couple of things.

Firstly, this is a typical Euler problem example in that Euler usually provides an example test case. Build that into your code so that you confidently refactor.

Secondly, I recommend separating the algorithm from the reporting of its results; this again supports writing built in tests without generating unwanted output.

Taking this approach, you remove the need for a command line or inputs; just keep adding test cases to the code.

I've also taken the liberty of removing/renaming a and b from the loop, but some may consider your original more readable in this respect. What is worth doing is making sure all your variable names are meaningful.

int sumOfEvenFibonaccis(int limit, int* steps)
{
    int prior = 1; 
    int even_fibbonaci = 2; 
    int sum = 0;//sum of even up to 2nd term
    int steps_taken = 0;
    do{
        sum += even_fibbonaci;
        prior += 2 * even_fibbonaci;
        even_fibbonaci = 2 * prior - even_fibbonaci;         
        steps_taken++;
    } while (even_fibbonaci<limit);
    if (steps != NULL)
        *steps = steps_taken;
    return sum;
}

struct TestCase
{
    int limit;
    int result;
}; 

struct TestCase testCases[] = 
{
    { 89, 2 + 8 + 34 }
};

int numTestCases = sizeof(testCases) / sizeof(testCases[0]);

void runTests()
{
    for (unsigned i = 0; i != numTestCases; ++i)
    {
        int testResult = sumOfEvenFibonaccis(testCases[i].limit, 0);
        int expectedResult = testCases[i].result;
        assert(testResult == expectedResult);
    }
}

int main(int argc, char ** argv)
{

    runTests();

    int steps = 0;
    int result = sumOfEvenFibonaccis(4000000, &steps);
    printf("Result: %d using %d steps", result, steps);

    return 0;
}
share|improve this answer
1  
Should int expectedResult = sumOfEvenFibonaccis(testCases[i].result); be int expectedResult = testCases[i].result;? –  Taemyr Aug 11 at 7:08
    
@Taemyr Yes! Fixed. –  Keith Aug 13 at 0:32
    
    
@200_success. True - I'll bet there are some more C++isms to be found. –  Keith Aug 13 at 1:23
1  
@200_success OK - I admit I'd compiled as C++ to begin with. Redone as C; I need struct TestCase as well. Fixing. –  Keith Aug 13 at 1:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.