分治策略其想法是把问题分成两个大致相等的子问题，然后分别求解，这是“分”的部分。“治”的阶段把两个子问题的解合并到一起，得到整个问题的解。
如果一个算法用常熟时间O(1)将问题的大小削减为一部分（通常是1/2），那么该算法的时间复杂度是O（logn）。
二分查找
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#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; } |
欧几里得算法
求两个数的最大公约数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#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; } |
高效的幂运算
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#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; } |
支付宝打赏 
微信打赏