これらのコードを理解する方法（a1 a2 ... am b1 b2..bn）を配列に入れて（b1 b2 ..bn a1 a2..am）

Question

このコードは誰かによって配列[a1 a2...am b1 b2..bn ]を変更するように設計されています配列[b1 b2 ..bn a1 a2..am]が、それは私がポイントを得ることができない最大の共通の除数を含む。

void Exchange(int a[],int m,int n,int s){ 
    int p=m,temp=m+n;int k=s%p; 
    while(k!=0){temp=p;p=k;k=temp%p;} 
    for(k=0 ; k<p ;k++){    //below is where i cant't understand 
     temp=a[k];i=k;j=(i+m)%(m+n); 
     while(j!=k) 
      {a[i]=a[j];i=j;j=(j+m)%(m+n);} 
     a[i]=temp; 
    } 
}; 

EDIT： "適切" インデント：

void Exchange(int a[], int m, int n, int s) { 
    int p = m, temp = m + n, k = s % p; 

    while (k != 0) { 
     temp = p; 
     p = k; 
     k = temp % p; 
    } 

    for (k = 0 ; k < p; k ++) { // below is where i cant't understand 
     temp = a[k]; 
     i = k; 
     j = (i + m) % (m + n); 

     while (j != k) { 
      a[i] = a[j]; 
      i = j; 
      j = (j + m) % (m + n); 
     } 

     a[i] = temp; 
    } 
}; 

Answer 1

コードは、アレイの回転を実現するためにオーバーヘッドの単一の値を使用しています。長さが互いに素である場合、単一のパスで十分である。そうでない場合は、シフトサイクルをGCDの長さで繰り返す必要があります。

これまでのところ、これをカバーする他の質問があります。一回の回転を扱う外観はSO 3333-3814である。しばらく前にGCDの必要性を証明するためのコードをいじっていましたが、以前は投稿していませんでした。

ここにコードがあります - C99 VLAs可変長配列を使用しています。

#include <stdio.h> 

static int gcd(int x, int y) 
{ 
    int r; 

    if (x <= 0 || y <= 0) 
     return(0); 

    while ((r = x % y) != 0) 
    { 
     x = y; 
     y = r; 
    } 
    return(y); 
} 

static void dump_matrix(int m, int n, int source[m][n]) 
{ 
    for (int i = 0; i < m; i++) 
    { 
     for (int j = 0; j < n; j++) 
      printf("%4d", source[i][j]); 
     putchar('\n'); 
    } 
} 

static void init_matrix(int m, int n, int source[m][n]) 
{ 
    for (int i = 0; i < m; i++) 
    { 
     for (int j = 0; j < n; j++) 
      source[i][j] = (i + 1) * (j + 2); 
    } 
} 

static void rotate_1col(int n, int vector[n], int z) 
{ 
    z %= n; 
    if (z != 0) 
    { 
     int c = gcd(n, z); 
     int s = n/c; 
     for (int r = 0; r < c; r++) 
     { 
      int x = r; 
      int t = vector[x]; 
      for (int i = 0; i < s; i++) 
      { 
       int j = (x + z) % n; 
       int v = vector[j]; 
       vector[j] = t; 
       x = j; 
       t = v; 
      } 
     } 
    } 
} 

static void rotate_cols(int m, int n, int source[m][n], int z) 
{ 
    for (int i = 0; i < m; i++) 
     rotate_1col(n, source[i], z); 
} 

int main(void) 
{ 
    int m = 3; 

    for (int n = 2; n < 9; n++) 
    { 
     int source[m][n]; 
     for (int z = 0; z <= n; z++) 
     { 
      init_matrix(m, n, source); 
      printf("Initial:\n"); 
      dump_matrix(m, n, source); 
      rotate_cols(m, n, source, z); 
      printf("Post-rotate %d:\n", z); 
      dump_matrix(m, n, source); 
      putchar('\n'); 
     } 
    } 

    return 0; 
} 

このコードは、さまざまなサイズの配列で回転のサイズが異なることを示しています。出力の例セクション：すべての

… 
Initial: 
    2 3 4 
    4 6 8 
    6 9 12 
Post-rotate 1: 
    4 2 3 
    8 4 6 
    12 6 9 
… 
Initial: 
    2 3 4 5 
    4 6 8 10 
    6 9 12 15 
Post-rotate 3: 
    3 4 5 2 
    6 8 10 4 
    9 12 15 6 
… 
Initial: 
    2 3 4 5 6 7 
    4 6 8 10 12 14 
    6 9 12 15 18 21 
Post-rotate 1: 
    7 2 3 4 5 6 
    14 4 6 8 10 12 
    21 6 9 12 15 18 

Initial: 
    2 3 4 5 6 7 
    4 6 8 10 12 14 
    6 9 12 15 18 21 
Post-rotate 2: 
    6 7 2 3 4 5 
    12 14 4 6 8 10 
    18 21 6 9 12 15 

Initial: 
    2 3 4 5 6 7 
    4 6 8 10 12 14 
    6 9 12 15 18 21 
Post-rotate 3: 
    5 6 7 2 3 4 
    10 12 14 4 6 8 
    15 18 21 6 9 12 
… 
Initial: 
    2 3 4 5 6 7 8 9 
    4 6 8 10 12 14 16 18 
    6 9 12 15 18 21 24 27 
Post-rotate 4: 
    6 7 8 9 2 3 4 5 
    12 14 16 18 4 6 8 10 
    18 21 24 27 6 9 12 15 

Initial: 
    2 3 4 5 6 7 8 9 
    4 6 8 10 12 14 16 18 
    6 9 12 15 18 21 24 27 
Post-rotate 5: 
    5 6 7 8 9 2 3 4 
    10 12 14 16 18 4 6 8 
    15 18 21 24 27 6 9 12 

Initial: 
    2 3 4 5 6 7 8 9 
    4 6 8 10 12 14 16 18 
    6 9 12 15 18 21 24 27 
Post-rotate 6: 
    4 5 6 7 8 9 2 3 
    8 10 12 14 16 18 4 6 
    12 15 18 21 24 27 6 9 
… 

Answer 2

まず、あなたが予想している結果を得るために、私はMを設定しているとnの半分のアレイサイズであることを。また、sはゼロに初期化されると仮定しました。この場合、最初のwhileループは反復しません。また、あなたのコードにはいくつかの宣言がありませんので、私の説明ではいくつかの前提があります。

The variable p holds the number of array elements to swap; 


// This is to keep the value to be overwritten by the swap 
temp=a[k]; 

// This is the array index of the bottom half element to write the top half element to 
i=k; 

// this is to get the current index of the top half; 
j=(i+m)%(m+n); 

// This assignes the bottom index value with the top half value 
while(j!=k) 
    { 
      // Write top half element to corresponding bottom half element 
      a[i]=a[j]; 
      // We can now overwrite top half element; this assignes the index at wich to copy the bottom half element 
      i=j; 
      // This is to get out of the loop 
      j=(j+m)%(m+n); 
    } 

// The bottom half element held at the beginning is now written to the top half at the corresponding index 
a[i]=temp; 

希望している回答です。この結果は、デバッガを使用し、コードを1行ずつ進めることで実現しました。私はあなたがデバッガの使い方を知っているかどうかわかりませんが、もしそうでなければ、私はあなたの使い方を強くお勧めします。それは時間を費やし、それはすばらしい配当を返します:-)