1?扔雞蛋問題

動態規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優化的過程。20世紀50年代初，美國數學家貝爾曼（R.Bellman）等人在研究多階段決策過程的優化問題時，提出了著名的最優化原理，從而創立了動態規劃。動態規劃的應用極其廣泛，包括工程技術、經濟、工業生產、軍事以及自動化控制等領域，并在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統可靠性問題等中取得了顯著的效果。

扔雞蛋問題是計算機程序設計中的一個經典問題。從一幢樓房的不同樓層往下扔雞蛋，用最少的最壞情況試驗次數，確定雞蛋不會摔碎的最高安全樓層。僅有一個雞蛋供試驗時，只能采用順序查找法。有足夠多的雞蛋時，可以采用二分查找法。有多于一個但數量有限的雞蛋時，采用動態規劃方法求解。雙蛋問題 (two-egg problem) 是本問題的一個特例，曾出現于谷歌的程序員面試題中。
?

2 源程序

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
?? ?/// <summary>
?? ?/// Dynamic Programming
?? ?/// Egg Dropping Puzzle
?? ?/// </summary>
?? ?public static partial class Algorithm_Gallery
?? ?{
?? ??? ?public static int Egg_Drop(int n, int k)
?? ??? ?{
?? ??? ??? ?if (k == 1 || k == 0)
?? ??? ??? ?{
?? ??? ??? ??? ?return k;
?? ??? ??? ?}
?? ??? ??? ?if (n == 1)
?? ??? ??? ?{
?? ??? ??? ??? ?return k;
?? ??? ??? ?}
?? ??? ??? ?int min = int.MaxValue;
?? ??? ??? ?for (int x = 1; x <= k; x++)
?? ??? ??? ?{
?? ??? ??? ??? ?int res = Math.Max(Egg_Drop(n - 1, x - 1), Egg_Drop(n, k - x));
?? ??? ??? ??? ?if (res < min)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?min = res;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?return min + 1;
?? ??? ?}

?? ??? ?public static int Egg_Drop_Second(int n, int k)
?? ??? ?{
?? ??? ??? ?int[,] eggFloor = new int[n + 1, k + 1];

?? ??? ??? ?for (int i = 1; i <= n; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?eggFloor[i, 1] = 1;
?? ??? ??? ??? ?eggFloor[i, 0] = 0;
?? ??? ??? ?}

?? ??? ??? ?for (int j = 1; j <= k; j++)
?? ??? ??? ?{
?? ??? ??? ??? ?eggFloor[1, j] = j;
?? ??? ??? ?}
?? ??? ??? ?for (int i = 2; i <= n; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?for (int j = 2; j <= k; j++)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?eggFloor[i, j] = int.MaxValue;
?? ??? ??? ??? ??? ?for (int x = 1; x <= j; x++)
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?int res = 1 + Math.Max(eggFloor[i - 1, x - 1], eggFloor[i, j - x]);
?? ??? ??? ??? ??? ??? ?if (res < eggFloor[i, j])
?? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ?eggFloor[i, j] = res;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?return eggFloor[n, k];
?? ??? ?}

?? ??? ?private static readonly int MAX_EGGS = 1000;
?? ??? ?private static int[,] egg_drop_dump = new int[MAX_EGGS, MAX_EGGS];

?? ??? ?public static int Egg_Drop_Third(int n, int k)
?? ??? ?{
?? ??? ??? ?if (egg_drop_dump[n, k] != -1)
?? ??? ??? ?{
?? ??? ??? ??? ?return egg_drop_dump[n, k];
?? ??? ??? ?}
?? ??? ??? ?if (k == 1 || k == 0)
?? ??? ??? ?{
?? ??? ??? ??? ?return k;
?? ??? ??? ?}
?? ??? ??? ?if (n == 1)
?? ??? ??? ?{
?? ??? ??? ??? ?return k;
?? ??? ??? ?}

?? ??? ??? ?int min = int.MaxValue;
?? ??? ??? ?for (int x = 1; x <= k; x++)
?? ??? ??? ?{
?? ??? ??? ??? ?int res = Math.Max(Egg_Drop_Third(n - 1, x - 1), Egg_Drop_Third(n, k - x));
?? ??? ??? ??? ?if (res < min)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?min = res;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?egg_drop_dump[n, k] = min + 1;
?? ??? ??? ?return min + 1;
?? ??? ?}
?? ?}
}

3 代碼格式

using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{/// <summary>/// Dynamic Programming/// Egg Dropping Puzzle/// </summary>public static partial class Algorithm_Gallery{public static int Egg_Drop(int n, int k){if (k == 1 || k == 0){return k;}if (n == 1){return k;}int min = int.MaxValue;for (int x = 1; x <= k; x++){int res = Math.Max(Egg_Drop(n - 1, x - 1), Egg_Drop(n, k - x));if (res < min){min = res;}}return min + 1;}public static int Egg_Drop_Second(int n, int k){int[,] eggFloor = new int[n + 1, k + 1];for (int i = 1; i <= n; i++){eggFloor[i, 1] = 1;eggFloor[i, 0] = 0;}for (int j = 1; j <= k; j++){eggFloor[1, j] = j;}for (int i = 2; i <= n; i++){for (int j = 2; j <= k; j++){eggFloor[i, j] = int.MaxValue;for (int x = 1; x <= j; x++){int res = 1 + Math.Max(eggFloor[i - 1, x - 1], eggFloor[i, j - x]);if (res < eggFloor[i, j]){eggFloor[i, j] = res;}}}}return eggFloor[n, k];}private static readonly int MAX_EGGS = 1000;private static int[,] egg_drop_dump = new int[MAX_EGGS, MAX_EGGS];public static int Egg_Drop_Third(int n, int k){if (egg_drop_dump[n, k] != -1){return egg_drop_dump[n, k];}if (k == 1 || k == 0){return k;}if (n == 1){return k;}int min = int.MaxValue;for (int x = 1; x <= k; x++){int res = Math.Max(Egg_Drop_Third(n - 1, x - 1), Egg_Drop_Third(n, k - x));if (res < min){min = res;}}egg_drop_dump[n, k] = min + 1;return min + 1;}}
}