试确定函数P e r m 共实施了多少次S w a p操作

试确定函数P e r m 共执行了多少次S w a p操作？
//本函数是输出所有可能的排列。

C/C++ code

template<class T>void Perm(T list[], int k, int m){ //生成list [k：m ]的所有排列方式int i,count=0;if (k == m) {//输出一个排列方式    for (int i = 0; i <= m; i++)        cout << list [i];    cout << endl;}else // list[k：m ]有多个排列方式// 递归地产生这些排列方式for (i=k; i <= m; i++) {    swap (list[k], list[i]);    Perm (list, k+1, m);    swap (list [k], list [i]);    count+=2;}}

//这个我怎么感觉是count=(2^(m-k+1))*(m-(k-1))*(m-k)*(m-(k+1))*....(m-(m-1))
//但最后输出结果显示是错误的，到底错在哪了？ 正确的计算交换次数是。。。？并且最好写出过程。。。答案上的结果也看不懂，所以写出过程。谢谢！

[解决办法]

如程序所示：count的值就是swap的执行次数

为了求count，我们构造数列a(n)，使程序中for循环的循环次数为n时语句“count+=2;”的执行次数为a

(n)，则count的值为2a(n)。显然for循环的循环次数为m-k+1，所以count的值为2a(n) = 2a(m-k+1)

下面我们来求数列a(n):
由程序显然有：a(1) = 0, a(n) = n(a(n-1)+1)
两边都除以n!可得：

a(n)/n! = a(n-1)/(n-1)! + 1/(n-1)!
a(n-1)/(n-1)! = a(n-2)/(n-2)! + 1/(n-2)!
.
.
.
a(3)/3! = a(2)/2! +1/2!
a(2)/2! = a(1)/1! +1/1!

上式相加可得：
a(n)/n! = 1/(n-1)! + 1/(n-2)! +...+ 1/2! + 1/1!
所以a(n) = n!(1/(n-1)! + 1/(n-2)! +...+ 1/2! + 1/1!)
所以count的值为2a(n) = 2a(m-k+1) = 2(m-k+1)!(1/(m-k)! + 1/(m-k-1)! +...+ 1/2! + 1/1!)

C/C++ code

#include <iostream>using namespace std;int count = 0;template<class T>void Perm(T list[], int k, int m){ //生成list [k：m ]的所有排列方式int i;if (k == m) {//输出一个排列方式    for (int i = 0; i <= m; i++)        cout << list [i];    cout << endl;}else // list[k：m ]有多个排列方式// 递归地产生这些排列方式for (i=k; i <= m; i++) {    swap (list[k], list[i]);    Perm (list, k+1, m);    swap (list [k], list [i]);    count+=2;}}int main(){    int list[7] = {1,2,3,4,5,6};    Perm(list, 2, 5);        printf("%d\n", count);    return 0;} 

 

查看更多 下一篇