用递劃归技术求解汉诺塔问题 ?算法设计思路 ·当n=1时，问题可以直接求解，一步完成 。当n>1时，分三步完成： >将n-1个较小盘子设法移动到辅助塔座 一构造出一个比原问题规模小1的问题 >将最大的盘子从原塔座一步移至目标塔座 >将-1个较小的盘子设法从辅助塔座移至目标塔座 一仍然是比原问题规模小1的问题
用递归技术求解汉诺塔问题 算法设计思路 ⚫ 当n=1时，问题可以直接求解，一步完成 ⚫ 当n>1时，分三步完成： ➢ 将n-1个较小盘子设法移动到辅助塔座 ━ 构造出一个比原问题规模小1的问题 ➢ 将最大的盘子从原塔座一步移至目标塔座 ➢ 将n-1个较小的盘子设法从辅助塔座移至目标塔座 ━ 仍然是比原问题规模小1的问题
汉诺塔问题的递！归算法 void hanoi (int n,int src,int tar,int aux){ if(n>0){ hanoi(n-1,src,aux,tar); move(src,tar); hanoi(n-1,aux,tar,src); } 其中：hanoi(intn,int src,int tar,,int aux)表示将塔座src上 的n个盘子移动到塔座tar,以塔座aux为辅助(auxiliary)
汉诺塔问题的递归算法 其中：hanoi(int n, int src, int tar, int aux) 表示将塔座src上 的n个盘子移动到塔座tar，以塔座aux为辅助（auxiliary） void hanoi (int n, int src, int tar, int aux){ if(n>0){ hanoi(n-1, src, aux, tar); move(src, tar); hanoi(n-1, aux, tar, src); } }
示例2：排列问题 3设计一个递归算法：生成n个元素{r1r2,rn}的全排列 ·设R={r1r2vrn是要进行排列的n个元素，R=R-{r} ·集合X中元素的全排列记为：perm(X) ·（(r:)perm(X)：在perm(X)的每个排列前加上前缀得到的排列 ·R的全排列可归纳定义如下： ·当n=1时，perm(R)=(r),其中r是集合R中唯一的元素 ·当n>1时，perm(R)的构成情况如下： (r)perm(R1),(r2)perm(R2),...(rn)perm(Rn)
示例2：排列问题 设计一个递归算法：生成n个元素{r1 ,r2 ,…,rn}的全排列 • 设R={r1 ,r2 ,…,rn}是要进行排列的n个元素，Ri=R-{ri} • 集合X中元素的全排列记为：perm(X) • (ri)perm(X) ：在perm(X)的每个排列前加上前缀得到的排列 • R的全排列可归纳定义如下： • 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素 • 当n>1时，perm(R)的构成情况如下： • (r1 )perm(R1 )，(r2 )perm(R2 )， …， (rn )perm(Rn )
template<class Type> void Perm(Type list[]int k,int m) {产生ist[k:m的所有排列 if (k==m) {川只剩下一个元素 for (int i=0;i<=m;i++)cout <<list[i]; cout<<endl; else /还有多个元素待排列，递归产生排列 for(int i=k;i<=m;i++) Swap(list[k],list叮)； Perm(list,k+1,m); Swap(list[k],list[i]); template<class Type> inline void Swap(Type &a,Type &b) } Type temp=a;a=b;b=temp;
template<class Type> void Perm(Type list[ ], int k, int m) { //产生list[k:m]的所有排列 if (k==m) { //只剩下一个元素 for (int i=0; i<=m; i++) cout <<list[i]; cout<<endl; } else //还有多个元素待排列，递归产生排列 for(int i=k; i<=m; i++) { Swap(list[k], list[i]); Perm(list, k+1, m); Swap(list[k], list[i]); } } template<class Type> inline void Swap(Type &a, Type &b) { Type temp=a; a=b; b=temp; }
排列问题：产生ist[k:m]的所有排列 void perm(type R[],int k,int m){ if(k==m){/只剩下一个元素 for (int i=0;i<=m;i++) cout <R[i]; cout<<endl; else 川还有多个元素待排列，递归产生排列 for(int i=k;i<=m;i++){ int tmp R[k];R[k]R[i];R[i]tmp;; perm(R,k+1,m); tmp R[k];R[k]R[i];R[i]tmp;
void perm(type R[], int k, int m) { if (k==m) { // 只剩下一个元素 for (int i=0; i<=m; i++) cout << R[i]; cout<<endl; } else { // 还有多个元素待排列，递归产生排列 for(int i=k; i<=m; i++) { int tmp = R[k]; R[k] = R[i]; R[i] = tmp;; perm(R, k+1, m); tmp = R[k]; R[k] = R[i]; R[i] = tmp; } } } 排列问题：产生list[k:m]的所有排列