算法第四章实践报告

一、问题

删数问题

引入：
给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。

输入格式：
第 1 行是1 个正整数 a。第 2 行是正整数k。

输出格式：
输出最小数。

输入样例1：
178543
4
输出样例1：
13
输入样例2：
109
1
输出样例2：
9
//去掉1，剩09，故输出为9

二、分析
利用贪心算法解题，删去数时，先找到一个比后面数大的数，删去这个数，再将其后面的每个数前移。
如178543，要去掉4个数。
① 找到8，8比5大，去掉8，并把后面的5、4、3前移，字符串变为17543
② 找到7，7比5大，去掉7，并把后面的4、3前移，字符串变为1543
同理接着删去其他两个数，余下13输出。

注意，0在组成数时可以在首位，但不输出。如样例2中，09最终输出的结果是9。故在输出前，需先将下标移到首个非0数，从该数开始对余下的数进行输出。

三、代码实现

#include
using namespace std;
int main(){
int n, i, j, k;
string a;
cin >> a >> n;
int len = a.size();
for(k = 0; k < n; k++)
{
for(i = 0; i < len-1; i++)
{ //从首位置开始判断，若有比后面大的数则删除并把其之后的数前移
if(a[i] > a[i+1])
{
for(j = i; j < len-1; j++) //删数并前移
a[j] = a[j+1]; //删除i位置上的数，并把i位置后的数前移
break; //break第二层循环
}
}
len--; //无论是否为完全递增序列，每次大循环都至少删去一个数，故长度一定减1
}
i = 0;
while(i <= len-1 && a[i] == '0') //注意a是字符串，判断a[i]是判断字符
//找到首个非零数的下标
i++;
if(i == len)
cout << "0";
else{
for(; i <= len-1; i++)
cout << a[i];
}
}

四、贪心算法的心得