★★ Java の宿題ここで答えます Part 66 ★★

★★ Java の宿題ここで答えます Part 66 ★★ at TECH

566:デフォルトの名無しさん
08/12/06 23:39:33
>>564
時間かかるからやめとけｗ
それよりも計算量を減らしたり無駄にループを回さないように工夫をしたほうがいい
for (int a = 0; a <= n; a += 1) {
for (int b = 0; b <= n; b += 5) {
for (int c = 0; c <= n; c += 10) {
for (int d = 0; d <= n; d +=20) {
if (a + b + c + d == n) count++;
これだけでも違うし最深のループで和がnに等しくなったらそれ以上ループするのは無意味だから
if (a + b + c + d == n) {
count++;
break;
各ループでも同様にそれまでの和(a, a+b, a+b+c)がnを超えるようならそれ以上やらなくてもいいから
for (int a = 0; a <= n; a += 1) {
for (int b = a; b <= n; b += 5) {
for (int c = b; c <= n; c += 10) {
for (int d = c; d <= n; d += 20) {
if (d == n) {
count++;
break;
みたいにできる(この場合のb,c,dはそのレベルのループまでの和であって各硬貨ごとの和を表していない)
この場合の最後のbreakは加算と比較をそれぞれ1回分減らすだけだがループ回数が多いので少し速くなる
たったこれだけの工夫でも少しはマシになる
それといきなり10倍なんて試さずに2倍づつとか1000刻みとかで計算時間の予測をつけておいた方が精神衛生上いいと思うが
それより気になるのは20円硬貨の存在かもしれんｗ

次ページ

続きを表示

1を表示