个人原创，转载请注明出处，谢谢！ 一、目的如示例： 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
评论