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;
}
}
}
