C#，动态规划（DP）丢鸡蛋问题（Egg Dropping Puzzle）的三种算法与源代码

本文主要是介绍C#，动态规划（DP）丢鸡蛋问题（Egg Dropping Puzzle）的三种算法与源代码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这篇关于C#，动态规划（DP）丢鸡蛋问题（Egg Dropping Puzzle）的三种算法与源代码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！