By Long Luo
题目:
将一个n元一维数组a[n]左移i个位置。例如,当n=8,i=3时,数组abcdefgh旋转为defghabc。请设计一个算法完成这个任务。
解答
杂技算法
分析:将a[0]存储在一个临时变量中,然后将a[i]替换a[0],a[2i]替换a[i]….当一个循环结束的时候,若替换次数小于n,则从a[1]开始替换…,需要经过gcd(n,i)(n和i的最大公约数)次循环后,才能把每一个元素都移到该移的地方。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
|
#include <iostream> #include <string>
using namespace std;
string AcrobatRotateShift(string str, int n);
int main(void) { string str1 = "abcdefg"; string str2 = "";
cout<<"str1= "<<str1<<endl; cout<<"str2= "<<str2<<endl;
str2 = AcrobatRotateShift(str1, 2);
cout<<"str1= "<<str1<<endl; cout<<"str2= "<<str2<<endl;
getchar();
return 0; }
string AcrobatRotateShift(string str, int n) { int strlen = str.length(); int count = 0; int i, j = 0; char temp;
while (1) { temp = str[j]; i = (j + n) % strlen;
while (i != j) { str[(i - n + strlen) % strlen] = str[i]; count++; i = (i + n) % strlen; }
str[(j - n + strlen) % strlen] = temp; count++;
if (count < strlen) { j++; } else { break; } }
return str; }
|
翻转算法
我们将问题看成把数组ab转换成ba,同时假定我们拥有一个函数可以将数组中的特定部分元素求逆。从ab开始,先对a求逆,得到ar b,然后对b求逆,得到ar br ,然后整体求逆,得到(ar br)r 。此时就是ba。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
|
#include <iostream> #include <string>
using namespace std;
string Reverse(string str, int m, int n); string InverseRotateShift(string str, int n);
int main(void) { string str1 = "abcdefg"; string str2 = "";
cout<<"str1= "<<str1<<endl; cout<<"str2= "<<str2<<endl; str2 = InverseRotateShift(str1, 5);
cout<<"str1= "<<str1<<endl; cout<<"str2= "<<str2<<endl;
getchar();
return 0; }
string Reverse(string str, int m, int n) { char temp;
while (m < n) { temp = str[m];
str[m] = str[n]; str[n] = temp;
m++; n--; }
return str; }
string InverseRotateShift(string str, int n) { int strlen = str.length();
str = Reverse(str, 0, n-1); str = Reverse(str, n, strlen-1); str = Reverse(str, 0, strlen-1);
return str; }
|
*** Modified By Long Luo at 2018年10月1日 in Shenzhen, China.***