注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mihooke's blog

IT之恋

 
 
 

日志

 
 

全排列递归算法  

2014-07-01 10:33:11|  分类: 学习录 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

首先,我们对递归算法肯定是熟悉得很,因为递归算法思想很简单,可读性强。递归的程序是自身调用自身,执行完之后然后才返回到调用点的下条语句,在这可能有个疑问,就是返回的时候如何知道返回地址呢?我们了解了栈的原理之后就会明白递归原理。实际上,递归函数在执行过程中,调用函数和被调用函数之间的信息传递和控制转移完全是通过栈来实现的。

每次递归函数调用时,都会:

  • 将返回地址、形参、局部变量等值压入栈。
  • 将形参等值传递给被调函数,并转到被调函数入口处开始执行。
每次调用结束,都会:

  • 从栈顶取出被保存的信息赋给相应的变量。
  • 转到刚取出值的返回地址。
当然我们在运行程序的时候是观察不到这些顺序的,这都是由系统来处理的。就拿n!来说吧,fact(n)。

全排列递归算法 - mihooke - mihooke的博客
 分析完这个这个过程,我相信理解递归原理就简单了吧。

接下来我们用递归分析一道算法题---全排列问题。全排列就是n个元素按照一定得顺序排列起来,有n!种排法。例如,[1,2,3]的全排列为[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1][3,1,2]、[3,2,1]。怎么用递归去分析这道题呢?可以这样想,全排列可以小分为以每个元素开头的除去这个元素的全排列,依次向下细分……不就可以用递归去解决了么。用ri表示要排到首位的元素,用Ri表示除去ri元素的集合,那么perm(X)表示全排列,(ri)perm(X)表示全排列perm(X)的每一个排列前加上排到首位元素的排列。算法代码如下:

void fact(int n)

{

if(n==0)

  return 1;

else

  return (n*fact(n-1));

}

void swap(int a[],int i,int j)

//数组中2个元素交换位置

{

int temp;

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

void perm(int list[],int m,int n)

{

int i;

if(m==n) //k==m表示数组中有一个元素,直接输出

{

  for(i=0;i<n;i++)

  printf("%d", list[i]);

  printf("\n");

}

else

{

  for(i=m;i<=n;i++)

  {

swap(list,m,i); //依次将ri移至数组第一个位置

perm(list,m+1,n);//递归求perm(Ri)

swap(list,m,i);//ri换回原位置

  }

}

}

  评论这张
 
阅读(33)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017