컴공 일기275

Question

교수가 꽤 재미있는 과제를 냈습니다. 피버나치 수열의 1000번째 값을 구하고 싶은데, 보다시피 자리수만 따져 보더라도 200자리가 훌쩍 넘어갑니다. 파이썬은 고민할 필요가 없겠습니다만 C언어에서는 200자리가 넘어가는 정수형을 담을 수 있는 기본 자료형이 존재하지 않습니다. 기껏해야 long long일텐데, 이 마저도 200자리는 커버할 수 없지요.

물론, 라이브러리를 이용하면 이 정도 문제야 간단히 해결할 수 있습니다만

바보가 아닌 교수는 라이브러리를 사용하지 않고, 적합한 코딩을 통해 200자리를 담아낼 수 있는 코드를 작성하라고 하는 겁니다.

방법은 간단합니다. 그냥 합치는 거죠. 기본 타입으로는 200비트를 커버할 수 없으므로, char형 200사이즈 되는 배열 두 개를 만들고,

피버나치 점화식을 돌리면서 이 배열들을 업데이트해주면 됩니다. 기본 정수형이 200비트에 모자라서 생긴 일이니, 충분히 커버할 수 있는 array 자료구조를 이용하면 되는 겁니다.

#include <stdio.h>

#include <string.h>

#define N 209 //The 1000th Fibonacci number has 209 decimal digits.

void print_digits(char d[N])

{

int i = 0;

while(d[i] == 0) i++;

while(i<N)

{

printf("%d", d[i++]);

}

void add_digits(char aa[N], char bb[N])

{

int i = 0;

int carry = 0;

int j,s;

while(aa[i] == 0) i++;

for(j=N-1; j>=i-1; j--)

{

if( ( s = carry + aa[j] + bb[j]) > 9)

{

carry = 1;

bb[j] = s-10;

}

else

{

bb[j] = s;

carry = 0;

}

int main()

{

char aa[N] = {0};

char bb[N] = {0};

char tmp[N] = {0};

bb[N-1] = 1;

for(int i=2; i<=1000; i++)

{

memcpy(tmp, bb, sizeof(bb)); //save bb

add_digits(aa, bb); //update bb

memcpy(aa, tmp, sizeof(tmp)); //update aa

}

print_digits(bb);

}

푸른색의청새치 · Accepted Answer

와 님 오랜만

ㅤ떽띠송우기ㅤㅤ · Answer

ㄷㄷ

밤바람 · Answer

빅 인티저 문제 맞나 이게

todayis_wendy · Answer

이야 이거 1학년 자료구조 과제였는데

컴공 일기275

최근 게시글 · 더보기

댓글이 많은 글