湖南龙网

  1. 首页 > 生活百科 > >

要求效率不能太低 如何有效地确定递归公式远电眼圆双答夜振独依( 二 )

生活百科电眼


if(d==1){v=1;printf("%d->%d",f,t);}
elsev=h(d-1,f,u,t)+h(1,f,t,u)+h(d-1,u,t,f);
returnv;
}
此程序的运行会话如下：
disks=3
1->21->32->31->23->13->21->2
7actionsfor3disks!
3例子：八皇后问题
八皇后问题[2]是一个更有代表性更复杂的递归例题 ， 要求在8×8的国际象棋棋盘上摆
放8个皇后 ， 使她们不致互相攻击 。我们采取的算法仍然是从棋盘第一行开始每行放一
个皇后 ， 对于每一行都从该行的第一列开始放置 ， 并判断它同前面的那些皇后是否互相
攻击 ， 如是就换成下一列 ， 否则继续放置下一个皇后 ， 直至放好8个皇后 。依照这种思想 ， 
我们定义一个有9个自变量的函数:
q（k,a1,a2,a3,a4,a5,a6,a7,a8）
其中k表示已放置的皇后个数 ， 而ai（此处i<=k）表示第i行上的皇后所在列的列号 ， 因
此这9个自变量能够代表求解过程中任一时刻的状态 ， 而函数值定义为从此状态出发能
得到的解的个数 。按照这一思想不难得到下面的递归公式：
q（k,a1,...,ak,0,...0）=0如果有0<i<k,使ai同ak不相容
q（k,a1,...,a8）=1如果对于任意的0<i<8,ai同a8都相容
【要求效率不能太低 如何有效地确定递归公式远电眼圆双答夜振独依】q（k,a1,...,ak,0,...0）=q(k+1,a1,...,ak,1,...0）+...+q(k+1,a1,...,ak,8,...,0）
如果k<8而且对于任意的0<i<k,ai同ak都相容
公式中的“ai和ak相容”的意思是它们不互相攻击 ， 即逻辑表达式：
(ai-ak)&&(i+ai-k-ak)&&(i-ai-k+ak)
为真 ， 就是说ai≠ak且i+ai≠k+aki且i-ai≠k-ak 。将上面的递归公式很容易地翻译成如
下程序：
main()
{inta[9],v,q(int,int*);
v=q(0,a);
printf("\nThereare%dsolutions!\n",v);
}
intq(intk,int*a)
{inti,u,v;
for(i=1,u=1;i<k&&ui++)
u=u&&(a[i]-a[k])&&(i+a[i]-k-a[k])&&(i-a[i]-k+a[k]);
if(u==0)v=0;
elseif(k==8)
{v=1;printf("%d%d%d%d%d%d%d%d",
a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]);
}
else
for(i=1,v=0;i<=8;i++){a[k+1]=i;v+=q(k+1,a);}
returnv;
}
递归公式中的自变量a1,…,a8是一个相关的序列 ， 在程序中只好用数组a表示 。在q()中
首先计算ak是否同其前的所有ai相容 ， 若是变量u非0 。q()与递归公式严格对应 ， 呈现
出有三个选择的分支结构 。在u非0且k为8的情况下 ， 置函数值v为1 ， 并显示已得到的
解 。显然这个程序编写起来最为简单 ， 而且最好理解 。下面给出该程序的交互会话 ， 为
节省版面只列出92个解中的4个：
1586372416837425...8316257484136275
Thereare92solutions!
4结束语
公式化方法是一种简单而有效的设计思想 ， 它把程序设计和程序理解的难点都集中
到递归公式上 。从上面的例子可以看到这种思想能够简化程序设计 ， 而且得到的程序显然好于通常的程序 。这种思想有普遍性 ， 至少适用多数递归程序的设计 。由递归公式设计出的程序具有标准的分支结构 ， 编写和理解都要简单得多 。
上面的两个例题在求得函数值的同时 ， 很容易地得到了要求的序列 ， 但对于一般的
问题未必总是这样 。笔者曾给出一种伴随序列法 ， 可以用来得到某些问题（如显示所有从m个数中取n个数的组合）要求的序列 。

推荐阅读


上一篇：美国主要农业地域类型是什么

下一篇：标准的枕头高度是多少