【C】Fibonacci数列を100桁表示

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
winter_cat
記事: 16
登録日時: 7年前
住所: Tokyo

【C】Fibonacci数列を100桁表示

#1

投稿記事 by winter_cat » 7年前

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

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

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

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

nil
記事: 428
登録日時: 8年前

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

#2

投稿記事 by nil » 7年前

いわゆる多倍長整数ですね。
フィボナッチ数列ならば多倍長整数同士の足し算、それから計算結果の出力さえ出来れば問題ないはずなので、
足し算の処理について考えて見ることにします。

コード:

#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]が二桁目という風に並んでいます。
基本は手計算の筆算と同じで一桁ずつ足し、繰り上がり、を繰り返すだけです。
桁あふれ等はこのコードではチェックしていないので注意してください。

アバター
黒船
記事: 29
登録日時: 7年前
住所: 東京都目黒あたり

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

#3

投稿記事 by 黒船 » 7年前

>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
も参考になります。

winter_cat
記事: 16
登録日時: 7年前
住所: Tokyo

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

#4

投稿記事 by winter_cat » 7年前

ありがとうございます!解決出来ました!!
多倍長整数と検索すれば結構出てきますね…

閉鎖

“C言語何でも質問掲示板” へ戻る