ページ 11

【C】Fibonacci数列を100桁表示

Posted: 2013年4月12日(金) 15:16
by winter_cat
Fibonacci数列を100桁まで求めたいのですが、long long intでもでも出来ませんし、ここ(http://www.nak.ics.keio.ac.jp/class/h-c/bigint.pdf)を見てもいまいちわかりません(汗)

配列を使って各桁を格納するという方法自体はわかったのですが実際にどのように書けばいいのかが…

単純に30までの数列を求めるような問題は出来ました。

どなたかアドバイスお願いします。

Re: 【C】Fibonacci数列を100桁表示

Posted: 2013年4月12日(金) 18:52
by nil
いわゆる多倍長整数ですね。
フィボナッチ数列ならば多倍長整数同士の足し算、それから計算結果の出力さえ出来れば問題ないはずなので、
足し算の処理について考えて見ることにします。

コード:

#include <stdio.h>
#define N (32)

//	多倍長整数同士の足し算
void Add( char a[N], const char b[N] ){
	int x, i;
	x = 0;
	for( i=0; i<N; i++ ){
		x += a[i] + b[i];
		a[i] = x%10;
		x /= 10;
	}
}

int main(){
	int i;
	char a[N] = { 1,2,3,4,5,6,7,8,9,1,0,2,5 };  // 5201987654321
	char b[N] = { 2,3,8,5,4,6,8 };              //       8645832
	Add( a, b );
	
	for( i=N-1; i>=0; i-- ){
		printf( "%d", (int)a[i] );
	}
	puts( "" );// 改行
}
-出力

コード:

00000000000000000005201996300153
※a[0]が一桁目, a[1]が二桁目という風に並んでいます。
基本は手計算の筆算と同じで一桁ずつ足し、繰り上がり、を繰り返すだけです。
桁あふれ等はこのコードではチェックしていないので注意してください。

Re: 【C】Fibonacci数列を100桁表示

Posted: 2013年4月12日(金) 23:09
by 黒船
>Fibonacci数列を100桁まで求めたいのですが、long long intでもでも出来ませんし、ここ(http://www.nak.ics.keio.ac.jp/class/h-c/bigint.pdf)を見てもいまいちわかりません(汗)

多倍長整数(かなり大きな数字を扱うことができる数)を扱うライブラリにGMPというものがあります。
インストールしなければいけませんが、
非常に高速で便利です。

よく参考にしているサイト
http://d.hatena.ne.jp/pyopyopyo/20090303/p1

英語のページですが
http://gmplib.org/manual/Function-Index ... tion-Index
も参考になります。

Re: 【C】Fibonacci数列を100桁表示

Posted: 2013年4月16日(火) 14:20
by winter_cat
ありがとうございます!解決出来ました!!
多倍長整数と検索すれば結構出てきますね…