正文

编程珠矶学习笔记(3)--反转旋转(手摇法实现旋转)2009-10-19 22:19:00

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

分享到:

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

一、目的
如示例:

input: n = 10, rotdist = 5 (移动前5个元素到数组尾), x[] = {1,2,3,4,5,6,7,8,9,10}

output: x[6,7,8,9,10,1,2,3,4,5]

constrain: 使用尽可能少的额外内存

可通过手揺法来实现旋转,其原理如下图:

准备:两手上下平放,左手在上,右手在下,手面圴冲自己,此时规定十个手指从上到下分别代表1,2,3,4,5,6,7,8,9,10


第一步:将左手反转,手背冲自己,拇指此时冲地面:

第二步:将右手也反转,手背冲自己,拇指此时冲地面:


第三步:将两个手同是反转,手面冲自己,与准备动作的区别是,现在右手在上左在下,观察手指上的数字会发现,此时已经达到了移位的目的(6,7,8,9,10,1,2,3,4,5):


这就是本算法的原理,通过三次反转(手摇三次)来实现旋转的目的。为了易于说明原理,本例采用了10个元素,移动5个的要求(必竟人就10个手指嘛),但对于其它任何要求,本算法也适用。

二、代码
#include <stdio.h>

#include <stdlib.h>

#include <time.h> 

#define MAXN 10000000 

int x[MAXN];

int rotdist, n; 

void reverse(int i, int j)

{      int t;

       while (i < j) {

              t = x[i]; x[i] = x[j]; x[j] = t;

              i++;

              j--;

       }

}

 

void revrot (int rotdist, int n)

{     

       reverse(0, rotdist-1);

       reverse(rotdist, n-1);

       reverse(0, n-1);

}

 

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();

              revrot (rotdist, n);

              printx();

       }

       return 0;

}

三、代码注解
#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAXN 10000000

 

int x[MAXN];

int rotdist, n;

 

/*反转函数*/

void reverse(int i, int j)

{      int t;

       while (i < j) {

              t = x[i]; x[i] = x[j]; x[j] = t;

              i++;

              j--;

       }

}

 

/*通过三次反转实现旋转要求*/

void revrot (int rotdist, int n)

{     

      reverse(0, rotdist-1);  /*等价于先反转左手*/

       reverse(rotdist, n-1); /*等价于再反转右手*/

       reverse(0, n-1); /*等价于两个手一起反转*/

}

 

/*

* 初始化前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();/*打印出旋转前的各元素*/

              revrot(rotdist, n);

             printx();/*打印出旋转后的各元素*/

       }

       return 0;

}

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/lijian818181/archive/2009/09/26/4598797.aspx

阅读(1859) | 评论(0)


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

评论

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