MATLAB讲稿_6-综合编程讲述.ppt

MATLAB的使用 第六章：复杂编程 MATLAB程序设计基础 1、汉诺塔 汉诺塔问题汉诺塔（又称河内塔）问题其实是印度的一个古老的传说。 开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。可以计算一下，即使人用最快的速度移动圆片，也要用几百亿年才能完成上面数字所代表的次数。 MATLAB程序设计基础 1.1 算法一 一位美国学者发现了一种非常简单的算法。 当盘子的个数为n时，移动的次数应等于2^n – 1（有兴趣的可以自己证明试试看）。 只要轮流进行两步操作就可以了。 首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，则按逆时针方向依次摆放A B C。 MATLAB程序设计基础 （1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。 （2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。 反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。 MATLAB程序设计基础 1.2 算法二 汉诺塔问题也是程序设计中的经典递归问题。 递归算法见程序 下面分别是使用递归算法、非递归算法编写的程序执行的结果。 MATLAB程序设计基础 2、N皇后问题 第五种程序执行流程：函数调用 这种流程与跳转有所不同，需要保存主调函数运行环境。 MATLAB程序设计基础 MATLAB程序设计基础 MATLAB程序设计基础 MATLAB程序设计基础 三种基本数据结构 线性 树 图 MATLAB程序设计基础 程序执行流与数据流 [count,res]=queen_solve(1,4,[],0,[]) queen_checkValidate(1,1,[]) 1 [count,res]=queen_solve(2,4,[1],0,[]) 2 queen_checkValidate(2,1,[1]) 3 4 queen_checkValidate(2,2,[1]) 5 6 queen_checkValidate(2,3,[1]) 7 [count,res]=queen_solve(3,4,[1,3],0,[]) 8 queen_checkValidate(3,1,[1,3]) 9 10 queen_checkValidate(3,2,[1,3]) 11 12 queen_checkValidate(3,3,[1,3]) 13 14 queen_checkValidate(3,4,[1,3]) 15 16 17 queen_checkValidate(2,4,[1]) 18 queen_checkValidate(1,4,[]) queen_checkValidate(1,3,[]) queen_checkValidate(1,2,[]) MATLAB程序设计基础 [count,res]=queen_solve(i,n,curPath,count,data) i=n j=n j=1 queen_checkValidate((i,j,curPath) curPath(i)=j [count,res]=queen_solve(i+1,n,curPath,count,data) count=count+1; data{count}=curPath; j=j+1 queen_solve函数程序流程图 MATLAB程序设计基础 queen_checkValidate函数程序流程图 queen_checkValidate((i,j,curPath) k=i-1 k=1 curPath(k)==j res=0; i-k==abs(j-curPath(k)) res=0; res=1 K=k+1 MATLAB程序设计基础 执行结果 MATLAB程序设计基础 3、俄罗斯方块 俄罗斯方块游戏，程序文件夹Tetris，函数列表： Tetris_Main 主函数 Tetris_View 视图函数，相当于用