C實現(xiàn)一維向量旋轉算法

本文格式為Word版，下載可任意編輯——C實現(xiàn)一維向量旋轉算法C++實現(xiàn)一維向量旋轉的算法的怎么編程的呢?下面內容由我為大家介紹C++實現(xiàn)一維向量旋轉算法，供大家參考!

在《編程珠璣》一書的其次章提到了n元一維向量旋轉算法又稱數(shù)組循環(huán)移位算法的五種思路，并且對比了它們在時間和空間性能上的識別和優(yōu)劣。本文將就這一算法做較為深入的分析。概括如下所示：

一、問題描述

將一個n元一維向量向左旋轉i個位置。例如，假設n=8，i=3，向量abcdefgh旋轉為向量defghabc。簡樸的代碼使用一個n元的中間向量在n步內可完成該工作。你能否僅使用幾十個額外字節(jié)的內存空間，在正比于n的時間內完成向量的旋轉?

二、解決方案

思路一：將向量x中的前i個元素復制到一個臨時數(shù)組中，接著將余下的n-i個元素左移i個位置，然后再將前i個元素從臨時數(shù)組中復制到x中余下的位置。

性能：這種方法使用了i個額外的位置，假設i很大那么產生了過大的存儲空間的消耗。

C++代碼實現(xiàn)如下：

/*************************************************************************

FileName:vector_rotate.cpp

Author:SongLee

************************************************************************/

#include

#include

usingnamespacestd;

intmain

strings=abcdefghijklmn;

coutTheoriginis:sendl;

//左移個數(shù)

inti;

cini;

ifis.size

i=i%s.size;

//將前i個元素臨時保存

stringtmps,0,i;

//將剩余的左移i個位置

forintj=i;j

s[j-i]=s[j];

s=s.substr0,s.size-i+tmp;

coutTheresultis:sendl;

return0;

思路二：定義一個函數(shù)將x向左旋轉一個位置其時間正比于n，然后調用該函數(shù)i次。

性能：這種方法雖然空間繁雜度為O1，但產生了過多的運行時間消耗。

C++代碼實現(xiàn)如下：

/*************************************************************************

FileName:vector_rotate_1.cpp

Author:SongLee

************************************************************************/

#include

#include

usingnamespacestd;

voidrotateOncestrings

chartmp=s[0];

inti;

fori=1;i

s[i-1]=s[i];

s[i-1]=tmp;

intmain

strings=abcdefghijklmn;

coutTheoriginis:sendl;

//左移個數(shù)

inti;

cini;

ifis.size

i=i%s.size;

//調用函數(shù)i次

whilei--

rotateOnces;

coutTheresultis:sendl;

return0;

思路三：移動x[0]到臨時變量t中，然后移動x[i]到x[0]中，x[2i]到x[i]，依次類推，直到我們又回到x[0]的位置提取元素，此時改為從臨時變量t中提取元素，然后終止該過程當下標大于n時對n取?；蛘邷p去n。假設該過程沒有移動全部的元素，就從x[1]開頭再次舉行移動，總共移動i和n的最大公約數(shù)次。

性能：這種方法分外精良，像書中所說的一樣堪稱高明的雜技表演?？臻g繁雜度為O1，時間繁雜度為線性時間，得志問題的性能要求，但還不是最正確。

C++代碼實現(xiàn)如下：

/*************************************************************************

FileName:vector_rotate_2.cpp

Author:SongLee

************************************************************************/

#include

#include

usingnamespacestd;

//歐幾里德輾轉相除算法求最大公約數(shù)

intgcdinti,intj

while1

ifij

i=i%j;

ifi==0

returnj;

ifji

j=j%i;

ifj==0

returni;

intmain

strings=abcdefghijklmn;

coutTheoriginis:sendl;

//左移個數(shù)

inti;

cini;

ifis.size

i=i%s.size;

//移動

chartmp;

inttimes=gcds.size,i;

forintj=0;j

tmp=s[j];

intpre=j;//記錄上一次的位置

while1

intt=pre+i;

ift=s.size

t=t-s.size;

ift==j//直到tmp原來的位置j為止

break;

s[pre]=s[t];

pre=t;

s[pre]=tmp;

coutTheresultis:sendl;

return0;

思路四：旋轉向量x實際上就是交換向量ab的兩段，得到向量ba，這里a代表x的前i個元素。假設a比b短。將b分割成bl和br，使br的長度和a的長度一樣。交換a和br，將ablbr轉換成brbla。由于序列a已在它的最終位置了，所以我們可以集中精力交換b的兩個片面了。由于這個新問題和原先的問題是一樣的，所以我們以遞歸的方式舉行解決。這種方法可以得到優(yōu)雅的程序，但是需要高明的代碼，并且要舉行一些斟酌才能看出它的效率足夠高。

//實現(xiàn)代碼略

思路五：最正確將這個問題看做是把數(shù)組ab轉換成ba，同時假定我們擁有一個函數(shù)可以將數(shù)組中特定片面的元素逆序。從ab開頭，首先對a求逆，得到arb，然后對b求逆，得到arbr。結果整體求逆，得到arbrr，也就是ba。

?

1

2

3

reverse0,i-1/*cbadefgh*/

reversei,n-1/*cbahgfed*/

reverse0,n-1/*defghabc*/

性能：求逆序的方法在時間和空間上都很高效，而且代碼分外簡短，很難出錯。

C++代碼實現(xiàn)如下：

/*************************************************************************

FileName:vector_rotate.cpp

Author:SongLee

************************************************************************/

#include

#include

usingnamespacestd;

voidreversestrings,intbegin,intend

whilebeginend

chartmp=s[begin];

s[begin]=s[end];

s[end]=tmp;

++begin;

--end;

intmain

strings=abcdefghijklmn;

coutTheoriginis:sendl;

inti;

cini;

ifis.size

i=i%s.size;

revers