算法设计与分析课程设计.doc

算法设计与分析课程设计题 目：删数问题专 业：信息与计算科学 一.课程设计内容问题描述:键盘输入一个高精度的正整数n（n10位）去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数最小。问题分析1、贪心法求解：删k个数符的全局最优解，包含了删除1个数符的子问题的最优解。2、以字串形式输入a，使用尽可能逼近目标的贪心法来逐一删去其中的k个数符，每一步总是选择一个能使剩下的数最小的数符删去。二.课程设计目的1. 运用贪心算法的方法解决上述问题，设计出一个通过删除数字，从输入的要删除的个数s中决定程序对正整数n的删除次数，每次删除原数据中最大的最大数，使得剩下的书最小。2.掌握贪心算法算法。三算法原理贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心准则：1、最近下降点优先2、按照高位低位搜索递减区间，若存在递减区间，则删去该区间的首字符；否则删去尾字符。3、重复上述规则，删下一个字符，依此类推，直至删去k个字符为止四、贪心算法的基本思路1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步 do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。五、程序流程图：Del(int D,int a10,int n) Main（）六源程序#includeint 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;elseD-;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(请输入一个高精度的正整数N(N=10位):);scanf(%d,&m);printf(请输入要去掉数的位数S(S=N):);scanf(%d,&D);while(1)z=m/10;ai=m-z*10;m=z;i+;n+;if(m=0)break;Res=Del(D,a,n);printf(删除后的结果为:);printf(%dn,Res);七程序运行结果8北京联合大学应用文理学院八算法时空复杂度分析此贪心算法的时间复杂度有while循环和for循环组成，所以此程序的时间复杂度为O（n2）此算法的空间复杂度为O（n2）九.