Write code that returns the __nth Fibonacci number. __
--If the argument is less than 0, -1 is returned. --Implement recursively. --The function should take the following form - int fibo(int index);
int fibo(int index)
{
if(index < 0) return -1;
if(index == 0) return 0;
if(index == 1) return 1;
if(index > 46) return 0;
return fibo(index - 1) + fibo(index -2);
}
int fibo(int index)
{
if (index < 0)
return (-1);
if (index == 0)
return (0);
if (index == 1)
return (1);
if (index > 46)
return (0);
return fibo(index - 1) + fibo(index - 2);
}
#include <stdio.h>
int main()
{
int i = 1;
int x = 0;
for(x = -3; x < 50; x++){
i = fibo(x);
printf("%Fibonacci number of d:%d\n",x,i);
}
return (0);
}
--At first, the code did not consider the maximum value of int type. You should always be aware of the maximum value of int. --I wanted to use memoized recursion, but I couldn't use it because the shape of the function was fixed. ――I was surprised because the speed was so different when I tried to implement it with memoization recursion.
--Things to consider in the test case --Behavior for negative numbers --Behavior when 0,1 --46 Behavior around
int fibo(int index, int a[])
{
if(index < 0) return -1;
if(index == 0) return 0;
if(index == 1) return 1;
if(index > 46) return 0;
if(a[index] != 0) return a[index];
return a[index] = fibo(index - 1, a) + fibo(index -2, a);
}
2020/04/14 I came back because I solved a similar problem for the first time in a month. I tried to write it, but it doesn't work. In the memoization recursion part, static was not added. Last time, I didn't understand it properly. By adding static, the value is retained in the static area and the calculation result is inherited. I didn't understand here. Review is important.
//Important here!
static int A[46 + 1] = {0, 1};
#include <stdio.h>
int fibo(int n)
{
static int A[46 + 1] = {0, 1};
if (n < 0)
return -1;
if (n > 46)
return 0;
if (n >= 2 && A[n] == 0)
A[n] = fibo(n - 1) + fibo(n - 2);
return A[n];
}
int main(void)
{
int N;
scanf("%d", &N);
printf("%d\n", fibo(N));
return 0;
}
Recommended Posts