正文

编程珠矶学习笔记(2)--移位旋转2009-10-19 22:13:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/ljqy/49435.html

分享到:

个人原创,转载请注明出处,谢谢!

一、代码
#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

阅读(1987) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册