#A03_Fibonacci 수열

목표 : 피보나치 수열을 반복문과 재귀적 방법으로 코딩학고 실행시간 측정하기

 

★ 피보나치 수열이란?

   - 처음 두 항을 1과 1로 한 후, 그 다음 항부터는 바로 앞의 두 개의 항을 더해 만드는 수열

   - 앞의 두 항을 더한 값이 현재의 항이 되는 것

 

 

▶ 재귀함수 알고리즘

<피보니치 수열 재귀함수 알고리즘>

 - if 조건이 함수를 끝내는 조건이 됨

 

 

 

★ 만들고자 하는 프로그램

<만들고자 하는 프로그램>

 

1. 새 프로젝트 만들기

   - [솔루션 위에서 마우스오른쪽 → 추가 → 새 프로젝트 → WPF 앱]을 눌러 새로운 프로젝트 추가

 

2. 디자인하기

   1) 도구상자에서 필요한 도구 추가하기

     - TextBlock * 4 (시간을 나타내기 위해 3개 추가)

     - TextBox * 1

     - Button * 1

     - ListBox * 1

<도구 추가하기>

 

   2) TextBlock

     ㅇ 내용 바꿔주기

       - 바꾸고자 하는 TextBlock을 선택하고 [속성 → 공용 → Text]에서 원하는 text로 바꿔준다

<TextBlock 내용바꾸기>

 

     ㅇ 이름바꿔주기

       - ["Recursive : "클릭 → 속성 → 이름]을 'txtRecusive'로 바꿔준다

       - ["반복문(배열) : "클릭 → 속성 → 이름]을 'txtArray'로 바꿔준다

       - ["반복문(리스트) : "클릭 → 속성 → 이름]을 'txtList'로 바꿔준다

 

 

   3) TextBox

     ㅇ 배열 바꾸기

       - [TextBox 클릭 → 속성 → 레이아웃 → HorizontalContentAlignment → 가운데 정렬 클릭]

<TextBox 배열 바꾸기>

     ㅇ 내용 없애기

       - [TextBox 클릭 → 속성 → 공용 → Text]에 내용을 지워준다

     ㅇ 이름 설정하기

       - [TextBox 클릭 → 속성 → 이름]을 "txtInput"으로 설정한다

 

   4) Button

     - Button을 누르고 [속성 → 공용 → Content]항목을 "계산하기"로 바꿔준다

 

   5) ListBox

      - ListBox를 누르고 [속성 → 이름]을 "lstResult"로 설정한다

 

   6) 원하는 위치에 각 도구들을 위치시킨다

<디자인하기>

 

 

3. 코딩하기

ㅇ "계산하기"를 더블클릭하여 Click 함수 만들기

 

   1) Button위에서 더블클릭하여 코드 창으로 넘어간다

   2) Button_Click 함수를 다음과 같이 작성한다

private void Button_Click(object sender, RoutedEventArgs e)
        {
            lstResult.Items.Clear();

            int n = int.Parse(txtInput.Text);

            // 재귀적 방법
            for (int i = 1; i <= n; i++)
            {
                int item = Fibonacci(i);
                lstResult.Items.Add(i + "항 : " + item);
            }

            // 반복문(배열)
            int[] fibo = new int[50];
            fibo[1] = 1;
            fibo[2] = 1;
            for(int i = 3; i <=n; i++)
            {
                fibo[i] = fibo[i - 1] + fibo[i - 2];
                // lstResult.Items.Add(i + "항 : " + fibo[i]);
            }

            // 반복분(리스트)
            List<int> lstFibo = new List<int>();
            lstFibo.Add(1); // 리스트 공간 만들기, lstFibo[1] = 1;(x) 이렇게 공간을 만들면 안됨.
            lstFibo.Add(1);
            for(int i = 3; i <= n; i++)
            {
                lstFibo.Add(lstFibo[lstFibo.Count - 1] + lstFibo[lstFibo.Count - 2]);
                // lstResult.Items.Add(i + "항 : " + lstFibo[i-1]);
            }
        }

 -> 반복문에서는 '리스트'와 '배열'을 사용할 수 있다

    (배열 : 갯수 정해짐, 속도빠름 / 리스트 : 갯수가 정해져 있지 않음)

 

 -> 리스트 사용법 주의해서 작성해야함!!!

 

 

   3) Fibonacci(i)함수 만들기

     - Fibonacci(i)에 빨간색 밑줄이 생김 → 마우스를 갖다대면 전구모양의 아이콘이 생김 → 전구모양 아이콘 클릭 → 메서드 생성 클릭

 private int Fibonacci(int i)
        {
            if (i == 1 || i == 2)
                return 1;
            else
                return Fibonacci(i - 1) + Fibonacci(i - 2);
        }

 

   4) 실행시간 측정 코드 작성하기

<실행시간 측정 예시 코드>

 -> 지난 포스트와 같이 앞뒤로 주의하여 작성해준다

 

 

ㅇ 재귀함수

	var watch = System.Diagnostics.Stopwatch.StartNew();
            // 재귀적 방법
            for (int i = 1; i <= n; i++)
            {
                int item = Fibonacci(i);
                lstResult.Items.Add(i + "항 : " + item);
            }
            watch.Stop();
            var elapsedTicks = watch.ElapsedTicks;      // 또는 watch.ElapsedMilliseconds
            string result = elapsedTicks + " Ticks = " + elapsedTicks / 10000.0 + " ms";
            txtRecusive.Text = "Recursive : " + result; // 출력

 

 

ㅇ 반복문

<반복문 코드>

 

작성이 완료되었다면 ctrl + F5를 눌러 실행한다.

 

 

 

<실행화면1>

<실행화면2>

<실행화면3>

<실행화면4>

<실행화면5>

 

★ 알 수 있는 것

   - 알고리즘에서 가장 효율적인 것은 "배열"이다

   - 배열로 작성할 수 있다면 가장 효율적인 코드가 될 수 있다

   - 배열의 단점은 크기가 정해져 있다는 것이다(남아도 공간을 차지하고 부족하면 에러 발생)

 

 

★ 알고리즘의 종류

 1. 재귀함수로만 풀 수 있는 문제

 2. 재귀함수로 풀 수 없는 문제

 3. 재귀함수, 반복문으로 모두 풀 수 있는 문제