1

配列の要素の順列を生成するコードを書いています。私は 2 つの異なるタイプのスワッピング関数を書きましたが、1 つは一時ストレージを使用して正常に動作し、もう 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

あなたが信じている神への愛のために（またはそうでない場合）、2番目のスワップ機能（または恐ろしいXORスワップトリック）のような醜いハックを使用しないでください。

それらは完全に不要であり、通常、典型的な一時変数ソリューションよりも遅くなります。また、 The Daily WTF のようなサイトにあなたのコードが登場することにもなり、何世代にもわたるプログラマー (そのような粗雑さを維持しなければならない) は、何世紀にもわたってあなたの名前を呪うでしょう :-)

いずれにせよ、「交換」している 2 つの要素が同じものである場合、それらは機能しません。

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

ここでi、 とjが同じ値の場合、他のステップが機能するために必要な情報が失われています。

これは、次のように実際に確認できます。2 つの異なる変数 と がある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.

そして、それらは交換されますが、2 の補数ではないオーバーフローとエンコーディング スキームのエッジ ケースを調べたいと思うでしょう (とにかく C では、C++ が 1 の補数または符号の大きさを許可するかどうかはわかりません)。

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];
}

次の場合は機能しませんi == j（その後、v [i]を0に設定します）、ループで発生する何か

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