算法第四章上机实验报告

1、实验题目：

4-2 删数问题 (30 分)

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

输入格式:

第 1 行是1 个正整数 a。第 2 行是正整数k。

输出格式:

输出最小数。

输入样例:

在这里给出一组输入。例如：

178543

4

结尾无空行

5001

1

结尾无空行

123456

2

结尾无空行

109

1

结尾无空行

输出样例:

在这里给出相应的输出。例如：

13

结尾无空行

1

结尾无空行

1234

结尾无空行

9

结尾无空行

2、解题思路：

题目给定n位正整数a，而且做题需要对正整数a的每一位数字比较，所以用字符串来存该数比较好。

(1) 网上的普遍思路是若全部数字单调递增就删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程k次，剩下的数字串就是问题的解。即用选择最近下降点的数进行删除的贪心策略，如此进行下去，直至删去k个数为止。参考代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {
    char n[1001];
    int s,len;
    cin>>n>>s;
    len=strlen(n);
    for(int k=1;k<=s;k++)
    {
        for(int j=0;j<len;j++)
        {
            if(n[j+1]<n[j])
            {
                for(int i=j;i<=len;i++)
                {
                    n[i]=n[i+1];
                }
                len--;
                break;
            }
        }
    }
    bool flag=false;
    for(int i=0;i<len;i++)
    {
        if(n[i]!='0')flag=true;
        if(flag)cout<<n[i];
    }
 　　return 0;
}

(2) 删数问题也可以换一种思维，当成选数问题来做，就是当题目要求删去k个数时，当成选（n-k）个数来做，贪心策略是优先选择高位的数字并且选出的数要是该位数字可选数字中的最小数。

比如178543要删去4个数（k=4），相当于要在不改变原来数字的次序的情况下从中选6-4=2个数字，使这选出的两个数字组成的数最小。当选最高位即十位数时要预留一位个位数：（17854）3

因为贪心策略是要先满足高位，从前5位中选择一个最小数“1”来当最高位。因为数字次序不变，所以选个位时可以从78543中选（因为运行过程中不会对字符串进行删减，所以选择范围可以从字符串的下标来表示），这里选出的个位最小数就是3，最后结果就是“13”。

在拿多组数据进行实验后发现该方法可行，而且也符合人们选数的思维，可以作为该题的解。参考代码如下：

#include<iostream>
using namespace std;
//find函数用来在start-end范围内找最小数 
int find(int start,int end,string a)
{
    int min=start;
    for(int i=start;i<=end;i++)
    {
        if(a[i]<a[min])min=i;
    }
    return min;
}
int main()
{
    //need表示要选的数字个数，start和end用来表示当前所选的数字的选取范围
    int k,need,start,end,p=0,i;
    string a;
    cin>>a>>k;
    need=a.length()-k;
    start=0;
    end=a.length()-need;
    while(need>0)
    {
        need--;
        int temp=find(start,end,a);
        //找到一位后start和end下标后移一位 ，当然end不能超过length
        start=temp+1; 
        if(end<a.length())end++;
        //注意如果最高位或者前面高位有0则不输出，如001只输出1 
        if(a[temp]!='0')
        {
            p++;
        }
        if(a[temp]=='0'&&p==0)continue;
        else cout<<a[temp];
    }
    return 0;
}

3、算法满足贪心选择性质

高位优先选择，并且根据删除数字个数k，和题目要求的数字的次序不能变，得出选数所在的范围。

4、并给出时间复杂度分析

根据代码可得时间复杂度为O（a.length()^2）

5、你对贪心算法的理解

先从最简单直接的角度去想，题目要求什么就针对什么定下贪心策略，使其在当下最优。贪心策略是只看当下，不同于动态规划的先满足最优子结构。