/*
Name: 向量旋轉(zhuǎn)算法集錦
Copyright: 始發(fā)于goal00001111的專欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
Author: goal00001111
Date: 28-12-08 23:28
Description:
向量旋轉(zhuǎn)算法：將具有n個(gè)元素的向量a向左旋轉(zhuǎn)r個(gè)位置。
例如 ：將字符串"abcdefghij"旋轉(zhuǎn)成"defghjabc"，其中n=10，r=3。
其實(shí)就是將 AB 轉(zhuǎn)換成 BA 的過程，這里A ="abc"， B="defghij"。
本文總共采用了四種方法來解決向量旋轉(zhuǎn)問題，依次是：
方法一：最簡(jiǎn)單的直接移動(dòng)向量旋轉(zhuǎn)算法；
方法二：簡(jiǎn)明的的逆置數(shù)組旋轉(zhuǎn)算法；
方法三：傳說中的雜耍旋轉(zhuǎn)算法；
方法四：一個(gè)類似于歐幾里得算法的旋轉(zhuǎn)算法；
其中方法一需要一個(gè)輔助數(shù)組，空間復(fù)雜度較高；方法二每個(gè)元素都要移動(dòng)兩次，效率相對(duì)較低；
方法三和方法四都是極牛的算法，空間和時(shí)間復(fù)雜度都很低。
這是牛書《編程珠璣》中的一個(gè)例題，在書的網(wǎng)站上有詳細(xì)的源碼，我把它改成了我所熟悉的樣子。
源碼的網(wǎng)站是：http://www.cs.bell-labs.com/cm/cs/pearls/code.html
*/
#include<iostream>
#include <time.h>
using namespace std;
template <class T> //最簡(jiǎn)單的直接移動(dòng)向量旋轉(zhuǎn)算法
void SlideRotate(T a[], int n, int r);
template <class T> //逆置數(shù)組的原子操作
void Reverse(T a[], int left, int right);
template <class T> //簡(jiǎn)明的的逆置數(shù)組旋轉(zhuǎn)算法
void ReverseRotate(T a[], int n, int r);
int Gcd(int m, int n); //歐幾里德算法求最大公約數(shù)
template <class T> //傳說中的雜耍旋轉(zhuǎn)算法
void JuggleRotate(T a[], int n, int r);
template <class T> //交換兩個(gè)長(zhǎng)度均為len的向量塊a[left_1..left_1+len) 和 a[left_2..left_2+len)
void Swap(T a[], int left_1, int left_2, int len);
template <class T> //一個(gè)類似于歐幾里得算法的旋轉(zhuǎn)算法
void GcdRotate(T a[], int n, int r);
template <class T> //創(chuàng)建一個(gè)向量
void InitVector(T a[], int n);
template <class T> //輸出一個(gè)向量
void PrintVector(const T a[], int n);
template <class T> //判斷向量旋轉(zhuǎn)是否成功
bool CheckRotate(const T a[], int n, int r);
int main()
{
const int N = 601; //測(cè)試次數(shù)
const int MAX = 500000; //向量長(zhǎng)度
int a[MAX] = {0};
int rotateDistance = 100000;
time_t startTime, endTime;
////////最簡(jiǎn)單的直接移動(dòng)向量旋轉(zhuǎn)算法///////////////////////////////
time(&startTime);
InitVector(a, MAX);
// PrintVector(a, MAX);
for (int i=0; i<N; i++)
SlideRotate(a, MAX, rotateDistance);
// PrintVector(a, MAX);
if (CheckRotate(a, MAX, rotateDistance))
cout << "True" << endl;
else
cout << "False" << endl;
time(&endTime);
cout << "time = " << difftime(endTime, startTime) << endl << endl;
///////////////////////////////////////////////////////////////////////////////////////////
//////////簡(jiǎn)明的的逆置數(shù)組旋轉(zhuǎn)算法//////////////////////////////////////////////////
time(&startTime);
InitVector(a, MAX);
// PrintVector(a, MAX);
for (int i=0; i<N; i++)
ReverseRotate(a, MAX, rotateDistance);
// PrintVector(a, MAX);
if (CheckRotate(a, MAX, rotateDistance))
cout << "True" << endl;
else
cout << "False" << endl;
time(&endTime);
cout << "time = " << difftime(endTime, startTime) << endl << endl;
///////////////////////////////////////////////////////////////////////////////////////////
////////////傳說中的雜耍旋轉(zhuǎn)算法 //////////////////////////////////////
time(&startTime);
InitVector(a, MAX);
// PrintVector(a, MAX);
for (int i=0; i<N; i++)
JuggleRotate(a, MAX, rotateDistance);
// PrintVector(a, MAX);
if (CheckRotate(a, MAX, rotateDistance))
cout << "True" << endl;
else
cout << "False" << endl;
time(&endTime);
cout << "time = " << difftime(endTime, startTime) << endl << endl;
///////////////////////////////////////////////////////////////////////////////////////////
/////////////一個(gè)類似于歐幾里得算法的旋轉(zhuǎn)算法///////////////////////////////////
time(&startTime);
InitVector(a, MAX);
// PrintVector(a, MAX);
for (int i=0; i<N; i++)
GcdRotate(a, MAX, rotateDistance);
// PrintVector(a, MAX);
if (CheckRotate(a, MAX, rotateDistance))
cout << "True" << endl;
else
cout << "False" << endl;
time(&endTime);
cout << "time = " << difftime(endTime, startTime) << endl << endl;
///////////////////////////////////////////////////////////////////////////////////////////
system("pause");
return 0;
}
////////////方法一：創(chuàng)建一個(gè)長(zhǎng)度為min{r, n-r)的輔助數(shù)組，以幫助完成旋轉(zhuǎn)任務(wù)//////////////////
/*
函數(shù)名稱：SlideRotate
函數(shù)功能：最簡(jiǎn)單的直接移動(dòng)向量旋轉(zhuǎn)算法：先利用一個(gè)輔助數(shù)組將較短的那一段元素存儲(chǔ)起來，
再移動(dòng)原向量中未另外存儲(chǔ)的那部分元素，最后將輔助數(shù)組中的元素再?gòu)?fù)制到正確位置
輸入?yún)?shù)：T a[]：需要被旋轉(zhuǎn)的向量
int n：向量的長(zhǎng)度
int r：向量左半段長(zhǎng)度
輸出參數(shù)：T a[]：旋轉(zhuǎn)后的向量
返回值：無
*/
template <class T>
void SlideRotate(T a[], int n, int r)
{
if (r < n - r) //如果左半段小于右半段，存儲(chǔ)左半段的元素
{
T *buf = new T[r];
for (int i=0; i<r; i++)//存儲(chǔ)左半段的元素
buf[i] = a[i];
for (int i=r; i<n; i++)//移動(dòng)右半段的元素
a[i-r] = a[i];
for (int i=0; i<r; i++)//復(fù)制左半段的元素到右半段
a[n-r+i] = buf[i];
delete []buf;
}
else //否則存儲(chǔ)右半段的元素
{
T *buf = new T[n-r];
for (int i=r; i<n; i++)//存儲(chǔ)右半段的元素
buf[i-r] = a[i];
for (int i=r-1; i>=0; i--)//移動(dòng)左半段的元素
a[i+n-r] = a[i];
for (int i=0; i<n-r; i++)//復(fù)制右半段的元素到左半段
a[i] = buf[i];
delete []buf;
}
}
////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////方法二：使用一個(gè)逆置數(shù)組的原子操作////////////////////////////////////
/*
函數(shù)名稱：Reverse
函數(shù)功能：逆置數(shù)組的原子操作
輸入?yún)?shù)：T a[]：需要被逆置的向量
int left： 數(shù)組的左界
int right：數(shù)組的右界
輸出參數(shù)：T a[]：逆置后的數(shù)組
返回值：無
*/
template <class T>
void Reverse(T a[], int left, int right)
{
T t;
while (left < right)
{
t = a[left];
a[left] = a[right];
a[right] = t;
left++;
right--;
}
}
/*
函數(shù)名稱：ReverseRotate
函數(shù)功能：簡(jiǎn)明的的逆置數(shù)組旋轉(zhuǎn)算法：構(gòu)造一個(gè)逆置數(shù)組的原子操作子函數(shù)，然后設(shè)置不同的數(shù)組左右界，
分三次調(diào)用子函數(shù)就行了。因?yàn)槊總€(gè)元素都需要移動(dòng)兩次，所以效率不是很高。
輸入?yún)?shù)：T a[]：需要被旋轉(zhuǎn)的向量
int n：向量的長(zhǎng)度
int r：向量左半段長(zhǎng)度
輸出參數(shù)：T a[]：旋轉(zhuǎn)后的向量
返回值：無
*/
template <class T>
void ReverseRotate(T a[], int n, int r)
{
Reverse(a, 0, r-1); //逆置左半段數(shù)組
Reverse(a, r, n-1); //逆置右半段數(shù)組
Reverse(a, 0, n-1); //逆置整段數(shù)組
}
////////////////////////////////////////////////////////////////////////////////////////////////
//////////////方法三：傳說中的雜耍旋轉(zhuǎn)算法////////////////////////////////////////////////
/*
函數(shù)名稱：Gcd
函數(shù)功能：歐幾里德算法求最大公約數(shù)
輸入?yún)?shù)：int m：正整數(shù)之一
int n：正整數(shù)之二
輸出參數(shù)：無
返回值：正整數(shù)m和n的最大公約數(shù)
*/
int Gcd(int m, int n)
{
int t;
while (m > 0)
{
t = n % m;
n = m;
m = t;
}
return n;
}
/*
函數(shù)名稱：JuggleRotate
函數(shù)功能：傳說中的雜耍旋轉(zhuǎn)算法：
先將a[0]存儲(chǔ)到臨時(shí)變量t中，然后將a[r]移動(dòng)到a[0],將a[2r] 移動(dòng)到 a[r]，
依此類推(數(shù)組中所有的下標(biāo)都要對(duì)數(shù)組的長(zhǎng)度n取模)，直到(k*r)%n == 0，
此時(shí)我們不能在a[0]中取數(shù)，而是在臨時(shí)變量t中取數(shù)，然后結(jié)束該過程。
如果該過程不能移動(dòng)所有的元素，那么我們從a[1]開始移動(dòng)，一直依次下去，
直到移動(dòng)了所有的元素為止。
那么總共要重復(fù)開始移動(dòng)幾次呢？數(shù)學(xué)證明是Gcd(r, n)次。
此算法每個(gè)元素只需移動(dòng)一次就可以到達(dá)正確位置，理論上效率是最高的，
但由于要做求最大公約數(shù)和求余運(yùn)算等準(zhǔn)備工作，所以沒有顯示出優(yōu)勢(shì)。
輸入?yún)?shù)：T a[]：需要被旋轉(zhuǎn)的向量
int n：向量的長(zhǎng)度
int r：向量左半段長(zhǎng)度
輸出參數(shù)：T a[]：旋轉(zhuǎn)后的向量
返回值：無
*/
template <class T>
void JuggleRotate(T a[], int n, int r)
{
int i, j, k;
int cyc = Gcd(r, n); //用r和n的最大公約數(shù)作為循環(huán)周期
for (i=0; i<cyc; i++) //總共需要重復(fù)開始移動(dòng)cyc次，才能使得所有的元素都移動(dòng)到正確位置
{
T t = a[i]; //臨時(shí)變量t存儲(chǔ)a[i]
j = i;
while (1)//依次移動(dòng)元素，直到 (k*r)%n == 0
{
k = j + r;
if (k >= n) //用除法運(yùn)算替代模運(yùn)算
k -= n;
if (k == i)
break;
a[j] = a[k];
j = k;
}
a[j] = t;
}
}
////////////////////////////////////////////////////////////////////////////////////////////////
//////////////方法四：一個(gè)類似于歐幾里得輾轉(zhuǎn)相除算法的旋轉(zhuǎn)算法/////////////////////////////////
/*
函數(shù)名稱：Swap
函數(shù)功能：交換兩個(gè)長(zhǎng)度均為len的向量塊a[left_1..left_1+len) 和 a[left_2..left_2+len)
輸入?yún)?shù)：T a[]：需要被處理的向量
int left_1：向量塊a[left_1..left_1+len)的左界
int left_2：向量塊a[left_2..left_2+len)的左界
int len： 兩個(gè)向量塊的長(zhǎng)度
輸出參數(shù)：T a[]：交換了部分元素的向量
返回值：無
*/
template <class T>
void Swap(T a[], int left_1, int left_2, int len)
{
T t;
while (len > 0)
{
t = a[left_1];
a[left_1] = a[left_2];
a[left_2] = t;
left_1++;
left_2++;
len--;
}
}
/*
函數(shù)名稱：JuggleRotate
函數(shù)功能：一個(gè)類似于歐幾里得輾轉(zhuǎn)相除算法的旋轉(zhuǎn)算法：
就像一個(gè)做阻尼振動(dòng)的彈簧振子一樣，按照由兩邊到中間的順序，整段的交換向量塊，
并且被交換的向量塊長(zhǎng)度不斷縮減，直到lLen == rLen。
由于重復(fù)移動(dòng)的元素較少，所以效率比逆置數(shù)組旋轉(zhuǎn)算法要高。
輸入?yún)?shù)：T a[]：需要被旋轉(zhuǎn)的向量
int n：向量的長(zhǎng)度
int r：向量左半段長(zhǎng)度
輸出參數(shù)：T a[]：旋轉(zhuǎn)后的向量
返回值：無
*/
template <class T>
void GcdRotate(T a[], int n, int r)
{
if (r == 0 || r == n) //特殊情況不用旋轉(zhuǎn)
return;
int lLen, rLen, pos;
lLen = pos = r;
rLen = n - r;
while (lLen != rLen)
{
if (lLen > rLen) //左半段大于右半段，移動(dòng)右半段
{
Swap(a, pos-lLen, pos, rLen);
lLen -= rLen; //減少移動(dòng)范圍
}
else
{
Swap(a, pos-lLen, pos+rLen-lLen, lLen);
rLen -= lLen;
}
}
Swap(a, pos-lLen, pos, lLen); //最后交換中間段
}
////////////////////////////////////////////////////////////////////////////////////////////////
/*
函數(shù)名稱：InitVector
函數(shù)功能：創(chuàng)建一個(gè)向量
輸入?yún)?shù)：T a[]：需要被賦值的向量
int n：向量的長(zhǎng)度
輸出參數(shù)：T a[]：創(chuàng)建好的向量
返回值：無
*/
template <class T>
void InitVector(T a[], int n)
{
for (int i=0; i<n; i++) //創(chuàng)建一個(gè)向量
a[i] = i;
}
/*
函數(shù)名稱：PrintVector
函數(shù)功能：輸出一個(gè)向量
輸入?yún)?shù)：const T a[]：需要被輸出的向量
int n：向量的長(zhǎng)度
輸出參數(shù)：無
返回值：無
*/
template <class T>
void PrintVector(const T a[], int n)
{
for (int i=0; i<n; i++)
cout << a[i] << ' ';
cout << endl;
}
/*
函數(shù)名稱：CheckRotate
函數(shù)功能：判斷向量旋轉(zhuǎn)是否成功
輸入?yún)?shù)：T a[]：需要被旋轉(zhuǎn)的向量
int n：向量的長(zhǎng)度
int r：向量左半段長(zhǎng)度
輸出參數(shù)：無
返回值：旋轉(zhuǎn)成功返回true，否則返回false
*/
template <class T>
bool CheckRotate(const T a[], int n, int r)
{
for (int i=0; i<n-r; i++) //判斷左半段
{
if (a[i] != i+r)
return false;
}
for (int i=0; i<r; i++)//判斷右半段
{
if (a[n-r+i] != i)
return false;
}
return true;
}