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