欢迎来到天天文库
浏览记录
ID:52397716
大小:2.43 MB
页数:8页
时间:2020-04-05
《贪心算法实训讲解1删数问题.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、贪心算法河南理工大学计算机科学与技术学院实训一:删数问题删除数问题。键盘输入一个高精度的正整数n(<=240位),去掉任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案,使得剩下的数最小。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
此文档下载收益归作者所有