个人原创，转载请注明出处，谢谢！
一、代码
#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
评论