程序设计导论——第16讲.ppt

递归(3);递归算法举例;递归算法举例;全排列问题;利用递归生成{1,2,3}的全排列的示意图;解题思路;解题思路（续）;要写出两个数（A1，A2）的全排列，那么此时可以分为两种情况： 第一种情况： A1第一个输出 此时接着输出A2的全排列即可 第二种情况： A2第一个输出 接着输出A1的全排列;可以猜想，每次对n个数（A1,A2,…,An）的全排列，可以分为n步 第1步为：以A1为第一个数，对余下的A2…An进行全排列 。。。。。。 第i步为：以Ai为第一个数，对余下的A1,A2…Ai-1,Ai+1…An进行全排列;根据这个思路，以3个数的全排列为例： 分别对A1，A2，A3这三种情况剩余的数列进行全排列的递推：;根据这个基本思路，在实际操作中还需要考虑如何将剩余的那一部分数列提供给接下来的一步操作/函数来调用的问题 这里采取交换的方法： 对于第i种情况，将A1与Ai交换位置，然后让接下来的全排列在后面n-1个数中进行 第i步： Swap（A1，Ai）//交换A1与Ai 交换前：A1,A2,…,Ai-1,Ai,Ai+1,…,An-1,An 交换后：Ai,A2,…,Ai-1,A1,Ai+1,…,An-1,An Perm（n-1，total） 输出后n-1个数的全排列 Swap（A1，Ai） //将A1与Ai交换回来 进行第i+1步……;;;;;产生n个元素的全排列;函数 void perm( int ary[], int setary[], int k, int nSize) 与或图:;//从k个元素setary[nSize-k+1],...,setary[nSize]中产生k个元素的全排列 void perm(int ary[], int setary[], int k, int nSize) { int i; if(k==1) { ary[nSize]=setary[nSize]; //只有1个元素 myOutput(ary, nSize); nTotal++; }else { for (i=nSize-k+1; i=nSize; i++) { ary[nSize-k+1] = setary[i]; //nSize-k+1个元素取setary[i]； swap(setary[i], setary[nSize-k+1]);//交换元素位置 perm(ary, setary, k-1, nSize); //求k-1个元素的全排列 swap(setary[i], setary[nSize-k+1]);//位置还原 } } } ;解题思路2;void perm(int ary[ ], int used[ ], int k) { int i; for (i=1; i=nSize; i++) //nSize是全局变量 { if ( used[i] ) continue; ary[k] = i; //变量k取值I used[i] = 1; if (k==nSize) //边界条件：nSize个变量都枚举完了 { myOutput(ary, nSize); //输出一组解 nTotal++; //解的个数加1 }else { perm(ary, list, k+1); //枚举k+1个变量 } used[i] = 0; } return; };;void perm(int ary[ ], int used[ ], int k) { int i; for (i=1; i=nSize; i++) { if (!used[i]) { ary[k]=i; used[i]=1; //标记i用过了 if (k==nSize) { myOutput(ary, nSize); nTotal++; }else { perm(ary, list, k+1); } list[i]=0; //取消i用过的标记 } } return; };课后思考