例題 2![]() 方針・アルゴリズム例題 1 と同様に x, y, z すべての組合わせを 1 つずつ試していくというのが最も単純である.しかし,この問題では x, y, z を使った 3 重ループとなり, 各々で 1991 回(※ 10 〜 2000 の範囲)の繰り返しが行われる. つまり,1991 × 1991 × 1991 = 7,892,485,271 回のチェックが必要になり効率が悪い. ここでは問題を解析することで効率の向上を図る.
いま,y, z = 10 (最小値)に固定すると,与式は
同様に解析すると y は 26 以下,z は 18 以下 で十分あることがわかる. したがって,x, y, z の 3 重ループという構造に変化は無いが, 繰り返しの範囲は
ポイント
多重ループで答えを探す場合,
その探索範囲をうまく絞り込むことで大幅な効率 UP
を実現できることもある.
コーディング例1 /* 2 * プログラミング演習 第 14 回 3 * [例題 2] 改善版 4 * (C) 2006 Hirohisa AMAN <aman@cs.ehime-u.ac.jp, aman@computer.org> 5 */ 6 #include <stdio.h> 7 8 int main(void){ 9 int x, y, z; 10 11 /* x = 10, ..., 21 として繰り返す */ 12 for ( x = 10; x <= 21; x++ ){ 13 14 /* 各 x に対して y = 10, ..., 26 として繰り返す */ 15 for ( y = 10; y <= 26; y++ ){ 16 17 /* 各 x,y に対して z = 10, ..., 18 として繰り返す */ 18 for ( z = 10; z <= 18; z++ ){ 19 20 /* 3x + 2y + 4z - 123 の値が 0 に等しい時のみ x,y,z を出力する */ 21 if ( 3*x + 2*y + 4*z - 123 == 0 ){ 22 printf("%d %d %d\n", x, y, z); 23 } 24 25 } 26 27 } 28 29 } 30 31 return 0; 32 }
※左端の数字は行番号であり,ソースコードには含まれない点に注意!
コンパイル & 実行例$ gcc example14_2.c [Enter] $ ./a.out [Enter] 11 11 17 11 13 16 11 15 15 11 17 14 11 19 13 11 21 12 11 23 11 11 25 10 13 10 16 13 12 15 13 14 14 13 16 13 13 18 12 13 20 11 13 22 10 15 11 14 15 13 13 15 15 12 15 17 11 15 19 10 17 10 13 17 12 12 17 14 11 17 16 10 19 11 11 19 13 10 21 10 10 |