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

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

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

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

4、　2.掌握貪心算法算法。</p><p><b>　　三．算法原理</b></p><p>　　貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(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ī)則，刪下一個(gè)字符，依此類推，直至刪去k個(gè)字符為止</p&

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

7、lt;b>　　實(shí)現(xiàn)該算法的過(guò)程：</b></p><p>　　從問(wèn)題的某一初始解出發(fā)；</p><p>　　while 能朝給定總目標(biāo)前進(jìn)一步 do</p><p>　　求出可行解的一個(gè)解元素；</p><p>　　由所有解元素組合成問(wèn)題的一個(gè)可行解。</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ù)問(wèn)題---------------------->\n");</p><p>　　printf("請(qǐng)輸入一個(gè)高精度的正整數(shù)N(N<=10位):");</p><p>　　scanf("%d",&m);</p><p>　　pri

18、ntf("請(qǐng)輸入要去掉數(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>　　八．算法時(shí)空復(fù)雜度分析</p><p>　　此貪心算法的時(shí)間復(fù)雜度有while循環(huán)和for循環(huán)組成，所以此程序的時(shí)間復(fù)雜度