向量左旋算法之取模置换

本文主要是介绍向量左旋算法之取模置换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

开篇

在之前的文章从0到1：C语言实现一维向量旋转操作中，讲解了一维向量的旋转操作的实现代码。而本篇文章中，会针对上次提到的一维向量的左旋操作，使用另一种方法来解决：取模置换法。
本题来源为《编程珠玑》第2章第3题。

问题概要

将一个n元一维向量向左旋转i个位置。例如，当n = 8且i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转。

思路分析

移动x[0]到临时变量t,然后移动x[i]到x[0],x[2i]到x[i]，依次类推（将x中所有下标对n取模），直至返回到取x[0]中的元素，此时改为从t取值，然后终止过程。
单纯看上面的思路，其实是有点抽象的，所以，以一个简单的例子，来说明:
假设有一个字符串: abcde, 需要左旋2个, 此时n = 5, i = 2
1: t=x[0]=a, x[0]=x[2]=c, 此时字符串为cb_de, 其中_为空位
2: (2+2)%5=4,所以t=a, x[2]=x[4]=e,此时字符串为cbed_
3: (4+2)%5=1, 所以t=a, t[4]=t[1]=b, 此时字符串为c_edb
4: (1+2)%5=3, 所以t=a, t[1] = t[3] = d, 此时字符串为cde_b
5: (3+2)%5=0, 因为又回到了x[0],此时取出t的值，放到空位上，得到cdeab
输出结果

代码实现

#include <stdio.h>
#include <string.h>// 辗转相除法求最大公约数
unsigned int gcd(unsigned int a, unsigned int b) {while (b != 0) {unsigned int temp = a % b;a = b;b = temp;}return a;
}// 旋转字符串左边的n个字符
void rotateLeft(char str[], int n, int k) {int len = strlen(str);k = k % len; // 确保旋转次数不超过字符串长度int gcdValue = gcd(len, k); // 计算字符串长度和旋转次数的最大公约数int i;for (i = 0; i < gcdValue; i++) {char temp = str[i];int j = i;int nextIndex;while (1) {nextIndex = (j + k) % len; // 直接计算下一个索引位置if (nextIndex == i) break; // 如果回到了起始位置，则结束这个循环str[j] = str[nextIndex];j = nextIndex;}str[j] = temp;}
}int main() {char str[1024]; // 假定输入的字符串不超过1023个字符int n;printf("输入一个字符串: ");fgets(str, sizeof(str), stdin); // 读取包括空格的字符串str[strcspn(str, "\n")] = 0; // 删除字符串末尾的换行符printf("输入要左旋的位数: ");scanf("%d", &n);printf("原字符串: %s\n", str);rotateLeft(str, strlen(str), n);printf("旋转后: %s\n", str);return 0;
}