本文索引目錄：
一、PTA實驗報告題1 ： 程序存儲問題
1.1 實踐題目
1.2 問題描述
1.3 算法描述
1.4 算法時間及空間複雜度分析
二、PTA實驗報告題2 ： 刪數問題
2.1 實踐題目
2.2 問題描述
2.3 算法描述
2.4 算法時間及空間複雜度分析
三、PTA實驗報告題3 ： 最優合併問題
3.1 實踐題目
3.2 問題描述
3.3 算法描述
3.4 算法時間及空間複雜度分析
四、實驗心得體會（實踐收穫及疑惑）
一、PTA實驗報告題1 ： 程序存儲問題
1.1 實踐題目：
1.2 問題描述：
題意是，題干給定磁盤總容量和各個文件的佔用空間，詢問該磁盤最多能裝幾個文件。
1.3 算法描述：
簽到題，只需要將各個文件從小到大排序，並拿一個變量存儲已佔用的容量總和，進行對比即可得到結果。
#include<bits/stdc++.h> #include<algorithm> using namespace std; #define MAXLENGTH 1000 int interger[MAXLENGTH]; int main() { int num,length; int sum = 0; int counter = 0; int m = 0; cin>>num>>length; for(int i=0;i<num;i++){ cin>>interger[i]; } sort(interger,interger+num); while(true){ if(sum+interger[m]>length||counter==num) break; sum+=interger[m]; counter++; m++; } cout<<counter<<endl; return 0; }
1.4 算法時間及空間複雜度分析：
整體算法上看，輸入需要O（n）的時間進行輸入，最快用O（nlogn）的時間複雜度進行排序，使用O（n）的時間進行結果疊加，總時間複雜度為O（nlogn），時間複雜度花費在排序上。
空間上，只需要一個臨時變量存儲當前佔用容量總和即可。
二、PTA實驗報告題2 ： 刪數問題
2.1 實踐題目：
2.2 問題描述：
第二題題意是指，在給定的数字串以及可刪數個數的條件下，刪數指定k個數，得到的數是最小的。
2.3 算法描述：
首先，分析題目，刪數問題，可以用一個比較方便的函數，String類的erase函數，這個函數可以刪除字符串內的單個或多個字符，可以比較方便的處理刪數問題。
第二，我們注意到這道題有個坑點，那就是前導零，我們需要注意100000，刪除1后結果應為0
第三，確定我們的貪心策略：噹噹前的數，比后一位數大時，刪去當前的數。
如：樣例178543
用一個index時刻從頭往後掃，不滿足就后移。
當滿足之後，刪除當前的值。
得到17543，這時將index重新置0，並記錄已刪數+1，直到滿足最大刪數。以此類推，直接輸出string便是結果。
AC代碼：
#include<iostream> #include<algorithm> #include<string> using namespace std; #define MAXLENGTH 1005 int main(){ int k; string a; cin>>a>>k; int len = a.size(); while(k>0){ for(int i = 0;(i<a.size()-1);i++){ if(a[i]>a[i+1]) { a.erase(i,1); break; } } k--; } while(a.size()>1&&a[0]=='0'){ a.erase(0,1); } cout<<a<<endl; return 0; }
2.4 算法時間及空間複雜度分析：
時間複雜度為O(n^2)，即開銷在不斷的刪數和回溯到字符串頭的過程。
空間複雜度需要一個String字符串長度，因此空間複雜度是O（n）
三、PTA實驗報告題3 ： 最優合併問題
3.1 實踐題目：
3.2 問題描述：
該題目為：題目用 2 路合併算法將這k 個序列合併成一個序列，並且合併 2 個長度分別為m和n的序列需要m+n-1 次比較，輸出某段合併的最大比較次數和最小比較次數。
3.3 算法描述：
這道題算是哈夫曼算法的一道裸題，很容易解決，只需要使用優秀隊列不斷維護最小值或最大值即可。
哈夫曼樹：是一顆最優二叉樹。給定n個權值作為n個恭弘=叶 恭弘子的結點，構造一棵二叉樹，若樹的帶權路徑長度達到最小，這棵樹則被稱為哈夫曼樹。
因此本題根據哈夫曼算法，我們以最小比較次數為例：
首先從隊列中選出兩個最小的數進行合併，並在隊列中刪除這兩個數，並將新合成數加入隊列中。
再取最小的兩個數再進行合併，以此類推，得到最終的大數如下
因此最小比較次數為：（ 7 – 1 ） + （ 18 – 1 ） + （ 30 – 1 ） = 52，即為所得。最大比較次數也是同理。
AC代碼如下：
#include<bits/stdc++.h> using namespace std; priority_queue<int> Haff; priority_queue<int, vector<int>, greater<int> > Haff2; int n,ans1,ans2; int main() { cin>>n; for(int i = 0;i<n;i++) { int temp; cin>>temp; Haff.push(temp); Haff2.push(temp); } while(1) { if(Haff.size() == 1) break; int temp1 = Haff.top(); Haff.pop(); int temp2 = Haff.top(); Haff.pop(); Haff.push(temp1+temp2); ans1 += temp1+temp2-1; } while(1) { if(Haff2.size() == 1) break; int temp1 = Haff2.top(); Haff2.pop(); int temp2 = Haff2.top(); Haff2.pop(); Haff2.push(temp1+temp2); ans2 += temp1+temp2-1; } cout<<ans1<<" "<<ans2; return 0; }
3.4 算法時間及空間複雜度分析：
由分析易知，雖然進行了兩次優先隊列維護，但是總的時間複雜度數量級是不變的，用O（n/2）的時間pop和push合成樹。在優先隊列裏面用紅黑樹對順序進行維護，時間複雜度為O（nlogn），最後將統計的結果輸出，總的時間複雜度為O（nlogn）。
空間複雜度為兩棵紅黑樹，即T（2n） = O（n）。
四、實驗心得體會（實踐收穫及疑惑）：
經過動態規劃的肆虐之後，貪心算法變得稍微容易很多，和三木小哥哥的合作很愉快，能夠很好較快及時的解決三道實踐問題，暫無太多的問題，繼續加油。
如有錯誤不當之處，煩請指正。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享
※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選
※評比南投搬家公司費用收費行情懶人包大公開
