个人原创，转载请注明出处，谢谢！ 一、代码#include <stdio.h> #include <stdlib.h> #include <time.h>   #define MAXN 10000000   int x[MAXN]; int rotdist, n;   int gcd(int i, int j) {      int t;        while (i != 0) {               if (j >= i)                      j -= i;               else {                      t = i; i = j; j = t;               }        }        return j; }   void jugglerot(int rotdist, int n) {             int cycles, i, j, k, t;        cycles = gcd(rotdist, n);          for (i = 0; i < cycles; i++) {                 /* move i-th values of blocks */               t = x[i];               j = i;               for (;;) {                 /*利用取余操作，使移动过程调头，这里是难点，见后面的示意图*/              /*等价于k = (j + rotdist ) % n*/                      k = j + rotdist;                      if (k >= n)                             k -= n;                      if (k == i)                             break;                      x[j] = x[k];                      j = k;               }               x[j] = t;        } }   void initx() {        int i;        for (i = 0; i < n; i++)               x[i] = i; }   void printx() {      int i;        for (i = 0; i < n; i++)               printf(" %d", x[i]);        printf("\n"); }   int main(void) {             while (scanf("%d %d ", &n, &rotdist) != EOF) {               initx();               jugglerot(rotdist, n); printx();        }        return 0; } 二、代码注解#include <stdio.h> #include <stdlib.h> #include <time.h>   #define MAXN 10000000   int x[MAXN]; int rotdist, n;     /* *计算最大公约数函数 *求i和j的最大公约数，比如5和3的最大公约数为1，8和6的最大 *公约数是2。 */ int gcd (int i, int j) {      int t;        while (i != 0) {               if (j >= i)                      j -= i;               else {                      t = i; i = j; j = t;               }        }        return j; }   /* 移位方式实现旋转: abcdefg  => defgabc 就像坐在一列凳子上的人（abcdefg），我们要求坐在最前面的三个人(abc)坐到最后面去，其他人依次往前坐三个位子（defg_ _ _），腾出最后的三个位子，然后原来前面的三个人坐进去(defg abc)即可。 本算法的结果和上面的结果类似，但实现过程有所不同，难点在于我们并不知道每次要转移几个元素（rotdist是个变量），所以我们不可能先申请另一个固定的数组去临时装载要移动的元素（当然如果内存足够的大也可以，但这不在本例研究的范畴内），要使用一个临时变量来实现多元素的移动是本例的难点，也是亮点   * input: n, rotdist, x[] = {a,b,c,d,e,f}(示例) * output: x[] * constrain: {a,b,c,d,e,f } è {d,e,f,a,b,c}, 使用尽可能少的额外内存 */ void jugglerot (int rotdist, int n) {            int cycles, i, j, k, t;         /*对于有公约数的现象，一轮可能并不能移完，比如abcdef, 要将ab移动到cdef的后面，则需要两轮，第一轮移动a以及与之相关的c,c，第二轮移动b以及与之相关的d,f，所以使用最大公约数方法计算需要移动几轮 */       cycles = gcd(rotdist, n);        for (i = 0; i < cycles; i++) {               /* move i-th values of blocks */               t = x[i];               j = i;               for ( ; ; ) {                      k = j + rotdist;                      if (k >= n)                             k -= n;                      if (k == i)                             break;                      x[j] = x[k];                      j = k;               }               x[j] = t;        } }   /* * 初始化前n个元素 */ void initx() {        int i;        for (i = 0; i < n; i++)               x[i] = i; }   /* *打印前n个元素 */ void printx() {      int i;        for (i = 0; i < n; i++)               printf(" %d", x[i]);        printf("\n"); }   int main(void) {             while (scanf("%d %d ", &n, &rotdist) != EOF) {               initx(); printx();/*打印出旋转前的各元素*/               jugglerot(rotdist, n); printx();/*打印出旋转后的各元素*/        }        return 0; }   附图：       即实现了从：abc defg =>defg abc   本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/lijian818181/archive/2009/09/23/4586096.aspx

评论