1、键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输入数据均不需判错。输出应包括所去掉的数字的位置和组成的新的正整数（N不超过240位）

算法分析：将N存在字符串中，模拟数据运算。

算法设计：若高位高于地位则删除高位，由前往后去除S位。若遍历字符串后删除位数小于S则删去最末尾几位，直到满足删除S的条件，同时输出前去除首位的0。

代码：

#include<iostream>
#include<string>
using namespace std;

void getmin(string &n,int &s,int k)//递归判断是否删去
{
    for(int i=k; i<n.size()-1; i++)
    {
        if (n[i]>n[i+1])
        {
            n.erase(i,1);
            getmin(n,--s,i-1);
        }
    }
}

int main()
{
    string n;
    int s;
    cin>>n>>s;
    getmin(n,s,0);
    while(s>0)//若删去位数小于S，删去末尾至满足条件
    {
        n.erase(n.size()-1,1);
        s--;
    }
    n.erase(0,n.find_first_not_of('0'));//去除首位的0
    if (n.empty())//若S与N的位数相等输出0
    {
        n="0";
    }
    cout<<n<<endl;
}

Hide：

1.string.erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符；

2.string.find_first_not_of(char);返回字符串第一个不是char的值的位置；

---

2、某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱, 且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编程完成。

算法分析：建立员工工资类，各种币值设置为静态成员。

算法设计：分别为每个员工求出各种币值的张数再求和。

代码：

#include<iostream>
using namespace std;
class yg
{
public:
    yg(int a=0):gz(a){}
    void setgz(int a)
    {
        gz=a;
        fun();
    }
    void fun()
    {
        m100+=gz/100;gz%=100;
        m50+=gz/50;gz%=50;
        m20+=gz/20;gz%=20;
        m10+=gz/10;gz%=10;
        m5+=gz/5;gz%=5;
        m2+=gz/2;gz%=2;
        m1+=gz;
    }
    static int m100,m50,m20,m10,m5,m2,m1;
private:
    int gz;
};
int yg::m100=0,yg::m50=0,yg::m20=0,yg::m10=0,yg::m5=0,yg::m2=0,yg::m1=0;//初始化
int main()
{
    int n,g;
    cin>>n; //输入员工数
    yg *p=new yg[n];
    for(int i=0;i<n;i++)
    {
        cin>>g;//分别输入员工工资
        p[i].setgz(g);
    }
    cout<<yg::m100<<" "<<yg::m50<<" "<<yg::m20<<" "<<yg::m10<<" "<<yg::m5<<" "<<yg::m2<<" "<<yg::m1<<endl;
}

 

---

3、有形如下图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。

9

12    15

10     6      8

2    18      9    5

19     7     10    4   16

算法分析：二位数组储存数塔。

算法设计：由倒数第二层开始往上层更新节点为由这个点到底部的最大值，塔尖得数为答案。

代码：

#include<iostream>
using namespace std;
int a[5+2][5+2];
int main()
{
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<=i;j++)
            cin>>a[i][j];
    }
    for(int i=3;i>=0;i--)
    {
        for(int j=0;j<=i;j++)
        {
            a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
        }
    }
    cout<<a[0][0]<<endl;
}