习题3
前面涉及了两个需要精巧代码来实现的向量旋转算法。将其分别作为独立的程序实现。在每个程序中，i和n的最大公约数如何出现？
现在我们来实现这两个精巧代码。
- 方法1
一个一个地置换，每个元素都调整到它所在的正确的位置。方法1的难点是下标的处理，萝卜A到达它的正确的坑后，我们就找到下一个萝卜B，B的正确位置是A原始位置，这样一个一个置换，每一个元素都要置换一次。
void rotate(string& s, int rotdist) {
//参数s是待旋转的字符串，rotdist是旋转的长度
int n = (int)s.size();
int mcd = maxCommonDivisor(rotdist, n);
for (int i = 0; i < mcd; ++i) {
char t = s[i];
int j = i;
while (true) {
int k = j + rotdist;
if (k >= n) {
k -= n;
}
if (k == i) {
break;
}
s[j] = s[k];
j = k;
}
s[j] = t;
}
}
- 方法2：利用swap操作不断缩小范围，类似于求最大公约数时的辗转相除法代码结构。利用递归可能跟容易看懂，因此我们的代码以递归方式呈现。
解析：
以字符串abcdefgh，rotdist=3为例。我们先按照rotdist将字符串分为两部分：A=abc，B=defgh。比较A，B子串的长度，有三种情况：
- A,B的长度相等，这种情况最简单，很显然，我们只需要将A，B交换一下位置就行了 。
- A长度 < B长度。如A=abc，B=defgh。由于长度不等，因此不能直接交换，但是我们可以先交换abc和fgh，变成fghdeabc。然后发现abc已经到达正确的位置，这时我们就不管abc子串了。我们要处理的范围变成fghde，就是将fgh和de交换，新的rotdist还是3。看！要处理的范围缩小了！
- A长度 > B长度。如上面的例子，现在我们需要处理fghde子串，rotdist=3，现在我们的A=fgh，B=de，这个时候我们交换的长度就是min(len(A),len(B))，于是交换得到 de hfg，可以看到de元素也到达了正确的位置，我们要处理的范围变成hfg，rotdist=1。要处理的范围又缩小了！
范围一步一步缩小，直到最终解决问题。
void myswap(string &s, int a,int b,int m) {
for (int i = 0; i < m; ++i) {
swap(s[i + a], s[i + b]);
}
}
void rotate2(string& s,int start,int end, int rotdist) {
int n = end-start+1; // n指的是参数s，从start索引到end索引这段子串的长度，下面统称这段子串为“子串”
if (rotdist == 0 || rotdist == n) {
return;
}
// 子串中旋转长度rotate后面的长度，
// 如“abcdefgh”，start=0，end=7，rotdist=3，则rightLen=5
int rightLen = end - (start + rotdist) + 1;
if (rightLen == rotdist) {
myswap(s, start, start + rotdist, rotdist);
}
else if (rotdist < rightLen) {
myswap(s, start, end-rotdist+1, rotdist);
rotate2(s, start, end - rotdist, rotdist);
}
else {
myswap(s, start, end- rightLen+1, rightLen);
rotate2(s,start+rightLen,end,rotdist-rightLen);
}
}
对于方法2，书中给出了非递归的解法，二者本质是一样的。我认为递归方式更直观，容易理解。
