分治与递归（练习题）

问题1：使用递归倒叙输出数字
输入 ： 12345
输出 ： 54321

void ReversePrint(int a)
{
    
	if (a <= 0)
	{
    
		printf("\n");
		return;
	}

	printf("%d", a % 10);
	ReversePrint(a / 10);
}

问题2：无序数组的查询（递归）

int Find_ar(int* ar, int pos, int len,int val)
{
    
	if (ar[pos] == val)
		return pos;
	else if (pos == len)
		return -1;

	return Find_ar(ar, ++pos, len, val);
}

问题3：有序数组折半查找（递归和循环）

int Binary(int* ar, int val, int left,int right)//递归
{
    
	int mid = (int)((left + right)*0.5);
	
	if (ar[mid] == val)
	{
    
		return mid;
	}
	else if (ar[mid] > val)
	{
    
		return Binary(ar, val, left, mid - 1);
	}
	else if (ar[mid] < val)
	{
    
		return Binary(ar, val, mid + 1, right);
	}
	return -1;
}

int Binary2(int *ar, int len, int val)//循环
{
    
	int left = 0;
	int right = len;
	int mid;
	while (left <= right)
	{
    
		mid = (left + right) / 2;
		if (val < ar[mid])
			right = mid - 1;
		else if (val > ar[mid])
			left = mid + 1 ;
		else return mid;
	}
	return -1;
}

问题4：全子集问题

void Swap(int& a, int& b)//交换
{
    
	int tmp = a;
	a = b;
	b = tmp;
}

void Perm(int* ar, int pos, int len)//全子集
{
    
	if (pos == len)
	{
    
		int i = 0;
		for (; i < len; i++)
		{
    
			printf("%d", ar[i]);
		}
		printf("\n");
	}
	else {
    
		for (int i = pos; i < len; i++)
		{
    
			Swap(ar[i], ar[pos]);
			Perm(ar, pos + 1, len);
			Swap(ar[pos], ar[i]);
		}
	}	
}

问题5：查找数组中的值，没有返回将被插入的位置

int BinarySearch2(int *a, int length, int key)
{
    
	
	int low = 1;      
	int high = length; 
	int mid;
	while (low <= high)
	{
    
		mid = (low + high) / 2;  
		if (key<a[mid])     
			high = mid - 1;     
		else if (key>a[mid]) 
			low = mid + 1;    
		else
			return mid;      
	}
	return mid;
}

问题6：贪吃的小Q

int GetMaxNum(int outday, int chocolateNum)
{
    
	int left = 1;
	int right = chocolateNum;

	while (left <= right)
	{
    
		int mid = (left + right) / 2;
		bool enough = true;
		int remind = chocolateNum;
		int eat = mid;

		for (int i = 0; i < outday; i++)
		{
    
			if (eat > remind)
			{
    
				enough = false;
				break;
			}
			remind -= eat;
			eat = (eat + 1) / 2;
		}
		if (enough)
			left = mid + 1;
		else right = mid - 1;
	}
	return right;
}

问题7：寻找旋转数组的最小值

int FindMin(int* nums, int numsSize)
{
    
	int left = 0;
	int right = numsSize - 1;
	int mid;
	while (left <= right)
	{
    
		mid = left + ((right - left) / 2);
		if (nums[mid] > nums[right])
			left = mid + 1;
		else
		{
    
			if (nums[mid] < nums[mid - 1])
				return nums[mid];
			right = mid;
		}
	}
	return nums[mid];
}

问题8：使用二分法查询二维数组

bool FindArrMin(int* num, int rows, int columns,int val)
{
    
	bool found = false;

	if (num != NULL&&rows != 0 && columns != 0)
	{
    
		int row = 0;
		int column = columns - 1;

		while (row < rows&&column >= 0)
		{
    
			if (num[row*columns + column] == val)
			{
    
				found = true;
				break;
			}
			else if (num[row*columns + column]>val)
				--column;
			else ++row;
		}
	}
	return true;
}

问题9：寻找峰值

int Peak(int *ar, int len)//寻找峰值
{
    
	if (ar == NULL || len == 1)
		return -1;
	int left = 0;
	int right = len - 1;
	int mid = 0;
	if (ar == NULL || len == 1)
		return -1;
	int left = 0;
	int right = len - 1;
	int mid = 0;
	while (left < right)
	{
    
		mid = left + (right - left) / 2;
		if (ar[mid] >= ar[mid - 1] &&  ar[mid] >= ar[mid + 1])
		{
    
			return mid;
		}
		else if (ar[mid] > ar[mid + 1])
		{
    
			right = mid - 1;
		}
		else left = mid + 1;
	}
	return mid;
}

问题10：my_sqrt()的简单实现

int my_sqrt(int num)
{
    
	if (num < 0)
		return -1;
	int i = 0;
	for (;; i++)
	{
    
		if (i*i == num)
			return i;
		else if(i*i>num)
			return i - 1;
	}
}