【background】 输入n，(1<=n<=20)要求输出 n^n 个 每个长度为n的所有通过乘法原理所列举出的排列。 比如n为2时 1---1 | X | 2---2 即要求按行输出 11 12 21 22

【sample input】 3 【sample output】 111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323 331 332 333

#include <stdio.h>

int n, k, c[20];

search(x) int x; { int i; if(!x){ for(i=0; i<n; i++) printf("%d",c[i]); printf("\n"); return; } for(i=1; i<=n; i++){ c[k]=i; k++; search(x-1); k--; } }

main() { scanf("%d",&n); if(n<1||n>20)return; k=0; search(n); }

盖茨厉害！ 真是再次领略了递归算法的魅力。 出于非常喜爱算法的缘故，在下也在此发表一些观后拙见了， 如有错误，还请在座各位高手们不吝指正。

设计此递归程序步骤： 1. 首先得发现此问题是 递归可解类型的，即递归的，如得出所有n-1位排列数是得出所有n位排列数在规则上的一个复制，n-2,n-3...1位数皆亦如此。 2. 其次为程序设计一个递归出口，即当n等于1时，盖茨这儿用的是 search()函数形参为0。 3. 最后 for(i=1; i<=n; i++) { c[k]=i; k++; search(x-1); k--; } 偶对这个关键部分的理解 k初值为0，c[k]的值即表示第n位的值（最左位） k++，k--是为了使c[k]保持在原位即最左位能取到所有1～n 什么时候开始递归？自然当最左位向右移动一位，接下来的步骤就是对前位操作规则的复制。

[此贴子已经被作者于2005-1-6 22:21:42编辑过]

我贴个自己写的递归算法。。。 #include <stdio.h> #include <stdlib.h> #include <conio.h>

void print_permutation(int *box,int n,int pos);

int main() { int *box; int n; printf("Input the number n="); scanf("%d",&n); box=(int*)malloc(n*sizeof(int)); if(!box) { printf("Cannot allocate memory!\n"); return 1; } print_permutation(box,n,0); free(box); getch(); return 0; }

void print_permutation(int *box,int n,int pos) { if(pos<n) { for(int i=1;i<=n;i++) { box[pos]=i; pos++; print_permutation(box,n,pos); pos--; } } else { for(int i=0;i<n;i++) printf("%d",box[i]); printf("\n"); } }

[此贴子已经被作者于2005-2-26 19:35:45编辑过]