第 14 回 - 組合わせ問題

[4/24, 2006 H.Aman]

例題 2

$456x99(16879bytes)$

方針・アルゴリズム

例題 1 と同様に x, y, z すべての組合わせを 1 つずつ試していくというのが最も単純である．
しかし，この問題では x, y, z を使った 3 重ループとなり，各々で 1991 回（※ 10 ～ 2000 の範囲）の繰り返しが行われる．つまり，1991 × 1991 × 1991 = 7,892,485,271 回のチェックが必要になり効率が悪い．
ここでは問題を解析することで効率の向上を図る．

いま，y, z = 10 （最小値）に固定すると，与式は $160x14(2658bytes)$ ，すなわち， $47x14(1062bytes)$ となる．
y, z の係数は正なので，これらが 10 以上の値をとれば x は 21 以下でなくてはならない．つまり，x > 21 において等号の成立はあり得ない．

同様に解析すると y は 26 以下，z は 18 以下で十分あることがわかる．

したがって，x, y, z の 3 重ループという構造に変化は無いが，繰り返しの範囲は

x = 10 ～ 21
y = 10 ～ 27
z = 10 ～ 18

で十分である．（チェック回数は 12 × 17 × 9 回で済むので，元の 99.9999767 % は無駄であったことが分かる．）

ポイント

多重ループで答えを探す場合，その探索範囲をうまく絞り込むことで大幅な効率 UP を実現できることもある．

コーディング例

example14_2.c

     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