算法設(shè)計(jì)與分析課程設(shè)計(jì)--刪數(shù)問題

1、<p>　　算法設(shè)計(jì)與分析課程設(shè)計(jì)</p><p>　　題 目：刪數(shù)問題</p><p>　　專 業(yè)：信息與計(jì)算科學(xué)</p><p><b>　　一.課程設(shè)計(jì)內(nèi)容</b></p><p><b>　　問題描述:</b></p><p>　　鍵盤輸入一個高

2、精度的正整數(shù)n（n<10位）去掉任意s個數(shù)字后剩下的數(shù)字按原左右次序組成一個新的正整數(shù)。編程對給定的n和s，尋找一種方案，使得剩下的數(shù)最小。</p><p><b>　　問題分析</b></p><p>　　1、貪心法求解：刪k個數(shù)符的全局最優(yōu)解，包含了刪除1個數(shù)符的子問題的最優(yōu)解。</p><p>　　2、以字串形式輸入a，使用盡可能逼

3、近目標(biāo)的貪心法來逐一刪去其中的k個數(shù)符，每一步總是選擇一個能使剩下的數(shù)最小的數(shù)符刪去。</p><p><b>　　二.課程設(shè)計(jì)目的</b></p><p>　　1. 運(yùn)用貪心算法的方法解決上述問題，設(shè)計(jì)出一個通過刪除數(shù)字，從輸入的要刪除的個數(shù)s中決定程序?qū)φ麛?shù)n的刪除次數(shù)，每次刪除原數(shù)據(jù)中最大的最大數(shù)，使得剩下的書最小。</p><p>　

4、　2.掌握貪心算法算法。</p><p><b>　　三．算法原理</b></p><p>　　貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。</

5、p><p><b>　　貪心準(zhǔn)則：</b></p><p><b>　　1、最近下降點(diǎn)優(yōu)先</b></p><p>　　2、按照高位→低位搜索遞減區(qū)間，若存在遞減區(qū)間，則刪去該區(qū)間的首字符；否則刪去尾字符。</p><p>　　3、重復(fù)上述規(guī)則，刪下一個字符，依此類推，直至刪去k個字符為止</p&

6、gt;<p>　　四、貪心算法的基本思路</p><p>　　1.建立數(shù)學(xué)模型來描述問題。</p><p>　　2.把求解的問題分成若干個子問題。</p><p>　　3.對每一子問題求解，得到子問題的局部最優(yōu)解。</p><p>　　4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。</p><p>&

7、lt;b>　　實(shí)現(xiàn)該算法的過程：</b></p><p>　　從問題的某一初始解出發(fā)；</p><p>　　while 能朝給定總目標(biāo)前進(jìn)一步 do</p><p>　　求出可行解的一個解元素；</p><p>　　由所有解元素組合成問題的一個可行解。</p><p><b>　　五、程序流

8、程圖：</b></p><p>　　Del(int D,int a[10],int n) Main（）</p><p><b>　　六．源程序</b></p><p>　　#include<stdio.h></p><p>　　int Del(int D,int a

9、[10],int n)//D 刪除幾位 a 數(shù)組 n 當(dāng)前數(shù)組位數(shù)</p><p><b>　　{</b></p><p>　　int res,max,i,j,x[10];</p><p>　　for(i=0;i<n;i++)</p><p>　　x[i]=a[n-i-1];</p><p>

10、;<b>　　while(1)</b></p><p><b>　　{</b></p><p><b>　　if(D==0)</b></p><p><b>　　break;</b></p><p><b>　　else</b><

11、;/p><p><b>　　D--;</b></p><p><b>　　max=0;</b></p><p><b>　　j=0;</b></p><p>　　for(i=0;i<n;i++)</p><p><b>　　{</b&g

12、t;</p><p>　　if(max<x[i])</p><p><b>　　{</b></p><p><b>　　max=x[i];</b></p><p><b>　　j=i;</b></p><p><b>　　}</b&

13、gt;</p><p><b>　　}</b></p><p><b>　　//n=n-2;</b></p><p>　　//for(i=j;i<n;i++)</p><p>　　//x[i]=x[i+1];</p><p><b>　　//n++;

14、</b></p><p><b>　　n--;</b></p><p>　　for(i=j;i<n;i++)</p><p>　　x[i]=x[i+1];</p><p><b>　　}</b></p><p><b>　　res=0;</b

15、></p><p>　　for(i=0;i<n;i++)</p><p>　　res=res*10+x[i];</p><p>　　return(res);</p><p><b>　　}</b></p><p>　　void main()</p><p>&l

16、t;b>　　{</b></p><p>　　int Res,D,z,n,m,i,a[10];</p><p>　　//m=43252556;</p><p><b>　　i=0;</b></p><p><b>　　n=0;</b></p><p>　　pr

17、intf("<------------------刪數(shù)問題---------------------->\n");</p><p>　　printf("請輸入一個高精度的正整數(shù)N(N<=10位):");</p><p>　　scanf("%d",&m);</p><p>　　pri

18、ntf("請輸入要去掉數(shù)的位數(shù)S(S<=N):");</p><p>　　scanf("%d",&D);</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p><b>　　z=m/

19、10;</b></p><p>　　a[i]=m-z*10;</p><p><b>　　m=z;</b></p><p><b>　　i++;</b></p><p><b>　　n++;</b></p><p><b>　　if

20、(m==0)</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　Res=Del(D,a,n);</p><p>　　printf("刪除后的結(jié)果為:");</p><p>　　

21、printf("%d\n",Res);</p><p><b>　　}</b></p><p><b>　　七．程序運(yùn)行結(jié)果</b></p><p>　　八．算法時空復(fù)雜度分析</p><p>　　此貪心算法的時間復(fù)雜度有while循環(huán)和for循環(huán)組成，所以此程序的時間復(fù)雜度