贪心算法C语言解决删数问题
问题描述：
给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。
如：把178543删掉4位数，生成最小的数为13
解决办法：贪心算法，每次删数时选择删除非递减序列的最后一个数，注意不是每次删除最大的数
证明过程略
C语言代码如下
#include<stdio.h>
void Delnum(int n,int k,int a[])//这个函数会稍微难理解些
{
int i,j,t;
for(t=1;t<=k;t++)//表示要删k次数
{
for(j=0;a[j]<=a[j+1]&&j<n-t;j++) ;//找到非递减序列的最后一个数
if(j<n-t)//表示要删的数不是目前数组最后一个数时（即要删的数不是a[n-t]时）
{
while(j<n-t)
{
a[j]=a[j+1];//移动数组
j++;
}
}
/*如果要删的数是目前数组最后一个数时（即要删的数是a[n-t]时）
这时可以不做任何操作，因为每次删数t会加一，后面的操作就不会涉及a[n-t],最终也不会输出a[n-t],
等效于把a[n-t]删除了，所以此处没有else语句，即不做任何操作*/
}
}
int main()
{
int n,k,i;//n为初始数字位数，k为要删的数字个数
printf("请输入n和k的值：");
scanf("%d%d",&n,&k);
printf("
请输入正整数a：");
int a[n];
for(i=0;i<n;i++)
scanf("%1d",&a[i]);
Delnum(n,k,a);
i=0;
while(a[i]==0)//跳过删数后所得的数前面的0
i++;
for(;i<n-k;i++)
printf("%d",a[i]);
}
运行结果如下
下一篇：
排序算法 Java编程问题 小结