编程珠玑第二章习题3

// 编程珠玑第二章习题3.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

int gcd(int x, int y)// 编程之美上的高效算法
{
	if (x < y)
		swap (x, y);
	if (y == 0)
		return x;
	else 
	{
		if ((x&1) == 0)//x 是偶数
		{
			if ((y&1) == 0)//y 是偶数
				return gcd(x >>1, y>> 1) << 1;//左移就是乘二
			else 
				return gcd(x >> 1, y);
		}
		else 
		{
			if ((y&1) == 0)
				return gcd(x, y>> 1);
			else 
				return gcd(y, x-y);
		}
	}
}
void m_rotate(int *arr,int n,int len)
{
	int m=gcd(n,len);//the greatest common divider between n and len 
	//cout<<endl<<" m is "<<m<<endl;
	int temp,j;
	for (int i=0;i<m;i++)
	{
		temp=arr[i];
		j=i;
		int k;
		while (1)
		{
			k=j+len;
			if (k>=n)
			{
				k=k%n;//k=k-n;
			}
			if (k==i)
			{
				break;
			}
			arr[j]=arr[k];
			j=k;
		}
		arr[j]=temp;
	}

}
void reverse(int *arr,int i,int j)
{
	if (i>=j)
	{
		return;
	}
	int low=i,high=j;
	int temp;
	while(low<high)
	{
		temp=arr[low];
		arr[low]=arr[high];
		arr[high]=temp;
		low++;
		high--;
	}
}
void reverse_rotate(int *arr,int n,int m)
{
	reverse(arr,0,m-1);
	reverse(arr,m,n-1);
	reverse(arr,0,n-1);
}
int _tmain(int argc, _TCHAR* argv[])
{
	int arr[]={1,2,3,4,5,6};
	for (int j=0;j<6;j++)
	{
		cout<<arr[j]<<" ";
	}
	cout<<endl;
	//m_rotate(arr,6,3);
	reverse_rotate(arr,6,3);
	for (int j=0;j<6;j++)
	{
		cout<<arr[j]<<" ";
	}
	cout<<endl;
	system("pause");
	return 0;
}