删数问题.pptVIP

删数问题 分析与贪心实现 问题描述 给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数n和正整数k，设计一个算法找出剩下的数字组成的新数最小的删数方案。 算法设计：对于给定的正整数a，计算删去k个数字后得到的最小数。 数据输入：由文件input.txt提供输入数据。文件的第一行是一个正整数a。 第二个行是正整数k。 结果输出：将计算的最小数输出到文件output.txt。 输入文件示例 输出文件示例 Input.txt output.txt 178543 13 4 问题分析 1.问题的贪心选择策略： n位数a可表示x1x2x3???xixjxkxm ??? xn， 要删去 k 位数 ， 使得剩下的数字组成 的整数最小 。设本问题为T，其最优解A=(y1,y2……yk) 表示依次删去的k个数 ，在删去 k 个数后剩下的数字按原次序排成的新数最优值记为 TA 。 本问题采用最近下降点优先的贪心策略 ： 即x1x2 ? xi xj； 如 果 xk xj ， 则删去Xj，即得到一个新的数且这个数为n一1位中为最小的数 N1， 可表示为x1x2x3???xixkxm 对N1而言 ,即删去了1位数后 , 原问题 T 变成了需对n-1位数删去k-1个数的新问题 T ’ 。新问题和原问题相同，只是问题规模 由n减小为n - 1 ， 删去的数字个数由k减少为 k - 1。 基于此种删除策略 ， 对新问题 T ’ ，选 择最近下降点的数进行删除 ， 如此进行下去，直至删去k个数为止 例如：对n=178543，s=4，删数的过程如下： n=178543 {删掉8} n=17543 {删掉7} n=1543 {删掉5} n=143 {删掉4} n=13 {解为13} 贪心算法性质证明 2.问题的贪心选择性质证明: 即证明： 对于问题T删除最近下降点 xj 后，得到的a1是n-1位数中最小的数。 对a按权展开得： a=x1?10n-1+x2?10n-2+ ??? +xi?10n-i+xj?10n-j+xk?10n-k ??? +xn 则有： N1=x1?10n-2+x2?10n-3+ ??? +xj?10n-j-1+xk?10n-k+ ??? +xn 假设删去的不是xq，而是其它位，则有： N2=x1?10n-2+x2?10n-3+ ??? +xi?10n-i-1+xj?10n-j+ ??? +xn 因为有x1?x2?????xi?xj且xj?xk，则有N1?N2。 因此，删数问题满足贪心选择性质。 贪心算法性质证明 3.问题的最优子结构性质证明: 即证明：若A=(xj, A’)是原问题T的最优解，则A‘是子问题T’的最优解，其最优值为TA’。 证明：反证法 假设A‘不是子问题T’的最优解，设子问题的最优解为TB‘，则： TB’TA’,而根据TA的定义可知： TA=TA’+xj?10n-j , TB’TA’，因此有 TB’+ xj?10n-j TA’+xj?10n-j =TA。 即存在一个由数a删去一位数后得到的n-1位数比最优值TA更小。与已知条件矛盾。故A‘是子问题T’的最优解，其最优值为TA‘。 从以上贪心选择及最优子结构性质的证明可知，删数问题可以用贪心算法求解 贪心算法求解 根据以上证明，删数问题可以用最近下降点优先的贪心策略可以达到最优解。具体程序实现如下 ： 程序源码 运行结果 谢谢观看