피보나치 수열

피보나치 수열: 두수의 합이 바로 뒤의 수가 되는 수의 배열 

 

역사

피보나치 수가 처음 언급된 문헌은 기원전 5세기 인도의 수학자 핑갈라가 쓴 책이다.

유럽에서 피보나치 수를 처음 연구한 것은 레오나르도 피보나치로 토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다. n 번째 달의 토끼 수는

• 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
• 두 달 이상이 된 토끼는 번식 가능하다.
• 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
• 토끼는 죽지 않는다.

따라서 첫 달에는 새로 태어난 토끼 한 쌍이 있고, 두 번째 달에는 그대로 토끼 한 쌍, 세 번째 달부터는 이 토끼 한 쌍이 새끼를 낳게 되어 토끼가 2쌍이 되고, 네 번째 달에는 3쌍, 다섯 번째 달에는 5쌍이 된다. 이때 n번째 달에 a 쌍의 토끼가 있었고, 다음 n+1번째 달에는 새로 태어난 토끼를 포함해 b쌍이 있었다고 하자. 그러면 그다음 n+2 번째 달에는 a+b 쌍의 토끼가 있게 된다. 이는 n번째 달에 살아있던 토끼는 충분한 나이가 되어 새끼를 낳을 수 있지만, 바로 전 달인 n+1번째 달에 막 태어난 토끼는 아직 새끼를 낳을 수 없기 때문이다.

 

항등식

using System;
using System.Text;
 
namespace _05
{
    class Solution1{
        public Solution1(){
            var result = this.Fac(4);
            Console.WriteLine(result);
        }
 
        private int Fac(int n){
            if(n == 1||n == 0) return 1;
            else return n * Fac(n-1);
        }
    }
 
    class Solution2{
        public Solution2(){
            for(int i = 0; i<=10; i++){
                var result = Fibo(i);
                Console.WriteLine(result);
            }
        }
 
        private int Fibo(int n){
            if(n == 0) return 0;
            else if( n == 1) return 1;
            else return Fibo(n -1) + Fibo(n-2);
        }
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            //new Solution1();
            new Solution2();
        }
    }
}