數(shù)字刪除的貪心算法

1、題目：貪心算法求解數(shù)字刪除問(wèn)題學(xué)生姓名：唐健峰學(xué)生姓名：吳賀壽專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)（非師范班）指導(dǎo)老師：石春2016年12月16日Greedy algorithm to solve the problem of digital deleteAbstract:n the process of seeking the optimal solution of the problem, on thebasis of a greedy standard, starting from the initial state of the problem,to find the optimal solut

2、ion for each step, through several greedy selection, finally obtains the optimal solution to the problem, this method is a greedy algorithm. From the definition of the greedy algorithm can be seen, the greedy method is not to think about the problem from the whole, it is the choice made by the local

3、 optimum in the sense of the solution, and the characteristics of the problem itself determines the use of greedy algorithm can achieve the optimal solution. The selection of the greedy algorithm can rely on previously made choices, but it does not depend on the choice of the future, does not depend

4、 on the solution of sub problems, so the greedy algorithm and other algorithm has certain advantages compared to the speed. If a problem can be solved simultaneously in several ways, the greedy algorithm should be one of the best options. This paper first analyzes the digital delete problem, and the

5、n gives the greedy solution of the problem, finally proposed the time complexity of the algorithm is analyzed and the core of the problem, the greedy algorithm of the basic properties, characteristics and existing.Keyword: Greedy Algorithm , Digital deletion problem, Optimal solution problem , Compl

6、exity 。貪心算法求解數(shù)字刪除問(wèn)題摘要：在求最優(yōu)解問(wèn)題的過(guò)程中，依據(jù)某種貪心標(biāo)準(zhǔn)，從問(wèn)題的初始狀態(tài)出發(fā)，直接去 求每一步的最優(yōu)解，通過(guò)若干次的貪心選擇，最終得出整個(gè)問(wèn)題的最優(yōu)解，這種 求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考 慮問(wèn)題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問(wèn)題自身的特性決定了該題運(yùn)用貪心算法可以得到最優(yōu)解。 貪心算法所作的選擇可以依賴于以往 所作過(guò)的選擇，但決不依賴于將來(lái)的選擇，也不依賴于子問(wèn)題的解，因此貪心算 法與其它算法相比具有一定的速度優(yōu)勢(shì)。如果一個(gè)問(wèn)題可以同時(shí)用幾種方法解決,貪心算法應(yīng)該是最好的選擇之一。本文首先對(duì)數(shù)字刪除刪除

7、問(wèn)題進(jìn)行了分析， 然后給出了該問(wèn)題的貪心解法，最后對(duì)所提出算法的時(shí)間復(fù)雜度進(jìn)行了分析以及 貪心算法的核心、基本性質(zhì)、特點(diǎn)及其存在的問(wèn)題。關(guān)鍵字：貪心算法 數(shù)字刪除問(wèn)題 最優(yōu)解問(wèn)題 復(fù)雜度引言貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法，通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解，而它所做的每一次選擇都是當(dāng)前狀態(tài)下某種意義的 最好選擇，即貪心選擇。即希望通過(guò)問(wèn)題的局部最優(yōu)解來(lái)求出整個(gè)問(wèn)題的最優(yōu)解。這種策略是一種很簡(jiǎn)潔的方法，對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解，但不能保證總 是有效，因?yàn)樗皇菍?duì)所有問(wèn)題都能得到整體最優(yōu)解， 只能說(shuō)其解必然是最優(yōu)解 的很好近似值。1 .數(shù)字刪除問(wèn)題描述給定n位正整數(shù)

