欢迎来到天天文库
浏览记录
ID：52397716
大小：2.43 MB
页数：8页
时间：2020-04-05
《贪心算法实训讲解1删数问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、贪心算法河南理工大学计算机科学与技术学院实训一：删数问题删除数问题。键盘输入一个高精度的正整数ｎ（<=240位），去掉任意ｓ个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的ｎ和ｓ，寻找一种方案，使得剩下的数最小。SimpleInput1785434SimpleOutput13SimpleInput1785434SimpleOutput13如果是你动手来做，你会怎么做呢？例如N=178543S=5过程如下N=178543{删掉8}17543{删掉7}1543{删掉5}143{删掉4}13{解为13}做法一首先枚举删除1个数字的情况，然后使剩下的数
2、字串最小，接着继续枚举，继续确保剩下的数字串最小。直到删除了S个数字……每次都要从头扫描一次，不停删除不同位置的数字，然后对剩下数字串选择出最小，接着又是从头扫描，直到删除了S个数字这是一个枚举的算法，虽然也是可以得到最优解。但是效率比较低，假设当前找到了删除一个数字使得剩下的数字串最小，根据做法一程序还要继续枚举，直到枚举完所有数字才会停止。这么做就在浪费时间了。做法二每一步总是选择一个使剩下的数最小的数字删除，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符，这样删一位便形成了一个新的数字串。然后回到串首，按上述
3、规则再删除下一个数字程序输入N，SWhiles>0doBegini=1;While(i1)and(n[1]=‘0’)dodelete(n,1,1)输出N
此文档下载收益归作者所有
