首页 > 技术文章 > 贪心算法----删数问题

cxmhy 2015-05-06 13:00 原文

一、问题描述

给定n位整数a,去掉其中任意k<=n个数字后,剩下的数字按原次序排列组成一个新的正整数。
如输入一个正整数:178543;
删除其中4个数
得到:13

二、解决思路--贪婪算法

这里先介绍之前错误的思路:

找出数字中n-k个最小的数,组成新的正整数;

但是很快就有问题出现,虽然每次都找的是整数各个位置中最小的数,但是忽略掉了位置的相对关系,如以下的例子:

输入的一个整数:178906; 6位数的整数

删除其中4个数;

按照这个思路,即要选择6-4=2个最小的数,即0 和1,按照数中原有的次序,得到的是10;

但是事实上,应该是06,即6

 

所以换个思路,叫“最近下降点”优先。

利用“最陡下降点”优先,即每次找到第一个元素,使其满足大于下一个元素。正如上述的那个例子,第一个删除的是9,因为9>0;

得到的整数是17806;第二个删除的是8,因为8>0,得到的整数是1706,第三个删除的是7,因为7>0,得到的整数是106;

第四个删除的是1,因为1>0,得到的是06,为正确的答案。

 

三、程序设计

(1)同样,给出错误的设计思路的程序:

(2)正确的设计思路的程序:

 

推荐阅读