「プロジェクトオイラー問78」の編集履歴(バックアップ)一覧はこちら
「プロジェクトオイラー問78」(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枚のコインを山に分ける異なったやり方は7通りなので 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 を求めよ.
解法
理屈はわかりませんがWikiに書いてある分割数の漸化式で答えが出ます。
配列のないPrologで書いたらあまりエレガントとはいいがたいことになります。
末尾100万意外計算に必要ないのですから、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枚のコインを山に分ける異なったやり方は7通りなので 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 を求めよ.
解法
理屈はわかりませんがWikiに書いてある分割数の漸化式で答えが出ます。
末尾6ケタ意外計算に必要ないのですから、100万以上は切り捨てるくらいです。
配列のないPrologで書いたらあまりエレガントとはいいがたいことになるのでProlog言語では書きません。
#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);
}
}