算法設(shè)計(jì)與分析課程設(shè)計(jì)---拼圖游戲問題

1、<p>　　算法設(shè)計(jì)與分析課程設(shè)計(jì)</p><p>　　題 目：拼圖游戲問題</p><p>　　專 業(yè)：xxx</p><p>　　學(xué) 號(hào)：xxx</p><p><b>　　姓 名：</b></p><p><b>　　指導(dǎo)老師：xxx</b&

2、gt;</p><p><b>　　一.課程設(shè)計(jì)內(nèi)容</b></p><p><b>　　問題描述:</b></p><p>　　拼圖游戲是很常見的而且很受歡迎的一種游戲。所謂拼圖游戲，是指將一個(gè)完整的圖片分割成若干個(gè)規(guī)則的小圖片，然后將這些小圖片隨機(jī)的拼接在一起。玩家按照原圖，通過移動(dòng)各個(gè)圖片，然后重新拼接出正確的圖片&

3、lt;/p><p>　　如何完成N*N拼圖游戲當(dāng)N較大時(shí)10*10</p><p>　　在完成的基礎(chǔ)上進(jìn)行優(yōu)化，使滑塊移動(dòng)次數(shù)較少（ 并非最優(yōu)算法）</p><p><b>　　問題分析</b></p><p>　　1、遞歸法：將拼圖的第一行和第一列的滑塊移動(dòng)至正確的位置，則此N*N的拼圖問題就轉(zhuǎn)化成立（N-1）*（N-1）

4、的問題，重復(fù)進(jìn)行該步驟</p><p><b>　　2、貪心算法</b></p><p><b>　　二.課程設(shè)計(jì)目的</b></p><p>　　1. 運(yùn)用貪心算法的方法解決上述問題，設(shè)計(jì)出一個(gè)通過刪除數(shù)字，從輸入的要?jiǎng)h除的個(gè)數(shù)s中決定程序?qū)φ麛?shù)n的刪除次數(shù)，每次刪除原數(shù)據(jù)中最大的最大數(shù)，使得剩下的書最小。</p

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

6、是整體最優(yōu)解的近似解。</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è)字符，依此類推，直

7、至刪去k個(gè)字符為止</p><p>　　四、貪心算法的基本思路</p><p>　　1.建立數(shù)學(xué)模型來描述問題。</p><p>　　2.把求解的問題分成若干個(gè)子問題。</p><p>　　3.對(duì)每一子問題求解，得到子問題的局部最優(yōu)解。</p><p>　　4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。</p

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

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

10、 Del(int D,int a[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];<

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

12、lse</b></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><

13、b>　　{</b></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><

14、;b>　　}</b></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>&l

15、t;b>　　//n++;</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&g

16、t;　　res=0;</b></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&

17、gt;<p><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>

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

19、<p>　　printf("請(qǐng)輸入要去掉數(shù)的位數(shù)S(S<=N):");</p><p>　　scanf("%d",&D);</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>

20、;<b>　　z=m/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&

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

22、gt;<p>　　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