删数问题

删数问题分析与贪心实现问题描述•给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数n和正整数k，设计一个算法找出剩下的数字组成的新数最小的删数方案。•算法设计：对于给定的正整数a，计算删去k个数字后得到的最小数。•数据输入：由文件input.txt提供输入数据。文件的第一行是一个正整数a。第二个行是正整数k。•结果输出：将计算的最小数输出到文件output.txt。输入文件示例输出文件示例Input.txtoutput.txt178543134问题分析1.问题的贪心选择策略：n位数a可表示x1x2x3···xixjxkxm···xn，要删去k位数，使得剩下的数字组成的整数最小。设本问题为T，其最优解A=(y1,y2……yk)表示依次删去的k个数，在删去k个数后剩下的数字按原次序排成的新数最优值记为TA。本问题采用最近下降点优先的贪心策略：即x1x2⋯xixj；如果xkxj，则删去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-jTA’+xj•10n-j=TA。即存在一个由数a删去一位数后得到的n-1位数比最优值TA更小。与已知条件矛盾。故A‘是子问题T’的最优解，其最优值为TA‘。从以上贪心选择及最优子结构性质的证明可知，删数问题可以用贪心算法求解贪心算法求解根据以上证明，删数问题可以用最近下降点优先的贪心策略可以达到最优解。具体程序实现如下：程序源码运行结果谢谢观看