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

1 递归程序设计递归算法实现的程序简洁、易读懂可以用来解决一些复杂的问题在使用Matlab软件进行递归程序设计当中，要特别注意的是：程序中一定要有返回语句(return)，以便使程序在适当的时候终止递归调用，否则会出现堆栈溢出，甚至导致程序中断退出为防止程序异常终止，可以添加异常处理代码(try…catch…end) 递归程序设计的第一步，要分析问题，建立问题求解的递推关系式或算法然后再进行程序设计实现1.1 计算阶乘从n个数中取n个数的数的全排列记为，且有 因此建立其求阶乘的递推关系式：，结束条件：计算阶乘的Matlab函数如下：function r=factorial(n)%计算n的阶乘if n==1 r=1; return endr=n*factorial(n-1);例子：再命令行输入factorial(3)则返回61.2 组合数学中的Pascal公式从n个数中取r个的组合数记为，且有，组合数学中又这样的Pascal公式：因此可以编写如下的函数求组合数：function num=getcom(n,r)if r==0 | (n==r) %结束条件 num=1; returnend if r==1,%2004-12-7add num=n; returnendnum=getcom(n-1,r)+getcom(n-1,r-1);1.3 汉诺塔问题1.3.1 “Hanoi塔”问题有3根柱子：A,B,C，现有n个大小不一的圆盘依半径的大小，从下而上套在柱子A上，最大的圆盘放在柱子A的最下面。

现要将所有的圆盘从柱子A移动到C柱子上，每次只允许从一根柱子转移到另一根柱子上，且在转移过程中不允许出现大圆盘放在小圆盘上B盘为可以利用的柱子，每次只允许移动一个盘子，请问要转移多少次才能将柱子A上的圆盘全部转移柱子C上？“Hanoi塔”是组合数学中的著名问题之一1.3.2 问题求解主程序调用：global nmovenmove=0;hanta(‘A’,’B’,’C’,3)nmove说明：上面的程序调用表示有3根柱子：A ,B,C，现有3个盘子在A上，要将其移动到C盘上，B盘为可以利用的柱子1.3.3 实现程序function hanta(posfrom,posmiddle,posend,numplate)global nmove%移动次数，调用nmove之前声明nmove为全局变量，且赋值为0if numplate==1 sprintf('从%s移到%s',posfrom,posend) nmove=nmove+1; returnendtry 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移到Cans =从A移到Bans =从C移到Bans =从A移到Cans =从B移到Aans =从B移到Cans =从A移到Cnmove =71.4 案例：商人安全过河问题三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行。

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货但是如何乘船渡河的大权掌握在商人们手中商人们怎样才能安全渡河呢？1.4.1 问题分析设商人某岸上的人数为x，随从人数为y；此岸彼岸商人与随从的人数必须满足以下下面其中一种情况：（1） x不等于0时，x>=y；（2） x等于0以上两种称为安全状态每次划行时做出决策：可能的决策必须满足两个条件：（1） 船上载人不超过2人；（2） 确保出发点岸上和到达对岸后，两岸的人数必须同时满足安全状态1.4.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)| (1,0),(0,1),(1,1),(2,0),(0,2)} （2）因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶回此岸，所以状态Sk，随决策dk变化的规律是Sk+1= Sk+(-1)k dk （3）如：（3）式称为状态转移律。

这样，制定安全渡河方案归结为如下的多步决策问题：求决策dk∈D（k=1,2,…,n），使状态Sk∈S按照转移规律（3）由初始状态S1=(3,3)经过有限步n到达状态Sn+1=(0,0)以上建立了一个简单的模型！但还没有求解1.4.3 模型求解如何求解上述模型？手工推算？还是借助计算机，通过设计求解算法来求解该问题？1.4.4 进一步的思考题1、 最少应划行多少次船才能过河？2、 总共有多少种过河方法？3、 还有无其他建模方法（还能否建立其他数学模型？比如图论模型）1.4.5 程序运行结果程序名：my_guohe_main（见后面）下面为程序中的注释，通过这个可以理解下面的运行结果输出思考题：请根据结果输出，将运行结果转化为文字叙述用于回溯的矩阵%mat_back = [阶段，状态（决策前），决策，阶段（决策后），状态（决策后），是否结束]%mat_back对应列序号： 1 2 3 4 5 6 7 8 9运行结果：ans = 129 9ans = 11 0 2 0 2 0 0 0 1 11 1 1 1 1 0 0 0 1 13 0 2 0 2 0 0 0 1 13 1 1 1 1 0 0 0 1 15 0 2 0 2 0 0 0 1第 1个策略cur_dec_seq = 1 3 3 1 1 2 2 2 0 2 2 2 1 0 3 3 2 0 3 3 2 0 2 4 3 0 0 4 3 0 0 1 5 3 1 0 5 3 1 2 0 6 1 1 0 6 1 1 1 1 7 2 2 0 7 2 2 2 0 8 0 2 0 8 0 2 0 1 9 0 3 0 9 0 3 0 2 10 0 1 0 10 0 1 0 1 11 0 2 0 11 0 2 0 2 0 0 0 1注：这里省略另外4个策略。

思考题：通过程序及其注释，分析结果输出的5种过河策略，并翻译为通俗易懂的过河策略注：对于一组确定的策略（比如上面的5种），实际上“第i行的第7,8列元素应该分别等于第i+1行的第2，3列元素”1.4.6 递归算法求解程序function my_guohe_main%2004-12-9 调试完毕，共有5种不同的决策clear allglobal fid numans mat_back%用于回溯的矩阵%mat_back = [阶段，状态（决策前），决策，阶段（决策后），状态（决策后），是否结束]%mat_back对应列序号： 1 2 3 4 5 6 7 8 9%状态和决策各2个元素存储mat_back=zeros(1,9);%init%"是否结束"：用1表示结束；0表示未结束；numans = 0 ;%决策序列个数fid = fopen('debug.txt','w');if fid < 3 disp('error open file') returnend%调用递归求解程序getd([3 3],1,[-1 -1 -1 -1],[-1 -1 -1 -1])fprintf(fid,'\nTotal ans num=%d',numans)fclose(fid)%mat_backsize(mat_back)%回溯得到过河策略mat_back = unique(mat_back,'rows');%消除重复行row_no=find(mat_back(:,9)==1);%最后一步决策mat_back(row_no,:)for i=1:length(row_no),%逐个回溯最优解 disp(sprintf('第%4d个策略',i)) cur_step_status=mat_back(row_no(i),1:3); step = mat_back(row_no(i),1); %决策序列 cur_dec_seq(step,:)= mat_back(row_no(i),1:9); %只要还没有到初态【3，3】，则继续回溯 while ~vec_equal(cur_step_status(2:3),[3 3]), id_mat= find(mat_back(:,9)~=1);%%?2004-12-9 mid_mat_back= mat_back(id_mat,[6 7 8]); %oldversion:[r,id]=vec_in_ma。