[C/C++] 프로젝트 오일러 #104 Pandigital Fibonacci Ends(단순반복)

프로젝트 오일러 문제 #104: Pandigital Fibonacci Ends는 피보나치 수열의 특성과 판디지털(pandigital) 숫자의 개념을 결합한 문제입니다.

문제 요약:

1. 피보나치 수열은 다음과 같이 정의됩니다:
• \(  F_1 = 1  \), \(  F_2 = 1 \)
• \(  F_n = F_{n-1} + F_{n-2} \) (n ≥ 3)
2. 판디지털 숫자란 숫자 1부터 9까지의 모든 숫자를 정확히 한 번씩 포함하는 숫자를 말합니다. (예: 123456789, 987654321 등)
3. 문제의 목표는 다음 두 조건을 모두 만족하는 가장 작은 피보나치 수 \(  F_n \) 의 인덱스 n를 찾는 것입니다:
• \(F_n\) 의 앞 9자리 숫자가 판디지털이어야 함.
• \(F_n\) 의 뒤 9자리 숫자가 판디지털이어야 함.

즉, 피보나치 수 \(F_n\) 이 앞뒤로 모두 1~9의 판디지털 속성을 가지는 최초의 경우를 찾는 문제입니다.

 

Fibonacci sequence

제가 작성한 코드입니다.

//------------------------------------------------
//    Project Euler #104 - Pandigital Fibonacci Ends
//        - by Aubrey Choi
//        - created at 2015-11-02
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

bool isPandigital(int64_t s)
{
    int f = 0;
    for( int i = 0 ; i < 9 ; i++, s/=10 )
    {
        int c = s%10;
        if( c == 0 || f & (1<<c) ) return false;
        f |= 1<<c;
    }
    return true;
}

void solve1()
{
    int64_t lof1 = 1, hif1 = 1, lof2 = 1, hif2 = 1;

    for( int k = 3 ; ; k++ )
    {
        int64_t t;
        t = lof1+lof2;
        lof1 = lof2;
        lof2 = t%1000000000;
        t = hif1+hif2;
        hif1 = hif2;
        hif2 = t;
        if( hif2 > 100000000000000000 )
        {
            hif1 /= 10;
            hif2 /= 10;
        }
        if( isPandigital(lof2) == false ) continue;
        if( isPandigital(hif2/100000000) == false ) continue;
        printf("Ans = %d (%d, %d)\n", k, (int)lof2, (int)(hif2/100000000));
        break;
    }
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

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

 

이 코드는 피보나치 수열을 계산하면서, 앞 9자리와 뒤 9자리가 판디지털인지 확인하여 조건을 만족하는 최초의 인덱스를 찾습니다.

주요 구성 요소 설명

1. isPandigital 함수

bool isPandigital(int64_t s)
{
    int f = 0;
    for( int i = 0 ; i < 9 ; i++, s/=10 )
    {
        int c = s%10;
        if( c == 0 || f & (1<<c) ) return false;
        f |= 1<<c;
    }
    return true;
}

• 기능: 입력받은 숫자가 판디지털인지 검사합니다.
• 구현 방식:
1. 숫자의 각 자릿수를 한 번씩 확인합니다.
2. 숫자가 0이거나, 이미 확인한 숫자가 다시 나타나면 false를 반환합니다.
3. 각 자릿수는 비트마스크(f |= 1<<c)로 기록하여 중복 여부를 확인합니다.
4. 9개의 자릿수를 모두 확인한 뒤, 중복이 없다면 true를 반환합니다.

2. solve1 함수

void solve1()
{
    int64_t lof1 = 1, hif1 = 1, lof2 = 1, hif2 = 1;

    for( int k = 3 ; ; k++ )
    {
        int64_t t;
        t = lof1+lof2;
        lof1 = lof2;
        lof2 = t%1000000000; // 마지막 9자리 계산
        t = hif1+hif2;
        hif1 = hif2;
        hif2 = t;
        if( hif2 > 100000000000000000 )
        {
            hif1 /= 10;
            hif2 /= 10; // 앞자리 overflow 방지
        }
        if( isPandigital(lof2) == false ) continue; // 뒷자리 확인
        if( isPandigital(hif2/100000000) == false ) continue; // 앞자리 확인
        printf("Ans = %d (%d, %d)\n", k, (int)lof2, (int)(hif2/100000000));
        break;
    }
}

• 기능: 판디지털 조건을 만족하는 가장 작은 피보나치 수열의 인덱스 를 찾습니다.
• 구현 방식:
1. 두 피보나치 수를 각각 **앞자리(hif1, hif2)**와 **뒷자리(lof1, lof2)**로 분리하여 계산합니다.
2. 새 피보나치 수의 마지막 9자리(lof2)는 모듈러 연산(%1000000000)으로 계산합니다.
3. 새 피보나치 수의 첫 9자리(hif2)는 덧셈 후 overflow 방지를 위해 필요 시 10으로 나눕니다.
4. 조건:
• isPandigital 함수를 사용해 뒤 9자리(lof2)가 판디지털인지 확인.
• 앞 9자리(hif2/100000000)가 판디지털인지 확인.
5. 두 조건을 만족하면, 결과를 출력하고 종료합니다.


코드의 주요 아이디어
• 피보나치 수의 마지막 9자리와 첫 9자리만 계산하여 메모리와 계산량을 줄였습니다.
• 매우 큰 수를 직접 다루지 않고, 숫자의 필요한 부분만 다룹니다.
• 비트마스크를 사용하여 중복 검사 및 효율적인 자릿수 처리를 구현했습니다.
• 앞자리와 뒷자리 모두 판디지털 조건을 만족하는지 확인.