BOJ #1003 Fibonacci

This problem was solved six months ago while solving the problems of Paekjoon Online Judgement Algorithm site.

 

Fibonacci

Fibonacci functions have a very simple structure, which is often mentioned as various properties are discovered. When learning the C/C ++ language, it is often discussed with the Tower of Hanoi to learn the concept of recursive functions.

This question is not a high percentage of correct answers. Maybe it's an initial problem.

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

Fibonacci sequence is slightly different according to the initialization value.

The most common case is when fib (0) = 0 and fib (1) = 1.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

What about the string that is output by this code? Just try a few.

n	output	zero count	one count
0	0	1	0
1	1	0	1
2	10	1	1
3	101	1	2
4	10110	2	3
5	10110101	3	5

 

We can see that the number of zeros and ones that the problem requires is also Fibonacci sequence.

This is the difference between whether the initial value is 0, 1 or 1, 0, because it takes the Fibonacci ignition.

Find the Fibonacci sequence up to n terms, then the nth term is the number of ones, and the n-1th term is the number of zeros.

Please see the source for your reference.

 

//---------------------------------------------------------------------
//	baekjoon #1003 - Fibonacci
//		- by Aubrey Choi
//		- created at 2019-05-17
//---------------------------------------------------------------------
#include <stdio.h>

int main()
{
	int t, n, f[42];
	f[0]=1, f[1]=0;
	for(int i=2;i<=41;i++) f[i]=f[i-1]+f[i-2];
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		printf("%d %d\n", f[n], f[n+1]);
	}
	return 0;
}