8、a,去掉其中任意k<=n （其中2<=n<=1000個(gè)數(shù)字后，剩下的 數(shù)字按原次序排列組成一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù)a和正整數(shù)k,設(shè)計(jì)一個(gè)算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。輸入輸入刪除位數(shù)輸出13245621234154789651214786541分析：n位數(shù)t可表示為x1,x2 , xi , xj , xk, ,xn,要?jiǎng)h去k位數(shù)，使得剩下的 數(shù)字組成的整數(shù)最小。設(shè)本問(wèn)題為S,其最優(yōu)解A=(y1 , y2, , yk)表示依次刪去的 k個(gè)數(shù)，在刪去k個(gè)數(shù)后剩下的數(shù)字按原次序排成的新數(shù)。即最優(yōu)值記為SA 本問(wèn)題采用貪心算法求解，采用最近下降點(diǎn)優(yōu)先的貪心策略

9、：即x1<x2<, <xi<xj ; 如果xk<xj ,則刪去xj ,即得到一個(gè)新的數(shù)且這個(gè)數(shù)為 n 1位中為最小的數(shù) Al,可表示為x1x2, xixkxm ,xn。對(duì)A1而言，即刪去了 1位數(shù)后，原問(wèn)題S變成 了需對(duì)n-1位數(shù)刪去k-1個(gè)數(shù)新問(wèn)題S'。新問(wèn)題和原問(wèn)題相同，只是問(wèn)題規(guī)模 由n減小為n-1 ,刪去的數(shù)字個(gè)數(shù)由k減少為k-1?；诖朔N刪除策略，對(duì)新問(wèn) 題S',選擇最近下降點(diǎn)的數(shù)進(jìn)行刪除，如此進(jìn)行下去，直至刪去k個(gè)數(shù)為止。2 .貪心算法2.1 貪心選擇性質(zhì)所謂的貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最的選擇。貪心選擇性質(zhì)

10、的證明。對(duì)問(wèn)題S刪除的最近的下降點(diǎn)的數(shù)xj后得到的N1是n-1 位數(shù)是中的最小的數(shù)。2.2 貪心選擇性質(zhì)證明：基本思路：考察一個(gè)問(wèn)題的最優(yōu)解，證明可修改的該最優(yōu)解是的使得其從貪 心選擇開(kāi)始，然后用數(shù)學(xué)歸納法證明每一步都可以通過(guò)貪心選擇得到最優(yōu)解。證明方法：1.假定首選定的元素不是貪心選擇所要的元素，證明將首要的元 素替換成貪心選擇所需要的元素，依然得到最優(yōu)解。2.數(shù)學(xué)歸納法證明每一步都可以通過(guò)貪心選擇得到的最優(yōu)解。 證明方法一：設(shè)問(wèn)題的S按照最近的下降點(diǎn)的方法刪除，A=(y1,y2,yk)是刪除數(shù)問(wèn) 題的一個(gè)最優(yōu)解。易知，若問(wèn)題有解，則 1<=k<=n.(1)當(dāng)k=1時(shí)，由前得證，

