第一个交换功能有什么问题?

我正在编写一个代码来生成数组元素的排列。我写了两种不同类型的交换功能,一种使用临时存储工作正常,另一种不使用任何临时存储,不产生输出。为什么会这样?

以下代码正常工作

#include
#include
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 ;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<

虽然下面的代码不会输出排列:

#include
#include
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 ;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<
0
额外 编辑
意见: 1
请记住, std :: swap()存在,应尽可能使用,但是您的 swap()函数可能会产生名称冲突,因为您使用 namespace std;
额外 作者 stefaanv,

2 答案

请为任何你相信(或以其他方式)的神的爱,不要使用你的第二个交换函数(或可怕的XOR交换技巧)这样的丑陋黑客。

与典型的临时变量解决方案相比,它们是完全不必要的,而且通常比速度更慢。他们还会导致您的代码在诸如每日WTF 等网站上出现,以及几代程序员(他们以维持这种罪行)将诅咒你的名字通过几个世纪前:-)

而且,无论如何,如果你正在“交换”的两个元素是同一个元素,那么它们将不起作用,因为你所做的一切:

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

其中 ij 具有相同的值,因此您已经失去了其他步骤工作所需的信息。

你可以看到如下的行动。假设您有两个不同变量, a = 20b = 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 ++是否允许补码或符号量级)。

但是让我们看看当 ab相同变量(不是相同的,但实际相同的变量,就像一个参考)。所以他们“两者”的价值是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.

这并不是你预期的结果。

0
额外
@paxdiablo感谢您的建议....
额外 作者 manyu,
+1,用于防止人们使用丑陋的黑客,因为我们不再使用8位微处理器上的汇编语言,所以没有任何好处。
额外 作者 Axel,
而且,根据数组的内容,计算过程中可能会发生上溢/下溢。
额外 作者 swegi,
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];
}

i == j (它随后将v [i]设置为0)时不起作用,这会发生在您的循环中

for (int j = index; j < n; ++j) {
    swap(arr, index, j);
0
额外
只是没有点击我的想法....非常感谢你为我节省了很多时间。 :)
额外 作者 manyu,