「プロジェクトオイラー問７８」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問７８」(2014/03/02 (日) 11:20:44) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2078

*Problem 78　「コインの分割」 †
n 枚のコインを異なった方法で山に分ける場合の数を p(n) と表わす. 例えば, 5枚のコインを山に分ける異なったやり方は７通りなので p(5)=7 となる.

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

p(n) が100万で割り切れる場合に最小となる n を求めよ.





解法
理屈はわかりませんがＷｉｋｉに書いてある分割数の漸化式で答えが出ます。
配列のないＰｒｏｌｏｇで書いたらあまりエレガントとはいいがたいことになります。
末尾１００万意外計算に必要ないのですから、100万以上は切り捨てるくらいです。


 #include<stdio.h>
 #include<vector>
 
 const int MOD=1000*1000;
 int main(){
 	std::vector<int> p;
 	p.push_back(1);
 	p.push_back(1);
 	for(int i=2;;i++){
 		int d=1;
 		int n=1;
  		int add;
 		int sum=0;
 		while(1){
  			int a=(n*(3*n-1))/2;
 			add= i>=a?p[i-a]:0;
 			sum+=add*d;
 			
  			int b=(-n*(3*(-n)-1))/2;
 			add=i>=b?p[i-b]:0;
 			sum=(sum+add*d) % MOD;
 			d*=-1;
 			n++;
 			if(i<b)break;
  		}
 		if(sum==0){
 			printf("%d\n",i);
 			break;
 		}
 		p.push_back(sum);
 	}
 }

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2078

*Problem 78　「コインの分割」 †
n 枚のコインを異なった方法で山に分ける場合の数を p(n) と表わす. 例えば, 5枚のコインを山に分ける異なったやり方は７通りなので p(5)=7 となる.

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

p(n) が100万で割り切れる場合に最小となる n を求めよ.





解法
理屈はわかりませんがＷｉｋｉに書いてある分割数の漸化式で答えが出ます。
末尾６ケタ意外計算に必要ないのですから、100万以上は切り捨てるくらいです。
配列のないＰｒｏｌｏｇで書いたらあまりエレガントとはいいがたいことになるのでＰｒｏｌｏｇ言語では書きません。



 #include<stdio.h>
 #include<vector>
 
 const int MOD=1000*1000;
 int main(){
 	std::vector<int> p;
 	p.push_back(1);
 	p.push_back(1);
 	for(int i=2;;i++){
 		int d=1;
 		int n=1;
  		int add;
 		int sum=0;
 		while(1){
  			int a=(n*(3*n-1))/2;
 			add= i>=a?p[i-a]:0;
 			sum+=add*d;
 			
  			int b=(-n*(3*(-n)-1))/2;
 			add=i>=b?p[i-b]:0;
 			sum=(sum+add*d) % MOD;
 			d*=-1;
 			n++;
 			if(i<b)break;
  		}
 		if(sum==0){
 			printf("%d\n",i);
 			break;
 		}
 		p.push_back(sum);
 	}
 }