算法设计与分析课程设计--删数问题

《算法设计与分析课程设计--删数问题》由会员分享，可在线阅读，更多相关《算法设计与分析课程设计--删数问题（8页珍藏版）》请在毕设资料网上搜索。

1、 算法设计与分析课程设计算法设计与分析课程设计 题 目：删数问题 专 业：信息与计算科学 一一. .课程设计课程设计内容内容 问题描述问题描述: : 键盘输入一个高精度的正整数 n（n10 位）去掉任意 s 个数字后剩 下的数字按原左右次序组成一个新的正整数。 编程对给定的 n 和s， 寻找一种方案，使得剩下的数最小。 问题分析问题分析 1、贪心法求解：删k个数符的全局最优解，包含了删除 1 个数符的 子问题的最优解。 2、以字串形式输入a，使用尽可能逼近目标的贪心法来逐一删去其 中的k个数符， 每一步总是选择一个能使剩下的数最小的数符删去。 二二. .课程设计课程设计目的目的 1. 运用贪心

2、算法的方法解决上述问题，设计出一个通过删除数 字，从输入的要删除的个数 s 中决定程序对正整数 n 的删除次数，每 次删除原数据中最大的最大数，使得剩下的书最小。 2.掌握贪心算法算法。 三三算法原理算法原理 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在 当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所 做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都 能得到整体最优解， 但对范围相当广泛的许多问题他能产生整体最优 解或者是整体最优解的近似解。 贪心准则：贪心准则： 1、最近下降点优先 2、按照高位低位搜索递减区间，若存在递减区间，则删去该区间 的首字符；

3、否则删去尾字符。 3、重复上述规则，删下一个字符，依此类推，直至删去k个字符为 止 四、四、贪心算法的基本思路贪心算法的基本思路 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 五、五、程序流程图：程序流程图： Del(int D,int a10,int n)Del(int D,int a10,int n) MainMain（）

4、（） 六源程序六源程序 #include int Del(int D,int a10,int n)/D 删除几位 a 数组 n 当前数组 位数 int res,max,i,j,x10; for(i=0;in;i+) xi=an-i-1; while(1) if(D=0) break; else D-; max=0; j=0; for(i=0;in;i+) if(maxxi) max=xi; j=i; / n=n-2; / for(i=j;in;i+) / xi=xi+1; / n+; n-; for(i=j;in;i+) xi=xi+1; res=0; for(i=0;in;i+) res=res*10+xi; return(res); void main() int Res,D,z,n,m,i,a10; /m=43252556; i=0; n=0; printf(“n“); printf(“请