UC知道请给写下下面程序的注释
来源：百度知道 编辑：UC知道 时间：2024/09/20 19:36:32
#include <stdio.h>
inline void Swap(char& a, char& b)
{// 交换a和b
char temp = a;
a = b;
b = temp;
}
void Perm(char list[], int k, int n)
{ //生成list [k：m ]的所有排列方式
int i;
if (k == n) {//输出一个排列方式
for (i = 0; i <= n; i++)
putchar(list[i]);
putchar('\n');
}
else // list[k：n ]有多个排列方式
// 递归地产生这些排列方式
for (i=k; i <= n; i++) {
Swap (list[k], list[i]);
Perm (list, k+1, n);
Swap (list [k], list [i]);
}
}
int main()
{
char s[]="123";
Perm(s, 0, 2);
return 0;
}
inline void Swap(char& a, char& b)
{// 交换a和b
char temp = a;
a = b;
b = temp;
}
void Perm(char list[], int k, int n)
{ //生成list [k：m ]的所有排列方式
int i;
if (k == n) {//输出一个排列方式
for (i = 0; i <= n; i++)
putchar(list[i]);
putchar('\n');
}
else // list[k：n ]有多个排列方式
// 递归地产生这些排列方式
for (i=k; i <= n; i++) {
Swap (list[k], list[i]);
Perm (list, k+1, n);
Swap (list [k], list [i]);
}
}
int main()
{
char s[]="123";
Perm(s, 0, 2);
return 0;
}
这个程序,如果你没有理解其算法原理,给出注释也没用.如果理解了算法原理,这么简单的几句代码又何必加注释呢.
实际上这个程序使用的算法,就是我们每个人在上小学时,老师就应该教过的列出所有排列的一种思路.
比如给出123的所有排列,
第一步,先给出1开头的排列,在这些排列中,先给出2开头的子排列,再给出3开头的子排列.
第二步,先给出2开头的排列,在这些排列中,先给出1开头的子排列,再给出3开头的子排列.
第三步,先给出3开头的排列,在这些排列中,先给出1开头的子排列,再给出2开头的子排列.
至此,123的所有排列都已给出.
为了用计算机程序实现这一思路,我们可以把上面的表述换一种方式.
题目:给出序列"123....n"的所有排列
思路:
1.将序列的第1个元素提取出来,对序列中的其他元素给出全排列
2.将序列的第2个元素提取出来,对序列中的其他元素给出全排列.这一步实际可以做个变换,就是把序列的第1,2个元素互换,那么这一步就又变成了和第1步一样,把交换后的序列的第1个元素提取出来,对序列中的其他元素给出全排列.
3.同样,是把序列的第1,3个元素互换后,转成和第一步一样.
...
n.把序列的第1,n个元素互换,转成和第一步一样.
看到这里,应该可以明白了吧.
把序列中的第1,k个元素交换,这对应程序中的Swap (list[k], list[i]);
对序列中的其他元素给出全排列,就对应Perm (list, k+1, n); 这个递归调用.
递归结束后,当然要把原来序列的第1,k个元素换回来,就是再执行一次Swap (list[k], list[i]);
wsfsdgdrgdxrgrg