配列要素の回転
配列要素の回転
目的
配列の要素を循環させながらシフトさせたい。
例) a[10] = {0,1,2,3,4,5,6,7,8,9}
4だけシフト
▶︎{4,5,6,7,8,9,0,1,2,3}
解法
a : 配列の先頭から、シフト数分の要素の集合
b : a集合以外の要素の集合
とする。
例)arr[10] 4シフト
a : arr[0]~arr[3]
b : arr[4]~arr[9]
a^rをaの"逆転"と定義し、以下の動作を表す。
例)
a ={0,1,2,3}
a^r = {3, 2, 1, 0}
与えられる配列をabとし、出力目標をbaとする。
(1) a^r b をつくる
(2) a^r b^rをつくる
(3) (a^r b^r) ^rをつくる。
(a^r b^r)^r = (ba)となり、上記の(1)~(3)を行うことで出力値を導く。
コード(C++)
/* *2014/10/5 *循環配列の要素を指定回数分だけ左シフトする。 * * 参考書籍 * ジョン・ベントリー著 * 珠玉のプログラミング */ #include<iostream> using namespace std; #define ARRAY_SIZE 10 void revArray(int* array, int num); void reverse(int* array, int a, int b); int main(void) { int array[ARRAY_SIZE] = {0,1,2,3,4,5,6,7,8,9}; //対象配列 int num = 3; //回転数 revArray(array,num); return 0; } void revArray(int* array,int num) { reverse(array, 0, num-1); reverse(array, num, ARRAY_SIZE-1); reverse(array, 0, ARRAY_SIZE-1); } void reverse(int* array,int a,int b) { for(int i=a,j=b; i<=((b-a)/2)+a; i++,j--){ int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } for(int i=0; i<ARRAY_SIZE; i++){ cout << array[i] << ","; } cout << endl; }