CODEWITHSUNDEEP
cmath
Amin Abourjaily
Amin Abourjaily

Reputation: 9

Fibonacci Sequence Code

The Fibonacci numbers have a range of interesting uses in Mathematics and Computer Science. For example, suppose that a single mould spores falls onto a loaf of break while someone is making their breakfast one day. Suppose also that 48 hours after a spore is created it is able to clone itself, and create a further fresh one every 24 hours thereafter. Finally suppose also that 48 hours after it is created each new spore also starts cloning a fresh spore everyday.

In general F(n) = F(n-1) + F(n-2).

Write a program that prints out the number of spores present at the end of each day. Stop when the number of spores exceeds ten million. How many days does it take? 

int days, next, first=0, second=1;

printf("Enter the day you want to know how many spores exists on\n");
scanf("%d", &days);

while(next < 10000000) {

    if(days == 1) {
        next = 1;
    }
    else {
        next = first + second;
        first = second;
        second = next;
    }
}
printf("The day %d has %d spores\n", days, next);

So far I've only been able to do this. But it's taking me no where. Can someone else only using while, if and scanf functions ?

Upvotes: 0

Views: 232

Answers (3)

Flying_Banana
Flying_Banana

Reputation: 2910

For a fast algorithm, you can use this to bypass (and probably surprise whoever gave you this problem) the recursive formula once and for all.

F(n) = (pow((1 + sqrt(5))/2, n) - pow((1 - sqrt(5)) / 2, n)) / sqrt(5)

For proof, see http://www.artofproblemsolving.com/wiki/index.php/Binet%27s_Formula

Basically given a limit on F(n), just rearrange the formula to find n. Or just try some values, since this formula gives much faster answers.

Upvotes: 1

Daniel Rudy
Daniel Rudy

Reputation: 1439

The Fibonacci sequence operates as the following:

1 1 2 3 5 8 13 21 34 etc....

So it comes down to the formula of F(n) = F(n-2) + F(n-1). You are missing code to increment days.

Try this:

days = 1;
next = 0;
first = 0;
second = 1;

while(next < 10000000) {
    next = first + second;
    first = second;
    second = next;
    printf("The day %d has %d spores\n", days, next);
    days++;
}

That should generate a proper Fibonacci number sequence. If not, I'll correct it.

EDIT: I also noticed that your printf statement is not inside the while loop. Furthermore, notice how I setup the variables before I entered the loop so as to not require an if statement inside the loop. It's more of a performance issue as the less stuff there is to do inside the loop, the faster it will execute.

Upvotes: 3

Granpasso
Granpasso

Reputation: 15

The problem is that you don't count the days you entered when you are calculating the number of spore. Here is a simple working code.

#include <stdio.h>
#include <stdlib.h>
#define LIMIT 10000000
int main()
{
    int days, next, first=0, second=1, i = 0, current_day = 1;

    printf("Enter the day you want to know how many spores exists on\n");
    scanf("%d", &days);

    while(i < days) {

        if(days == 1) {
            next = 1;
        }
        if(next < LIMIT){
            next = first + second;
            first = second;
            second = next;
            printf("Spores at day %d : %d\n", current_day, next);
            current_day++;
        }
        if(next>= LIMIT)
        {
            printf("You reached the limit of 10.000.000 spores in %d days.\n", current_day);
            break;
        }
        i++;
    }

    return 0;
}

Upvotes: 1

Related Questions