欢迎来到天天文库
浏览记录
ID:35626878
大小:52.50 KB
页数:8页
时间:2019-04-03
《算法设计与分析课程设计--拼图游戏问题》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
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;i5、i++){if(max6、------------------>");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河北联合大学理学院
5、i++){if(max6、------------------>");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河北联合大学理学院
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河北联合大学理学院
此文档下载收益归作者所有