雅乐网

分治策略其想法是把问题分成两个大致相等的子问题，然后分别求解，这是“分”的部分。“治”的阶段把两个子问题的解合并到一起，得到整个问题的解。

如果一个算法用常熟时间O(1)将问题的大小削减为一部分（通常是1/2），那么该算法的时间复杂度是O（logn）。

二分查找

#include <stdio.h>

int binarysearch(int a[], int numtofind, int n);	

int main(void)
{
	int a[] = {1,2,5,7,9,11,12,23,45,55,78,100};
	printf("%d\n", binarysearch(a, 1, 12));

	return 0;
}

int binarysearch(int a[], int x, int n)
{
	int low, high, mid;
	low = 0; high = n-1;

	while (low <= high)
	{
		mid = (low + high) / 2;
		if (x < a[mid])
			high = mid - 1;
		if (a[mid] < x)
			low = mid + 1;
		if (a[mid] == x)
			return mid;
	}
	return -1;
}

 欧几里得算法

求两个数的最大公约数

#include <stdio.h>

int gcd(int a, int b);	//Greatest Common Divisor

int main(void)
{
	int a, b;
	while (1)
	{
		printf("please input two numbers\n");
		scanf("%d %d", &a, &b);

		printf("the Greatest Common Divisor of %d and %d is %d\n",a, b, gcd(a, b));
	}
	return 0;
}

int gcd(int a, int b)
{
	int x;
	while (b > 0)
	{
		x = a % b;
		a = b;
		b = x;
	}
	return a;
}

 高效的幂运算

#include <stdio.h>

long power(int a, int b);	//

int main(void)
{
	int a, b;
	while (1)
	{
		printf("please input two numbers\n");
		scanf("%d %d", &a, &b);

		printf("pow %d of %d is %ld\n",a, b, power(a, b));
	}
	return 0;
}

long power(int a, int b)
{
	if (b == 0)
		return 1;
	if (b % 2 == 0)
		return power(a * a, b / 2);
	if (b % 2)
		return power(a * a, b / 2) * a;

}