递归程序设计与优化模型及其求解.doc

递归程序设计 递归算法实现的程序简洁、易读懂。可以用来解决一些复杂的问题。 在使用Matlab软件进行递归程序设计当中，要特别注意的是：程序中一定要有返回语句(return)，以便使程序在适当的时候终止递归调用，否则会出现堆栈溢出，甚至导致程序中断退出。为防止程序异常终止，可以添加异常处理代码(try…catch…end)。 递归程序设计的第一步，要分析问题，建立问题求解的递推关系式或算法。然后再进行程序设计实现。 计算阶乘 从n个数中取n个数的数的全排列记为，且有。 因此建立其求阶乘的递推关系式：，结束条件：。 计算阶乘的Matlab函数如下： function r=factorial(n) %计算n的阶乘 if n==1 r=1; return end r=n*factorial(n-1); 例子： 再命令行输入factorial(3)则返回6 组合数学中的Pascal公式 从n个数中取r个的组合数记为，且有，。 组合数学中又这样的Pascal公式： 。 因此可以编写如下的函数求组合数： function num=getcom(n,r) if r==0 | (n==r) %结束条件 num=1; return end if r==1,%2004-12-7add num=n; return end num=getcom(n-1,r)+getcom(n-1,r-1); 汉诺塔问题 “Hanoi塔”问题 有3根柱子：A,B,C，现有n个大小不一的圆盘依半径的大小，从下而上套在柱子A上，最大的圆盘放在柱子A的最下面。现要将所有的圆盘从柱子A移动到C柱子上，每次只允许从一根柱子转移到另一根柱子上，且在转移过程中不允许出现大圆盘放在小圆盘上。B盘为可以利用的柱子，每次只允许移动一个盘子，请问要转移多少次才能将柱子A上的圆盘全部转移柱子C上？ “Hanoi塔”是组合数学中的著名问题之一。 问题求解 主程序调用： global nmove nmove=0; hanta(‘A’,’B’,’C’,3) nmove 说明：上面的程序调用表示有3根柱子：A ,B,C，现有3个盘子在A上，要将其移动到C盘上，B盘为可以利用的柱子。 实现程序 function hanta(posfrom,posmiddle,posend,numplate) global nmove%移动次数，调用nmove之前声明nmove为全局变量，且赋值为0 if numplate==1 sprintf(从%s移到%s,posfrom,posend) nmove=nmove+1; return end try hanta(posfrom,posend,posmiddle,numplate-1) sprintf(从%s移到%s,posfrom,posend) nmove=nmove+1; hanta(posmiddle,posfrom,posend,numplate-1) catch catch error end 实例：当有3个盘子时，该递归程序的输出为： ans = 从A移到C ans = 从A移到B ans = 从C移到B ans = 从A移到C ans = 从B移到A ans = 从B移到C ans = 从A移到C nmove = 7 案例：商人安全过河问题 三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全渡河呢？ 问题分析 设商人某岸上的人数为x，随从人数为y； 此岸彼岸商人与随从的人数必须满足以下下面其中一种情况： x不等于0时，x=y； x等于0 以上两种称为安全状态。 每次划行时做出决策： 可能的决策必须满足两个条件： 船上载人不超过2人； 确保出发点岸上和到达对岸后，两岸的人数必须同时满足安全状态 模型建立 设第k次渡河前此岸的商人数为xk，随从人数为yk，k=1,2,……, xk，yk=0,1,2,3. 将二维向量Sk=(xk，yk)定义为状态（即第k-1次渡河后的此岸状态）。安全渡河条件下的状态几何称为允许状态集合，记作S，根据问题分析很容易得到 S＝{(x,y)|(0,0),(0,1),(0,2),(0,3),(1,1),(2,2)(3,0),(3,1),(3,2),(3,3) } （1） 注：为什么不能取(1,0),(2,0),(2,1)? 记第k次渡船上的商人数为uk，随从数为vk，将二维向量dk={ uk，vk}定义为决策。允许决策集合记作D，由小船的容量可知 D＝{(u,v)|