組み合わせの数を教えてください

質問

下記を合計して1,000,000になる組み合わせの数を教えてください。
(5+5+5…のように重複も可)

2、3、5、8、13、21、34、55、89、144、233、377、610、987、1,597、2,584、4,181、6,765、10,946、17,711、28,657、46,368、75,025、121,393、196,418、317,811、514,229、832,040

回答No.7

7625597484987 · ベストアンサー

a[0]～a[1000000]の1000001個の要素を持つ多倍長型
（一つの要素が175ビット以上必要）の配列を作り
a[0]=1,a[1]～a[100000]=0と初期化、そして
2,3,5,8,…という配列をt[0]～t[27]として
for(i=27;i>=0;i--)
　for(j=t[i];j<=1000000;j++)
　　a[j]+=a[j-t[i]];
という二重ループを実行すれば
a[1000000]が求める値になります。

お礼

ありがとうございます。
ベストアンサーにさせていただきました。

回答No.6

7625597484987

35149126091976381690058120656043297588150432104344399通りです。

補足

ありがとうございます。
どのように解かれたか教えていただけますでしょうか。
ソルバーでしょうか？
プログラミングの場合ソースコードお教えいただきたいです。

回答No.5

hashioogi

2、3、5だけで1000000を構成する組み合わせだって膨大な数になる訳だから、全ての数を使った組み合わせの数なんて何かアイデアが無いと通常のプログラミングでもできるかどうかわかりませんよ。

回答No.4

nag0720

この問題は、手計算だけで求めるのは不可能に近いでしょうね。
エクセルのソルバーを使ったとしても無理かもしれません。

これを求めるには、プログラムを組んで総当たり法で数えるか、漸化式を作って計算するしかないでしょう。
どちらかといえば、数学というよりプログラミングの問題です。

この問題はどこかに載っていたのでしょうか？
それともご自分で考えたのでしょうか？
背景が知りたいです。

回答No.3

f272

#2です。
さっきの回答はなんだか変だな。もう少し考えてみる。

回答No.2

f272

55+144+46,368+121,393+832,040=1,000,000
だから
求める組み合わせの数は
21+55+17,711+46,368+317,811=381,966
ということかな。なぜこれでよいのかは，自分でじっくり考えてください。

補足

ありがとうございます。

回答No.1

NemurinekoNya

コンピュータを使え！！
コンピュータに解かせろ！！
これだって、立派な数学的解法よ。

補足

エクセルを持っておらず、ソルバーを使えないため解をご教示頂けますと幸いです。よろしくお願いします。