算法第4章實踐報告

1.實踐題目：最小刪數問題

2.問題描述：給定n位正整數a，去掉其中任意k≤n 個數字后，剩下的數字按原次序排列組成一個新 的正整數。對于給定的n位正整數a和正整數 k，設計一個算法找出剩下數字組成的新數最 小的刪數方案。

3.算法描述：

#include<iostream>
using namespace std;
string n; //定義字符串n
int s;
main()
{cin>>n>>s;int len=n.length(); while(s--)for(int i=0;i<len;i++) if(n[i]>n[i+1]||i==len-1) //刪除遇到的第一個遞減序列的第一個數字(若整個字符串為非遞減序列，則刪去末尾的數字)
            {n.erase(i,1); //把當前字符從字符串中刪除break; //不可省略，否則字符串會多刪字符
            }while(n[0]=='0'&&n[1]) //去掉前綴0，并至少保留1個數字n.erase(0,1); //刪去當前字符串開頭的'0'cout<<n; //輸出字符串
}

4.算法時間和空間復雜度分析：
代碼中只用了一個數組來儲存字符串。所以空間復雜度為O（n）；時間復雜度為O（n2）；

5.心得：最開始對本道題的思路在糾結刪最大的數還是其他，用這個思路一直行不通，經過結對編程討論后發現思路是錯的，得到正確思路之后開始完善代碼。經過本次實踐，明白編程之前要先思考題目的解法，如果思路一直是錯的，可以和別人討論得出自己的思路錯在哪里再開始打代碼，不然會把自己繞暈了。