卵落としパズルをC言語で解く ― 動的計画法（DP）による実装

「卵落としパズル（Egg Dropping Puzzle）」は、動的計画法（DP）を学ぶうえで有名な古典的なアルゴリズム問題です。n階建ての建物とm個の卵が与えられたとき、卵が割れずに落とすことのできる「安全な階」を見つけるために必要な最小の落下回数を求めます。

この問題を解くうえで、次の重要なポイントを押さえておきましょう。

• ある階で卵が割れなかった場合、それより下のどの階から落としても割れることはありません。
• ある階で卵が割れた場合、それより上のすべての階から落としたときには必ず割れます。
• 割れてしまった卵は廃棄しなければなりません。一方、割れなかった卵は何度でも再利用できます。

入力 − 卵の数と最大階数。ここでは、卵が4個、最大階数が10階の場合を例にします。

出力 − 最悪の場合における最小試行回数は 4回。

アルゴリズム

eggTrialCount(eggs, floors)

入力 − 卵の数、最大階数。

出力 − 最小試行回数を取得します。

Begin
    define matrix of size [eggs+1, floors+1]
    for i:= 1 to eggs, do
       minTrial[i, 1] := 1
       minTrial[i, 0] := 0
    done
    for j := 1 to floors, do
       minTrial[1, j] := j
    done
    for i := 2 to eggs, do
       for j := 2 to floors, do
          minTrial[i, j] := ∞
          for k := 1 to j, do
             res := 1 + max of minTrial[i-1, k-1] and minTrial[i, j-k]
             if res < minTrial[i, j], then minTrial[i,j] := res
          done
       done
    done
    return minTrial[eggs, floors]
End

このアルゴリズムでは、minTrial[i][j] を「i個の卵とj階の建物に対する最悪ケースの最小試行回数」として定義します。各階kで卵を落とした場合を想定し、卵が割れたときは残り i−1 個の卵で k−1 階を調べるケース、割れなかったときは i 個の卵で j−k 階を調べるケースのうち、大きい方（最悪ケース）に1を加えた値を候補とし、その中から最小値を選びます。

サンプルコード（C言語）

#include<stdio.h>
#define MAX_VAL 9999

int max(int a, int b) {
   return (a > b)? a: b;
}

int eggTrialCount(int eggs, int floors) { //最悪ケースにおける最小試行回数を求める
   int minTrial[eggs+1][floors+1]; //i番目の卵・j番目の階に対する最小試行回数を格納
   int res, i, j, k;

   for (i = 1; i <= eggs; i++) { //1階からは1回の試行、0階なら試行不要
      minTrial[i][1] = 1;
      minTrial[i][0] = 0;
   }

   for (j = 1; j <= floors; j++) //卵が1個のときは、各階につき1回ずつ試行が必要
      minTrial[1][j] = j;

   for (i = 2; i <= eggs; i++){ //卵が2個以上の場合
      for (j = 2; j <= floors; j++) { //2階以上の場合
         minTrial[i][j] = MAX_VAL;
         for (k = 1; k <= j; k++) {
            res = 1 + max(minTrial[i-1][k-1], minTrial[i][j-k]);
            if (res < minTrial[i][j])
               minTrial[i][j] = res;
         }
      }
   }
   return minTrial[eggs][floors]; //指定された卵の数と階数に対する試行回数
}

int main () {
   int egg, maxFloor;
   printf("Enter number of eggs: ");
   scanf("%d", &egg);
   printf("Enter max Floor: ");
   scanf("%d", &maxFloor);
   printf("Minimum number of trials: %d", eggTrialCount(egg, maxFloor));
}

実行結果

Enter number of eggs: 4
Enter max Floor: 10
Minimum number of trials: 4

卵4個、10階建ての建物という条件では、最悪の場合でもわずか4回の落下で安全な階を特定できることがわかります。このように動的計画法を用いることで、全探索に比べて大幅に試行回数を削減できます。