[책-알고리즘퍼즐68]11.피보나치

문제

 피보나치 수열 중 각 자리의 숫자를 더한 수로 나누어 떨어지는 수를 다음 예에 이어 작은 쪽부터 5개 구해보세요.

 예)

   2 > 2/2

   3 > 3/3

   5 > 5/5

   8 > 8/8

   13 > 13/4  x

   21 > 21/3

   144 > 144/9

 

난이도

IQ 85

 

목표시간

20분

 

풀이(c#,VS)

1. 

using System;

namespace _11_Fibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            long num1 = 1;
            long num2 = 2;
            for(long i =0; i<1000; i++)
            {
                //피보나치 수 구하기
                long pbNum;
                pbNum = num1 + num2;

                num1 = num2;
                num2 = pbNum;

                //자릿수 구하기
                long tempPbNum = pbNum;
                long sumNumLen = 0;
                do
                {
                    sumNumLen+= (long)(tempPbNum % 10);
                    tempPbNum = (long)(tempPbNum / 10);
                } while (tempPbNum > 0);
                   
                //자릿수 합으로 나누었을때 떨어지는 숫자 구하기
                if(pbNum%sumNumLen == 0f)
                {
                    Console.WriteLine(pbNum + "/" + sumNumLen);
                }

                
            }
        }
    }
}

 

문제정답(사용언어:python)

 

1.

a=b=1
count = 0
while count<11:
    c = a+b
    # 1자리씩으로 분할하여 각 자리의 합을 취득
    sum =0
    for e in str(c):
        sum +=int(e)
    if c%sum == 0:
        #나누어 떨어지면 출력
        print(c)
        count += 1
    a,b,=b,c

 

-

재귀를 이용해서 문제를 풀지 않았지만 책에서는 재귀를 이용하면 자칫 stackoverflow에 빠질 수 있다고 한다. 재귀가 끝나는 시점까지 호출 메소드관련 메모리가 스택에 계속 살아 있어야 되기 때문인것 같다. 간단하고 작은 수를 다룰 때는 재귀 나름의 장점이 있지면 역시 재귀는 쓰기전에 고려해볼 점이 많은것 같다.