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)的三种算法与源代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

如何将Python彻底卸载的三种方法

《如何将Python彻底卸载的三种方法》通常我们在一些软件的使用上有碰壁,第一反应就是卸载重装,所以有小伙伴就问我Python怎么卸载才能彻底卸载干净,今天这篇文章,小编就来教大家如何彻底卸载Pyth... 目录软件卸载①方法:②方法:③方法:清理相关文件夹软件卸载①方法:首先,在安装python时,下

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》:本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、

C#TextBox设置提示文本方式(SetHintText)

《C#TextBox设置提示文本方式(SetHintText)》:本文主要介绍C#TextBox设置提示文本方式(SetHintText),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录C#TextBox设置提示文本效果展示核心代码总结C#TextBox设置提示文本效果展示核心代

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

C#中DrawCurve的用法小结

《C#中DrawCurve的用法小结》本文主要介绍了C#中DrawCurve的用法小结,通常用于绘制一条平滑的曲线通过一系列给定的点,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 如何使用 DrawCurve 方法(不带弯曲程度)2. 如何使用 DrawCurve 方法(带弯曲程度)3.使用Dr

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2