配列回転問題の議論

質問:配列aの要素を左にi個の位置に回転します.
この問題は比較的簡単に見える.しかし、多くのアプリケーションでは、さまざまな偽装が行われています.この機能もベクトルの基本的な動作である.この問題について,本稿では3つの解決方法を提示する.
方法1
まず、aの前のi個の要素を一時配列にコピーし、残りのn−i個の要素を左にi個の位置を移動し、最後に最初のi個の要素を一時配列からaの残りの位置にコピーする.

void convert1(int a[], int n, int m)
{
	int *b = new int[m];                 //      
	for (int i = 0; i < m; i++)          //  m           
		*(b + i) = a[i];
	for (int i = m; i < n; i++)          //    n-m       m   
		a[i - m] = a[i];
	for (int i = 0; i < m; i++)          //    m            a      
		a[n-m + i] = b[i];
	delete[]b;                           //           
}

int main()
{
	int a[10];
	for (int i = 0; i < 10; i++)
		a[i] = i;

	convert1(a, 10, 5);

	for (int i = 0; i < 9; i++)
		cout << a[i] << ",";
	cout << a[9] << endl;
	return 0;
}

この方法で使用されるi個の追加の位置は、過大な記憶領域の消費を生じる.この方法は、メモリ容量が非常に貴重な場合には実行できません.
方法2
a[0]を一時変数tempに移動し、a[0+i]をa[0]に移動し、a[0+2*i]をa[0+i]に移動し、順次類推する.配列の下付き文字が配列の長さより大きい場合、現在の下付き文字から配列の長さを減算し、a[0]の値を取るまで戻り、tempから値を取るように変更して現在のループを終了します.このプロシージャがすべての要素を移動しない場合は、a[1]からすべての要素がすべて移動されるまで再び移動します.

int gcd(int a, int b)                                  //       i   a        
{
	int c;
	c = (a>b) ? b : a;
	while (a%c != 0 || b%c != 0)
	{
		c--;
	}
	return c;
}
void convert2(int a[],int n,int m)
{
	int temp;                              //    temp  
	for (int i = 0; i < gcd(m,n); i++)
	{
		int temp = a[i];               // a[0]       temp 
		int j=i;
		for (; ;)
		{
			int k = j + m;
			if (k>=n)             //             ，           
				k -= n;
			if (k == i)          //  a[0]   ，      
				break;
			a[j] = a[k];           // a[0+i]   a[0] 
			j = k;
		}	
		a[j] = temp;                // temp      a[0+n*i] 
	}
}

int main()
{
	int a[10];
	for (int i = 0; i < 10; i++)
		a[i] = i;

	convert2(a, 10, 5);

	for (int i = 0; i < 9; i++)
		cout << a[i] << ",";
	cout << a[9] << endl;
	return 0;
}

この方法では、メモリ消費量が短く、実行時間も長くありません.しかし,プログラムを記述する過程では困難であり,記述されたコードは比較的長い.
方法3
配列aの前のi個の要素をベクトルmと見なし,残りの要素をベクトルnと見なし,配列aをmnと表すことができる.では,配列aをiビット左にシフトすることは,実はmnをnmに変換することである.mnについては,まずnに対して逆を求め,次にmに対して逆を求め,最後に全体に対して逆を求めるとmnをnmに変換できる.

void convert3(int a[], int n, int m)
{
	if ((m - n) % 2 == 0)
	{
		for (int i = 0; i < (m - n) / 2; i++)
		{
			a[m - i] = a[m - i] ^ a[n + i];
			a[n + i] = a[n + i] ^ a[m - i];
			a[m - i] = a[m - i] ^ a[n + i];
		}
	}
	else{
		for (int i = 0; i <=(m - n) / 2; i++)
		{
			a[m - i] = a[m - i] ^ a[n + i];
			a[n + i] = a[n + i] ^ a[m - i];
			a[m - i] = a[m - i] ^ a[n + i];
		}
	}
		
}

int main()
{
	int a[10];
	for (int i = 0; i < 10; i++)
		a[i] = i;
	
	convert3(a, 0, 4);                       // m  
	convert3(a, 5, 9);                       // n  
	convert3(a, 0, 9);                       //     
	
	for (int i = 0; i < 9; i++)
		cout << a[i] << ",";
	cout << a[9] << endl;
	return 0;
}

この方法は時間的にも空間的にも効率的で、コードが非常に短く、エラーが発生しにくい.
反転の理解については、非常に古典的な例を参照することができる:Doug McIlroyが与えた10元配列を5つの位置に上方に選択する反転例.
ソースダウンロードリンク:https://github.com/XiaoYaoNet/Array-Convert