c - 如何理解这些将数组中的 (a1 a2...am b1 b2..bn ) 重新排列为(b1 b2 ..bn a1 a2..am) 的代码

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 6 年前。

Improve this 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;
    }
};

编辑:“正确”缩进:

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 上还有其他问题涵盖了这一点。一看发现SO 3333-3814它处理单个旋转。不久前我修改了一些代码来支持这一点，演示了 GCD 的必要性，但我之前没有发布它。

这是代码 - 它使用 C99 VLA - 可变长度数组。

#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
…