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

2024-02-23 14:44
文章标签 c# 算法 动态 规划 问题 dp 三种 源代码 .net 鸡蛋 egg netcore puzzle dropping

本文主要是介绍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）的三种算法与源代码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/738974。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
2. c#从不同cs的文件调用函数

2. c#从不同cs的文件调用函数

1.文件目录如下： 2. Program.cs文件的主函数如下 using System;using System.Collections.Generic;using System.Linq;using System.Threading.Tasks;using System.Windows.Forms;namespace datasAnalysis{internal static
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2