1

我正在编写代码来生成数组元素的排列。我编写了两种不同类型的交换函数，一种使用临时存储可以正常工作，而另一种不使用任何临时存储则不会生成输出。为什么会这样？？

以下代码工作正常

#include<iostream>
#include<cstdio>
using namespace std;
int tt=0;
void swap1 (int v[], int i, int j) {
    int t;

    t = v[i];
    v[i] = v[j];
    v[j] = t;
}   
void permute(int arr[],int n,int index)
{
     if(index==n)
                {
                for(int i=0;i<n;i++) printf ("%c", arr[i]) ;
                printf("\n");
                tt++;
                }
     else
         for(int j=index; j < n ;j++)
         {
           swap1(arr,index,j);
           permute(arr,n,index+1); 
           swap1(arr,j,index);           
         }        
}
int main()
{
    int arr[]={'a','b','c','d'};
    permute(arr,4,0);
    cout<<endl;
    printf("%d\n",tt);
    getchar();
}

output:
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc

24

虽然以下代码不输出排列：

#include<iostream>
#include<cstdio>
using namespace std;
int tt=0;
void swap(int v[],int i,int j)
{
     v[i]= v[i] + v[j];
     v[j]= v[i] - v[j];
     v[i]= v[i] - v[j];
}
void permute(int arr[],int n,int index)
{
     if(index==n)
                {
                for(int i=0;i<n;i++) printf ("%c", arr[i]) ;
                printf("\n");
                tt++;
                }
     else
         for(int j=index; j < n ;j++)
         {
           swap(arr,index,j);
           permute(arr,n,index+1); 
           swap(arr,j,index);           
         }        
}
int main()
{
    int arr[]={'a','b','c','d'};
    permute(arr,4,0);
    cout<<endl;
    printf("%d\n",tt);
    getchar();
}

output:

























24
4

2 回答 2

7

请，为了你所信仰的任何神灵的爱（或其他），不要使用像你的第二个交换功能（或可怕的异或交换技巧）这样的丑陋黑客。

它们完全没有必要，而且通常比典型的临时变量解决方案要慢。它们还将导致您的代码出现在The Daily WTF之类的网站上，而一代又一代的程序员（他们必须维护这样的垃圾）将在未来的几个世纪中诅咒您的名字 :-)

而且，无论如何，如果您“交换”的两个元素是相同的，它们将不起作用，因为在您这样做的那一刻：

v[i]= v[i] + v[j];

如果i和j是相同的值，则您丢失了其他步骤工作所需的信息。

您可以在下面看到这一点。假设您有两个不同的变量，a = 20并且b = 30. 完成您的步骤：

a = a + b;  // a <- (20 + 30) = 50, b still = 30.
b = a - b;  // b <- (50 - 30) = 20, a still = 50.
a = a - b;  // a <- (50 - 20) = 30, b still = 20.

并且它们被交换了，尽管您可能希望使用不是二进制补码的溢出和编码方案来研究边缘情况（无论如何，在 C 中，不确定 C++ 是否允许二进制补码或符号幅度）。

但是让我们看看当a和b都是同一个变量时会发生什么（不是同一个值，而是实际的同一个变量，就像一个引用）。所以它们“都”的值是 20，你会期望它们在交换后仍然是 20，但让我们看一下：

a = a + b;  // a <- (20 + 20) = 40, AND b = 40 as well.
b = a - b;  // b <- (40 - 40) =  0, AND a =  0 as well.
a = a - b;  // a <- ( 0 -  0) =  0, AND b =  0 as well.

这并不是你所期望的结果。

于 2012-05-24T07:35:16.430 回答
2 
void swap(int v[],int i,int j)
{
     v[i]= v[i] + v[j];
     v[j]= v[i] - v[j];
     v[i]= v[i] - v[j];
}

当（然后将 v[i] 设置为 0）时不起作用i == j，您的循环会发生这种情况

for (int j = index; j < n; ++j) {
    swap(arr, index, j);
于 2012-05-24T07:31:52.220 回答