C++完成一維向量扭轉算法。本站提示廣大學習愛好者：（C++完成一維向量扭轉算法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++完成一維向量扭轉算法正文
在《編程珠玑》一書的第二章提到了n元一維向量扭轉算法（又稱數組輪回移位算法）的五種思緒，而且比擬了它們在時光和空間機能上的差別和好壞。本文遷就這一算法做較為深刻的剖析。詳細以下所示：
1、成績描寫
將一個n元一維向量向左扭轉i個地位。例如，假定n=8，i=3，向量abcdefgh扭轉為向量defghabc。簡略的代碼應用一個n元的中央向量在n步內可完成該任務。你可否僅應用幾十個額定字節的內存空間，在反比於n的時光內完成向量的扭轉？
2、處理計劃
思緒一：將向量x中的前i個元素復制到一個暫時數組中，接著將余下的n-i個元素左移i個地位，然後再將前i個元素從暫時數組中復制到x中余下的地位。
機能：這類辦法應用了i個額定的地位，假如i很年夜則發生了過年夜的存儲空間的消費。
C++代碼完成以下：
/*************************************************************************
> File Name: vector_rotate.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s = "abcdefghijklmn";
cout << "The origin is: " << s << endl;
// 左移個數
int i;
cin >> i;
if(i > s.size())
{
i = i%s.size();
}
// 將前i個元素暫時保留
string tmp(s, 0, i);
// 將殘剩的左移i個地位
for(int j=i; j<s.size(); ++j)
{
s[j-i] = s[j];
}
s = s.substr(0, s.size()-i) + tmp;
cout << "The result is: "<< s << endl;
return 0;
}
思緒二：界說一個函數將x向左扭轉一個地位（當時間反比於n），然後挪用該函數i次。
機能：這類辦法固然空間龐雜度為O(1)，但發生了過量的運轉時光消費。
C++代碼完成以下：
/*************************************************************************
> File Name: vector_rotate_1.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
using namespace std;
void rotateOnce(string &s)
{
char tmp = s[0];
int i;
for(i=1; i<s.size(); ++i)
{
s[i-1] = s[i];
}
s[i-1] = tmp;
}
int main()
{
string s = "abcdefghijklmn";
cout << "The origin is: " << s << endl;
// 左移個數
int i;
cin >> i;
if(i > s.size())
{
i = i%s.size();
}
// 挪用函數i次
while(i--)
{
rotateOnce(s);
}
cout << "The result is: "<< s << endl;
return 0;
}
思緒三：挪動x[0]莅臨時變量t中，然後挪動x[i]到x[0]中，x[2i]到x[i]，順次類推，直到我們又回到x[0]的地位提取元素，此時改成從暫時變量t中提取元素，然後停止該進程（當下標年夜於n時對n取模或許減去n）。假如該進程沒有挪動全體的元素，就從x[1]開端再次停止挪動，總共挪動i和n的最年夜條約數次。
機能：這類辦法異常精致，像書中所說的一樣可謂奇妙的雜技扮演。空間龐雜度為O(1)，時光龐雜度為線性時光，知足成績的機能請求，但還不是最好。
C++代碼完成以下：
/*************************************************************************
> File Name: vector_rotate_2.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
using namespace std;
// 歐幾裡德（展轉相除）算法求最年夜條約數
int gcd(int i, int j)
{
while(1)
{
if(i > j)
{
i = i%j;
if(i == 0)
{
return j;
}
}
if(j > i)
{
j = j%i;
if(j == 0)
{
return i;
}
}
}
}
int main()
{
string s = "abcdefghijklmn";
cout << "The origin is: "<< s << endl;
// 左移個數
int i;
cin >> i;
if(i > s.size())
{
i = i%s.size();
}
// 挪動
char tmp;
int times = gcd(s.size(), i);
for(int j=0; j<times; ++j)
{
tmp = s[j];
int pre = j; // 記載上一次的地位
while(1)
{
int t = pre+i;
if(t >= s.size())
t = t-s.size();
if(t == j) // 直到tmp本來的地位j為止
break;
s[pre] = s[t];
pre = t;
}
s[pre] = tmp;
}
cout << "The result is: "<< s << endl;
return 0;
}
思緒四：扭轉向量x現實上就是交流向量ab的兩段，獲得向量ba，這裡a代表x的前i個元素。假定a比b短。將b朋分成bl和br，使br的長度和a的長度一樣。交流a和br，將ablbr轉換成brbla。由於序列a已在它的終究地位了，所以我們可以集中精神交流b的兩個部門了。因為這個新成績和本來的成績是一樣的，所以我們以遞歸的方法停止處理。這類辦法可以獲得優雅的法式，然則須要奇妙的代碼，而且要停止一些思慮能力看出它的效力足夠高。
//完成代碼（略）
思緒五：（最好）將這個成績看作是把數組ab轉換成ba，同時假定我們具有一個函數可以將數組中特定部門的元素逆序。從ab開端，起首對a求逆，獲得arb，然後對b求逆，獲得arbr。最初全體求逆，獲得（arbr）r，也就是ba。
reverse(0, i-1) /*cbadefgh*/ reverse(i, n-1) /*cbahgfed*/ reverse(0, n-1) /*defghabc*/
機能：求逆序的辦法在時光和空間上都很高效，並且代碼異常冗長，很難失足。
C++代碼完成以下：
/*************************************************************************
> File Name: vector_rotate.cpp
> Author: SongLee
************************************************************************/
#include<iostream>
#include<string>
using namespace std;
void reverse(string &s, int begin, int end)
{
while(begin < end)
{
char tmp = s[begin];
s[begin] = s[end];
s[end] = tmp;
++begin;
--end;
}
}
int main()
{
string s = "abcdefghijklmn";
cout << "The origin is: "<< s << endl;
int i;
cin >> i;
if(i > s.size())
{
i = i%s.size();
}
reverse(s, 0, i-1);
reverse(s, i, s.size()-1);
reverse(s, 0, s.size()-1);
cout << "The result is: "<< s << endl;
return 0;
}
3、擴大延長
若何將向量abc扭轉釀成cba？
和後面的成績相似，此向量扭轉對應著非相鄰內存塊的交流模子。解法很類似，即應用恆等式：cba = （arbrcr）r
留意：在面試或口試時，如若湧現向量扭轉（內存塊交流）成績，建議最好應用思緒五答題，不只高效並且簡練。
