読者です 読者をやめる 読者になる 読者になる

配列要素の回転

配列要素の回転

目的

配列の要素を循環させながらシフトさせたい。
例) 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;
}

参考文献

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造

広告を非表示にする