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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C#中的 StreamReader/StreamWriter 使用示例详解

《C#中的StreamReader/StreamWriter使用示例详解》在C#开发中,StreamReader和StreamWriter是处理文本文件的核心类,属于System.IO命名空间,本... 目录前言一、什么是 StreamReader 和 StreamWriter?1. 定义2. 特点3. 用

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时