《删数问题共8页》由会员分享，可在线阅读，更多相关《删数问题共8页（8页珍藏版）》请在金锄头文库上搜索。
1、删数问题删数问题分析与贪心实现分析与贪心实现1问题描述给定n位正整数a，去掉其中任意kn个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数n和正整数k，设计一个算法找出剩下的数字组成的新数最小的删数方案。算法设计：对于给定的正整数a，计算删去k个数字后得到的最小数。数据输入：由文件input.txt提供输入数据。文件的第一行是一个正整数a。 第二个行是正整数k。结果输出：将计算的最小数输出到文件output.txt。输入文件示例 输出文件示例 Input.txt output.txt 178543 13 42问题分析1.问题的贪心选择策略：n位数a可表示x1x2x3xix
2、jxkxm xn， 要删去 k 位数 ， 使得剩下的数字组成 的整数最小 。设本问题为T，其最优解A=(y1,y2yk) 表示依次删去的k个数 ，在删去 k 个数后剩下的数字按原次序排成的新数最优值记为 TA 。本问题采用最近下降点优先的贪心策略 ： 即x1x2 xi xj； 如 果 xk xj ， 则删去Xj，即得到一个新的数且这个数为n一1位中为最小的数 N1， 可表示为x1x2x3xixkxm对N1而言 ,即删去了1位数后 , 原问题 T 变成了需对n-1位数删去k-1个数的新问题 T 。新问题和原问题相同，只是问题规模 由n减小为n - 1 ， 删去的数字个数由k减少为 k - 1。基
3、于此种删除策略 ， 对新问题 T ，选 择最近下降点的数进行删除 ， 如此进行下去，直至删去k个数为止 例如：对n=178543，s=4，删数的过程如下： n=178543 删掉8 n=17543 删掉7 n=1543 删掉5 n=143 删掉4 n=13 解为133贪心算法性质证明2.问题的贪心选择性质证明:即证明： 对于问题T删除最近下降点 xj 后，得到的a1是n-1位数中最小的数。对a按权展开得：a=x110n-1+x210n-2+ +xi10n-i+xj10n-j+xk10n-k +xn则有：N1=x110n-2+x210n-3+ +xj10n-j-1+xk10n-k+ +xn假设删
4、去的不是xq，而是其它位，则有：N2=x110n-2+x210n-3+ +xi10n-i-1+xj10n-j+ +xn 因为有x1x2xixj且xjxk，则有N1N2。 因此，删数问题满足贪心选择性质。4贪心算法性质证明3.问题的最优子结构性质证明:即证明：若A=(xj, A)是原问题T的最优解，则A是子问题T的最优解，其最优值为TA。证明：反证法假设A不是子问题T的最优解，设子问题的最优解为TB，则： TBTA,而根据TA的定义可知： TA=TA+xj10n-j , TBTA，因此有 TB+ xj10n-j TA+xj10n-j =TA。即存在一个由数a删去一位数后得到的n-1位数比最优值TA更小。与已知条件矛盾。故A是子问题T的最优解，其最优值为TA。从以上贪心选择及最优子结构性质的证明可知，删数问题可以用贪心算法求解5贪心算法求解根据以上证明，删数问题可以用最近下降点优先的贪心策略可以达到最优解。具体程序实现如下 ：程序源码6运行结果7谢谢观看8
