1、設計分析
● 問題描述：
鍵盤輸入乙個高精度的正整數n（n不超過240位） ，去掉其中任意s個數字後剩下的數字按原左右次序將組成乙個新的正整數。程式設計對給定的n和s，尋找一種方案使得剩下的數字組成的新數最小。
● 設計思路：
在位數固定的前提下，讓高位的數字盡量小其值就較小，依據此貪心策略解決此問題。刪除高位較大的數字。具體：相鄰兩位比較若高位比低位大則刪除高位。
刪除字元的方法：
1）物理刪除，用後面的字元覆蓋已刪除的字元。有比較多字元移動操作，演算法效率不高。
2）用陣列記錄字元的狀態，「1」表示對應數字存在，「0」表示對應數字已刪除。
3） 利用陣列，記錄未刪除字元的下標：
n=「1 2 4 3 5 8 3 3」 0 0 0 0 0 0
4比3大刪除 「1 2 3 5 8 3 3」 1 2 4 5 0 0
8比3大刪除 「1 2 3 5 3 3」 1 2 4 5 0
5比3大刪除 「1 2 3 3 3」 1 2 4 7 8
2、程式**
c語言實現
三、測試用例
4、實驗總結
加深了對貪心演算法的理解與運用。
所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列區域性最優的選擇，即貪心選擇來達到。這是貪心演算法可行的第乙個基本要素，也是貪心演算法與動態規劃演算法的主要區別。動態規劃演算法通常以自底向上的方式解各子問題，而貪心演算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。
貪心演算法,過載問題
演算法設計與分析 上機實驗報告 1.上機題目及實驗環境 1.1上機題目 貪心演算法，過載問題 1.2實驗環境 cpu 英特爾第二代酷睿i3 2330m 2.2ghz 雙核 記憶體 4g 作業系統 window s 7 軟體平台 ubuntu 2.演算法設計與分析 1.用快速排序把隨機生成的一組數排序...
貪心演算法經典例題
所謂貪心演算法指的是為了解決在不回溯的前提之下，找出整體最優或者接近最優解的這樣一種型別的問題而設計出來的演算法。貪心演算法的基本思想是找出整體當中每個小的區域性的最優解，並且將所有的這些區域性最優解合起來形成整體上的乙個最優解。因此能夠使用貪心演算法的問題必須滿足下面的兩個性質 1.整體的最優解可...
中南大學演算法實驗報告
中南大學 演算法分析與設計 實驗報告 實驗一 歸併排序 編寫乙個簡單的程式，實現歸併排序 1 實驗目的 了解並熟練掌握歸併排序 2 實驗內容 給定乙個陣列，並使其按照所要求的顯示輸出 3 演算法思想分析 遞迴是簡單的方法，但是其不能很好的表示出歸併 非遞迴的方法能比較好的從底層開始顯示整個歸併排序的...