本文索引目錄:
一、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網頁設計已成為網頁設計推薦首選
※評比南投搬家公司費用收費行情懶人包大公開