11、A=(y1,A')是問(wèn)題的最優(yōu)解；(2)當(dāng)k=1時(shí)，由反正法，得出A=(y1,y2,yq)是最優(yōu)解；當(dāng)k=q+1時(shí)，由前得證，A=(y1,y2,yq+yq+1)是最優(yōu)解。所以，最優(yōu)解再問(wèn)題具有貪心選擇性質(zhì)。證明方法二：設(shè)問(wèn)題S已經(jīng)按照最近下降點(diǎn)的方法刪除，A=(yi,y2, .,yk)將t這個(gè)十進(jìn)制數(shù)轉(zhuǎn)化為下形式：x1*10A(n-1)+x2*10A(n-2)+xi*10 A(n-i)+xj*10A(n-j)+xk*10A(n-k)+ +xn這樣的進(jìn)制數(shù)。則：N1=x1*10A(n-2)+x2*10A(n-3 )+ +xi*10 A(n-i-1)+xj*10A(n-j-1)+xk*10

12、A(n- k-1)+ -+xn；假設(shè)刪去的不是xj而是其他位，則有N2=x1*10A(n-2)+x2*10A(n-3)+ +xj*10A(n-k) + +xn 因?yàn)橛?x1<x2V<xi<x j and xj>xk,貝U有 N1<N2.所以數(shù)字刪除問(wèn)題滿足貪心選擇性質(zhì)。2.3最優(yōu)子結(jié)構(gòu)證明：在進(jìn)行了貪心選擇后，原問(wèn)題 T就變成了對(duì)N1如何刪去k-1個(gè)數(shù)的問(wèn)題， 是原問(wèn)題的子問(wèn)題。若 A=(xj , A')是原問(wèn)題T的最優(yōu)解，則A是子問(wèn)題了 的最優(yōu)解，其最值為TA'。證明：假設(shè)A不是子問(wèn)題的最優(yōu)解，其子問(wèn)題 的最優(yōu)解為B',其最優(yōu)值記為TB&

13、#39;,則有TB'TA'。而根據(jù)TA的定義可知： TA=TA，+xj*1On-j ,而 TB' <TA , IX 因此有 TB' +xj*1On-j<TA ' +xj*1On-j=TA。 即存在一個(gè)由數(shù)a刪去1位數(shù)后得到的n-1位數(shù)比最優(yōu)值TA更小。這與TA為問(wèn) 題T的最優(yōu)值相矛盾。因此，A是子問(wèn)題了的最優(yōu)值。因此，刪數(shù)問(wèn)題滿足 最優(yōu)子結(jié)構(gòu)性質(zhì)。從以上貪心選擇及最優(yōu)子結(jié)構(gòu)性質(zhì)的證明可知?jiǎng)h數(shù)問(wèn)題用貪心 算法可以求得最優(yōu)解。3.1 算法代碼分析#include<stdio.h> #include<string.h> vo

14、idzhuanhuan(int k, char a) while (k>0)inti = 0;/每次開(kāi)始將i初始化為0,表示重新開(kāi)始檢。.。測(cè)下降算法最為關(guān)鍵的部while (i<strlen(a) && ai <= ai + 1)i+;/for (int j = i; j <strlen(a); j+) aj = aj + 1;/ 覆蓋實(shí)現(xiàn)刪除效果k-; void main(void)int n, k;char a1000;/定義字符數(shù)組，最多可以存放 1000個(gè)數(shù)字printf(” 請(qǐng)輸入正整數(shù)m:");gets_s(a);n = strl

15、en(a);printf(" 該數(shù)m的位數(shù)有%d位",n);printf("n請(qǐng)輸入要?jiǎng)h除的k (正整數(shù))位的k:");scanf_s("%d", &k);while (k < 1 11k >= n)printf("你數(shù)輸入的有誤！n請(qǐng)重新再輸入k:");scanf_s("%d", &k);.printf(" 你要?jiǎng)h除%d位數(shù)之后的結(jié)果為:",k);zhuanhuan(k, a);/ 刪除后重新按原次序排列puts(a);3.2 實(shí)驗(yàn)環(huán)境：(a)數(shù)

16、據(jù)輸入：輸入數(shù)據(jù)第一行是一個(gè)整數(shù)m ,第二行是一個(gè)整數(shù) k,2<=n<=1000(b)數(shù)據(jù)輸出：輸出刪除后的數(shù)字(c)編程環(huán)境： Windows10 和 Microsoft Visual Studio 20133.3 算法流程3 .復(fù)雜度針對(duì)具體算法，分析復(fù)雜性。該部分內(nèi)容要有過(guò)程說(shuō)明。此貪心算法的時(shí)間復(fù)雜度有 whlile循環(huán)和for循環(huán)組成，所以此程序的時(shí)間復(fù)雜性為0mA2）,此程序的空間復(fù)雜性為0mA2）；總結(jié)：1）學(xué)習(xí)到了貪心算法的性質(zhì)（貪心選擇性質(zhì)和最優(yōu)質(zhì)3結(jié)構(gòu)性質(zhì)）以及貪心算法的證明。其中貪心算法的貪心性質(zhì)需要用數(shù)學(xué)歸納證明。證明每一步的所 做的貪選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解來(lái)解決問(wèn)題。2）在代碼方面，利用覆