时尚字体设计网站,购物网站排名2016,怎么仿制网站,湖州做网站推广的公司1 扔鸡蛋问题
动态规划#xff08;Dynamic Programming#xff0c;DP#xff09;是运筹学的一个分支#xff0c;是求解决策过程最优化的过程。20世纪50年代初#xff0c;美国数学家贝尔曼#xff08;R.Bellman#xff09;等人在研究多阶段决策过程的优化问题时#xf…
1 扔鸡蛋问题
动态规划Dynamic ProgrammingDP是运筹学的一个分支是求解决策过程最优化的过程。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/// /summarypublic 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;}}
}
