文档介绍：该【函数的递归调用与分治策略】是由【森林书屋】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【函数的递归调用与分治策略】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。函数的用与分治策略
方法是算法和程序中的一种重要技。方法即通函数或程用
自身将化本相同但模小的子。方法具有易于描述和理解、
明等点,在划、心算法、回溯法等多算法中都有着极广泛的用,是多复算法的基。方法中所使用的“分而治之”的策略也称分治策略。
方法的构造
构造方法的关在于建立关系。里的关系可以是描述的,也
可以是推描述的。下面由一个求n的乘的程序例,出构造方法的一般步。
[例1]从入正整数 N(0<=N<=20),出N!。
[分析]N!的算是一个典型的。使用方法来描述程序,十分且
易于理解。
[

步

1]

描述关系

关系是的一种关系。

{U1,U2,U3,

⋯,Un⋯}是一
个序列,如果从某一

k开始,

Un和它之前的若干之存在一种只与

n有关的
关系,便称关系。
注意到,当 N>=1,N!=N*(N-1)! (N=1,0!=1),就是一种关系。于
特定的K!,它只与K与(K-1)! 有关。
[步2]确定界在步1的关系中,大于k的Un的求解将最Uk的求解。里的Uk称界(或出口)。在本例中,界k=0,即0!=1。于任意定的N!,程序将最求解到0!。
确定递归边界十分重要,如果没有确定递归边界,将导致程序无限递归而引起死
循环。例如以下程序:
#include<>
intf(intx){
return(f(x-1));
}
main(){
cout<<f(10);
}
它没有规定递归边界,运行时将无限循环,会导致错误。
[步骤3]写出递归函数并译为代码将步骤1和步骤2中的递归关系与边界统一起
来用数学语言来表示,即
N*(N-1)! 当N>=1时
n!=
1 当N=0时
再将这种关系翻译为代码,即一个函数:
longf(intn){
if(n==0)
return(1);
else
return(n*f(n-1));
}
[步骤4]完善程序主要的递归函数已经完成,将程序依题意补充完整即可。
ey>
j--;
if(i<j)
{
R[i]=R[j];
i++;
}
while(i<j&&R[i].key<
i++;
if(i<j)
{
R[j]=R[i];
j--;
}
}
R[i]=temp;
QuickSort(R,s,i-1);
QuickSort(R,i+1,t);
}
}
[ 例6]“九宫阵”智力游戏。
[描述]一个9×9方,由9个“九格”成,每个九格又由
3×3共9
个小格子成。在每个空白小格子里面填上 1~9的数字,使每个数字在每个九
格内以及在整个九中的每行、每列上均出一次。
1)程将下面中的九充完整。
2)是否可能出“九”的全部解?
[分析]本可利用回溯法解决,其基本思想深度先搜索( DFS),也是一种
以分治策略基的算法。回溯法与粹的 DFS不同的是,它在搜索程中不断
死不合意的点。一点保了解法的效率。
首先考如何得出全部解的情况。
解空容易构造,只需按序(从第一行第一个数字开始到第一行最后一个,
然后第二行⋯⋯,一直到最后一行最后一个数字) “”填入数字即可。
了解决个,我需要先写一个函数 check,其原型 intcheck(int
i,intj,intk) ,用于求第i行第j列能否填上数字 k。如果可以,返回 1,否
返回0。由于我是按序填入数字的, 看起来一个数字后面的数字并不在判断能
否填的范内。但了解决中某个特解的方便,是引入的判断
方法。
函数check代如下:
intcheck(inti,intj,intk){
intl,m,pi,pj;
Checktheline
for(l=1;l<=9;l++)
if((l!=j)&&(a[i][l]!=0)&&(a[i][l]==k))
return(0);
Checkthecolumn
for(l=1;l<=9;l++)
if((l!=i)&&(a[l][j]!=0)&&(a[l][j]==k))
return(0);
Checkthe3x3matrix
Checktheline
for(l=1;l<=9;l++)
if((l!=j)&&(a[i][l]!=0)&&(a[i][l]==k))
return(0);
Checkthecolumn
for(l=1;l<=9;l++)
if((l!=i)&&(a[l][j]!=0)&&(a[l][j]==k))
return(0);
Checkthe3x3matrix
Firstlywewillhavetochecktheparent_i(pi)andparent_j(pj)if(i<=3)pi=1;
elseif(i<=6)pi=4;elsepi=7;
if(j<=3)pj=1;elseif(j<=6)pj=4;elsepj=7;
//Nowwecancheckit
for(l=0;l<=2;l++)
for(m=0;m<=2;m++){
if(((pi+l)!=i)&&((pj+m)!=j))
if((a[pi+l][pj+m]!=0)&&(a[pi+l][pj+m]==k))
return(0);
}
return(1);
}
voidoutput(){
inti,j;
cout<<"Onesolutionis:"<<endl;
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
cout<<a[i][j]<<"";
cout<<endl;
}
}
voidbacktrack(inti,intj,intk){
intl;
if(check(i,j,k)==1)
{
a[i][j]=k;//Fillintheokaysolution
//Generatenexti,j
do{
if(j<9)j++;
else{i++;j=1;}
}while(a[i][j]!=0);//EndofGeneratenexti,jif(i<10)
{
for(l=1;l<=9;l++)backtrack(i,j,l);
}
elseoutput();
a[i][j]=0;/*Whenfails andgoesupperwards,
}

thevalue

mustbecleared*/
}
voidinit(){
a[1][2]=9;a[1][6]=4;a[1][7]=5;a[1][9]=7;
a[2][3]=3;a[2][5]=7;a[2][6]=9;a[2][7]=4;
a[3][4]=3;a[3][5]=6;a[3][8]=8;a[3][9]=9;
a[4][1]=3;a[4][4]=1;
a[5][3]=4;a[5][8]=2;a[5][9]=3;
a[6][2]=1;a[6][3]=2;a[6][6]=3;
a[7][1]=8;a[7][8]=5;
a[8][2]=6;a[8][4]=2;a[8][5]=9;
a[9][2]=2;a[9][3]=1;a[9][7]=8;
//memset(a,0,sizeof(a));
}
intmain(){
inti;
for(i=1;i<=9;i++){
init();
backtrack(1,1,i);
}
system("PAUSE");
return0;
}
递归方法在算法与数据结构中的应用无所不在,如动态规划(状态方程) 、回溯
法(深度优先搜索)等等,以上两例只是冰山一角。只有熟悉掌握函数递归调用
的编程方法,深入理解分治策略的重要思想,才能编写出功能强大、高效简明的
程序。