算法设计与分析课程设计--拼图游戏问题

《算法设计与分析课程设计--拼图游戏问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、河北联合大学理学院算法设计与分析课程设计题目：拼图游戏问题专业：xxx学号：xxx姓名：指导老师：xxx河北联合大学理学院一.课程设计内容问题描述:拼图游戏是很常见的而且很受欢迎的一种游戏。所谓拼图游戏，是指将一个完整的图片分割成若干个规则的小图片，然后将这些小图片随机的拼接在一起。玩家按照原图，通过移动各个图片，然后重新拼接出正确的图片（1）如何完成N*N拼图游戏当N较大时10*10（2）在完成的基础上进行优化，使滑块移动次数较少（并非最优算法）问题分析1、递归法：将拼图的第一行和第一列的滑块移动至正确的位置，则此N

2、*N的拼图问题就转化成立（N-1）*（N-1）的问题，重复进行该步骤2、贪心算法二.课程设计目的1.运用贪心算法的方法解决上述问题，设计出一个通过删除数字，从输入的要删除的个数s中决定程序对正整数n的删除次数，每次删除原数据中最大的最大数，使得剩下的书最小。2.掌握贪心算法算法。三．算法原理河北联合大学理学院贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许

3、多问题他能产生整体最优解或者是整体最优解的近似解。贪心准则：1、最近下降点优先2、按照高位→低位搜索递减区间，若存在递减区间，则删去该区间的首字符；否则删去尾字符。3、重复上述规则，删下一个字符，依此类推，直至删去k个字符为止四、贪心算法的基本思路1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；河北联合大学理学

4、院由所有解元素组合成问题的一个可行解。五、程序流程图：河北联合大学理学院Del(intD,inta[10],intn)Main（）河北联合大学理学院河北联合大学理学院六．源程序河北联合大学理学院#includeintDel(intD,inta[10],intn)//D删除几位a数组n当前数组位数{intres,max,i,j,x[10];for(i=0;i

5、i++){if(max

6、------------------>");printf("请输入一个高精度的正整数N(N<=10位):");scanf("%d",&m);printf("请输入要去掉数的位数S(S<=N):");scanf("%d",&D);while(1){z=m/10;a[i]=m-z*10;m=z;i++;n++;if(m==0)break;}Res=Del(D,a,n);printf("删除后的结果为:");printf("%d",Res);}河北联合大学理学院河北联合大学理学院七．程序运行结果8河北联合大学理学院河

7、北联合大学理学院8河北联合大学理学院河北联合大学理学院8河北联合大学理学院河北联合大学理学院八．算法时空复杂度分析此贪心算法的时间复杂度有while循环和for循环组成，所以此程序的时间复杂度为O（n^2）此算法的空间复杂度为O（n^2）九.工具软件及运行环境1.工具软件：MicrosoftVisualC++6.02.运行环境：Win32ConsoleApplication8河北联合大学理学院