[C++/Python] 프로젝트 오일러 #57 : 제곱근의 수렴

이번 문제는 수학 문제인 듯 보이지만, 그냥 단순 계산 문제입니다.

프로젝트 오일러 사이트 난이도 평가 5% 문제네요.

 

 

문제의 내용은 2의 제곱근을 구할 때, 연분수 전개를 할 수가 있습니다.  연분수 전개에 관련해서는 펠의 방정식(http://sdev.tistory.com/213) 글을 참조하세요.

 

$$\sqrt{2}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\cdots }}}=[1;\bar{2}]$$

 

와 같이 2의 제곱근을 표시할 수 있습니다.

 

이 문제에서는 이것이 중요한 것이 아니고, 이 연분수 전개를 할 때, 분수로 표현하게 되면, 분모와 분자가 모두 정수가 되는데, 분자의 정수부가 분보의 정수부보다 자릿수가 많은 것이 몇개가 있는 가가 문제입니다.

 

연분수 전개를 분수로 만들면 되는 것이지만, 연분수 전개 자체가 상당히 큰 자릿수가 나옵니다.  물론 double 형을 이용해서 근사치로 계산해도 되겠지만, 실제 double을 이용해서 계산하면, 이 문제의 답이 틀려지게 됩니다.  그만큼 예민해서, 어쩔 수 없이 BigInt를 이용해서 풀어야 합니다.

 

Pell's equation

 

BigInt를 이용해서 푸는 것은 사실 C/C++ 언어보다는 Python과 같이 BigInt 라이브러리가 기본 제공되는 것을 이용하는 것이 편합니다.

 

저는 제가 직접 만든 BigInt 구조체를 이용해서 사용했어요.  

 

//------------------------------------------------
//    Project Euler #57 - Square Root Convergents
//        - by Aubrey Choi
//        - created at 2015-09-24
//------------------------------------------------
#include <stdio.h>
#include <time.h>

struct BigInt
{
    BigInt() { len = 0; }
    BigInt(int m)
    {
        len = 0;
        while(m)
        {
            v[len++] = m%10;
            m /= 10;
        }
    }
    void mul2add(BigInt &a)
    {
        int c = 0;
        for(int i = 0; i < len; i++)
        {
            c += v[i]*2 + ((i < a.len)?a.v[i]:0);
            v[i] = c%10;
            c /= 10;
        }
        while(c)
        {
            v[len++] = c%10;
            c /= 10;
        }
    }
    int len;
    char v[1024];
};

void solve1()
{
    BigInt d = 2, n = 3, d1 = 1, n1 = 1;
    int count = 0;
    for( int i = 2 ; i <= 1000 ; i++ )
    {
        BigInt t;
        t = d; d.mul2add(d1); d1 = t;
        t = n; n.mul2add(n1); n1 = t;
        if( n.len > d.len ) count++;
    }
    printf("Ans = %d\n", count);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}

 

python에 비해서 C/C++로 제가 효율이 그렇게 훌륭하다고 생각치는 않지만, 2~3배 빠르게 수행이 되었습니다.  인터넷에서 BigInt 라이브러리를 찾으셔서 C/C++에 적용해도 되고요.  

 

알고리즘 자체는 그다지 어렵지는 않습니다.

#------------------------------------------------------------
#    Project Euler #57 - Square Root Convergents
#    Author: Aubrey Choi
#    Date:    2015.09.24.
#------------------------------------------------------------
d, n, d1, n1 = 2, 3, 1, 1
count = 0
for i in range(2, 1001):
    d, d1 = 2*d+d1, d
    n, n1 = 2*n+n1, n
    if len(str(n)) > len(str(d)): count += 1
print(f"Ans = {count}")