四、排列问题的递归算法_第1页
四、排列问题的递归算法_第2页
四、排列问题的递归算法_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

排列问题的递归算法本文的关键目标是设计并实现排列问题的递归算法。该文主要是为了解决如何利用递归规则来解决排列n个元素的问题。该文中介绍了递归算法的基本思想，还向读者阐述了排列问题的递归算法的实现。最后本文还对这个算法进行了一些详细的分析。关键词：全排列；算法；递归问题描述对于给定的集合A{a1,a2,...,an},其中的n个元素互不相同，如何输出这n个元素的所有排列(全排列)。问题分析常用的全排列四种算法：字典序法递增进位制数法递减进位制数法邻位对换法本文采用可以采用树的结构表示全排列生成算法，以数字的全排列生成算法为例，从最小的数1开始，其全排列只有一种可能；加入数字2，数字2可以插入在1的后边或前边，有两个不同位置;再加入3,对于第二层中的每一种不同排列，都可以通过将3插入不同位置得到三种不同的排列数，共有6种排列数;依次类

推可以得到多个数的全排列。算法描述这里以A{a,b,c}为例，来说明全排列的生成方法，对于这个集合，其包含3个元素，所有的排列情况有3!=6种，对于每一种排列，其第一个元素有3种选择a,b,c，对于第一个元素为a的排列，其第二个元素有2种选择b,c；第一个元素为b的排列，第二个元素也有2种选择a，c，，依次类推，我们可以将集合的全排列与一棵多叉树对应。如右图所示：在此树中，每一个从树根到叶子节点的路径，就对应了集合A的一个排列。通过递归算法，可以避免多叉树的构建过程，直接生成集合A的全排列，代码如下。具体算法4.2线性查找的非递归算法4.1线性查找的递归算法template<typenameT>inlinevoidswap(T*array,unsignedinti,unsignedintj)//交换{Tt=array[i];array[i]=array[j];array[j]=t;}/**递归输出序列的全排列*/voidFullArray(char*array,size_tarray_size,unsignedintindex){if(index>=array_size){for(unsignedinti=0;i<array_size;++i){cout<<array[i]<<'';}cout<<'\n';return;}for(unsignedinti=index;i<array_size;++i){swap(array,i,index);FullArray1(array,array_size,index+1);//递归调用swap(array,i,index);//将交换位置的元素还原}}结果分析该算法使用原始的集合数组array作为参数，将i位置的元素，与index位置的元素交换的目的是使得array[index+1]到array[n]的所有

人人文库> 全部分类> 行业资料 > 机电工程

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论