算法設計與分析課程設計---拼圖游戲問題

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

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

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

4、的問題，重復進行該步驟</p><p><b>　　2、貪心算法</b></p><p><b>　　二.課程設計目的</b></p><p>　　1. 運用貪心算法的方法解決上述問題，設計出一個通過刪除數字，從輸入的要刪除的個數s中決定程序對正整數n的刪除次數，每次刪除原數據中最大的最大數，使得剩下的書最小。</p

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

6、是整體最優(yōu)解的近似解。</p><p><b>　　貪心準則：</b></p><p><b>　　1、最近下降點優(yōu)先</b></p><p>　　2、按照高位→低位搜索遞減區(qū)間，若存在遞減區(qū)間，則刪去該區(qū)間的首字符；否則刪去尾字符。</p><p>　　3、重復上述規(guī)則，刪下一個字符，依此類推，直

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

8、><p><b>　　實現該算法的過程：</b></p><p>　　從問題的某一初始解出發(fā)；</p><p>　　while 能朝給定總目標前進一步 do</p><p>　　求出可行解的一個解元素；</p><p>　　由所有解元素組合成問題的一個可行解。</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 數組 n 當前數組位數</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("<------------------刪數問題---------------------->\n");</p><p>　　printf("請輸入一個高精度的正整數N(N<=10位):");</p><p>　　scanf("%d",&m);</p>

19、<p>　　printf("請輸入要去掉數的位數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("刪除后的結果為:");</p&

22、gt;<p>　　printf("%d\n",Res);</p><p><b>　　}</b></p><p><b>　　七．程序運行結果</b></p><p>　　八．算法時空復雜度分析</p><p>　　此貪心算法的時間復雜度有while循環(huán)和for