第一次交换功能有什么问题？

Question

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

以下代码工作正常

#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

Answer 1

请相信你所信仰(或其他)神灵的爱,不要使用丑陋的黑客,比如你的第二个交换功能(或可怕的XOR交换技巧).

它们完全不必要,并且通常比典型的临时变量解决方案慢.它们还会导致你的代码在像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.

这不是你期望的结果.