컴공 일기275
게시글 주소: https://orbi.kr/00072352394

교수가 꽤 재미있는 과제를 냈습니다. 피버나치 수열의 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);
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
민지 왤케 이쁘지 12
-
오늘한공부 수학:미적 별문제 다지기,수1 프로메테우스 3강,수2 문풀 국어:피램독서...
-
ㅇㅈ 5
집까지 걸어가늦중..
-
한국사 공부 그거 해야되는데 미루고 미루다가 수능일주일 전에 하면 충분하겠지 하고...
-
4등급정도 되는 학생이라 기출 처음부터 하려고 하는데 그냥 자이스토리같은걸로 하면...
-
독서 공부할 때 7
밑줄 안 그으면 약간 모래주머니 훈련처럼 공부할 수 있는데 줄 그으면 읽고 푸는...
-
고2 10모 국어2(94) 수학3 영어1(안정) 생명4 지구4 제대로된 정시공부...
-
ㅇㅇ…
-
나온지 3년된 문제가 아직도 화제
-
잘난게 없구나 9
갈수록 꼬라박는 자신감과 자존감
-
웅야
-
강민철 환승연애 7
뉴분감 끝내고 바로 대가리 깨지면서 드릴드 박아버릴까
-
울컥울컥 4
-
국어 영어중에 최저로 11
뭘 선탣하는게 좋을까요? 방금 25수능 국어 풀어봤는데 독서는 그래도 꽤 풀리는...
-
일 어 나 라 5
-
총쏠라고사냥꾼자격증취득하고있어요허가받지않고몰래동물을사냥했어요
-
내 돈 내놔 7
내놔--!!!
-
수능을 한번 더 치고싶어서 그런데 3칸합대학 자퇴하는건 미 친짓일까요? 나이는...
-
ㅈㄱㄴ
-
스벅죽어
와 님 오랜만
ㄷㄷ
빅 인티저 문제 맞나 이게
이야 이거 1학년 자료구조 과제였는데