1、 算法设计与分析课程设计算法设计与分析课程设计 题 目：拼图游戏问题 专 业：xxx 学 号：xxx 姓 名： 指导老师：xxx 一一. .课程设计内容课程设计内容 问题描述问题描述: : 拼图游戏是很常见的而且很受欢迎的一种游戏。所谓拼图游戏， 是指将一个完整的图片分割成若干个规则的小图片， 然后将这些小图 片随机的拼接在一起。玩家按照原图，通过移动各个图片，然后重新 拼接出正确的图片 （1） 如何完成 N*N 拼图游戏当 N 较大时 10*10 （2） 在完成的基础上进行优化，使滑块移动次数较少（ 并非最优 算法） 问题分析问题分析 1、递归法：将拼图的第一行和第一列的滑块移动至正确的位置
2、，则 此 N*N 的拼图问题就转化成立（N-1）*（N-1）的问题，重复进行该 步骤 2、贪心算法 二二. .课程设计目的课程设计目的 1. 运用贪心算法的方法解决上述问题，设计出一个通过删除数 字，从输入的要删除的个数 s 中决定程序对正整数 n 的删除次数，每 次删除原数据中最大的最大数，使得剩下的书最小。 2.掌握贪心算法算法。 三算法原理三算法原理 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在 当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所 做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都 能得到整体最优解， 但对范围相当广泛的许多问题他能产生整
3、体最优 解或者是整体最优解的近似解。 贪心准则：贪心准则： 1、最近下降点优先 2、按照高位低位搜索递减区间，若存在递减区间，则删去该区间 的首字符；否则删去尾字符。 3、重复上述规则，删下一个字符，依此类推，直至删去k个字符为 止 四、四、贪心算法的基本思路贪心算法的基本思路 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 五
4、、程序流程图：五、程序流程图： Del(int D,int a10,int n)Del(int D,int a10,int n) MainMain（）（） 六源程序六源程序 #include int Del(int D,int a10,int n)/D 删除几位 a 数组 n 当前数组 位数 int res,max,i,j,x10; for(i=0;in;i+) xi=an-i-1; while(1) if(D=0) break; else D-; max=0; j=0; for(i=0;in;i+) if(maxxi) max=xi; j=i; / n=n-2; / for(i=j;in;i+) / xi=xi+1; / n+; n-; for(i=j;in;i+) xi=xi+1; res=0; for(i=0;in;i+) res=res*10+xi; return(res); void main
