-
C - Fibonacci HW help :(
I'm supposed to 'Write a program that reads a positive integer n entered by the user and then computes and displays the corresponding Fibonacci number"
Here's what I have so far
Code:
/* This program displays the fibonacci number of the user's input*/
#include "stdafx.h"
#include "simpio.h"
#include "genlib.h"
#include <math.h>
int fibonacci(int num);
int main()
{
int input, fibnum;
printf("Input a positive integer to calculate the fibonacci of: ");
input = GetInteger();
fibnum=fibonacci(input);
printf("f(%d) = %d\n", input, fibnum);
}
int fibonacci(int num)
{
int num1, num2, fibnum, i;
num1 = 0;
num2 = 1;
if (num == 0)
{
return(0);
}
if (num == 1)
{
return(1);
}
i = 1;
while (i != num)
{
fibnum = num1+num2;
num1 = num1+num2;
i+=1;
while (i != num)
{
fibnum = num1+num2;
num2=num1 + num2;
i+=1;
}
}
return(fibnum);
}
It works fine for up to 4, but then at 5 it starts messing up. I've been trying to get it to work for about an hour now (from scratch I mean) and my head hurts O_o Any hints or tips would be appreciated...
-
try this
Code:
int fibonacci(int index) {
if(index == 0)
return 0;
int one = 1;
int two = 1;
for(int i = 0; i < index; i++) {
int cache = two;
two = two + one;
one = cache;
}
return two;
}
havent actually tested
edit: just so i dont have to imagine it, heres the sequence
1 1 2 3 5 8 13 21
-
Tested it, doesn't work. It gives f(1) = 2, f(2) = 3, f(3) = 5. I'll see maybe there's some small bug causing it to mess up...
EDIT: Ah, using a third var gives me an idea, lets see if I can make it work...
EDIT: My idea didn't work :(
EDIT:
Redid it, can't figure out for the life of me why this won't work...
Code:
/* This program displays the fibonacci number of the user's input*/
#include "stdafx.h"
#include "simpio.h"
#include "genlib.h"
#include <math.h>
int fibonacci(int num);
int main()
{
int input, fibnum;
printf("Input a positive integer to calculate the fibonacci of: ");
input = GetInteger();
fibnum=fibonacci(input);
printf("f(%d) = %d\n", input, fibnum);
}
int fibonacci(int num)
{
int num1, num2, num3, fibnum, i;
num1 = 0;
num2 = 1;
if (num == 0)
{
return(0);
}
if (num == 1)
{
return(1);
}
i = 1;
while (i != num)
{
fibnum = num1 + num2;
num1 = num1 + num2;
i+=1;
while(i != num)
{
fibnum = num1 + num2;
num2 = num1 + num2;
i+=1;
}
}
return(fibnum);
}
Ops, nvm that's the same thign as I had in first post -.-
-
Try this, it does work (tested it myself)
Then explain to your teacher why you dynamically allocated memory... :D
Code:
unsigned long int fib(unsigned int num)
{
int i = 1;
unsigned long int value = 0;
unsigned long int* fibarray;
fibarray = (unsigned long int*) calloc(num + 1, sizeof(unsigned long int)); // Potentially create a memory leak
fibarray[0] = 0;
fibarray[1] = 1; // Prime the pump, so to speak
while(i < num)
{
fibarray[i + 1] = fibarray[i] + fibarray[i - 1];
++i;
}
value = fibarray[num];
free(fibarray); // Avoid a memory leak
return value;
}
Here is another version that doesn't use an array. Probably better for this assignment.
Code:
unsigned long int fib(unsigned long int num)
{
unsigned long int first = 0;
unsigned long int second = 1;
unsigned long int third = num;
for(int i = 1; i < num; ++i)
{
third = second + first;
first = second;
second = third;
}
return third;
}
And here is the recursive solution *WARNING* WAY SLOW!
Code:
unsigned long int fib(unsigned long int num)
{
if (num == 0)
return 0;
else if (num == 1)
return 1;
else
return fib(num - 2) + fib(num - 1);
}
Hope that gives you a feel for how to do this.
-
Ops, forgot to post that I solved it :( Sorry you had to do that work :p I ended up doing something like your second method.