【0】README 1)本文旨在review 算法分析的幾個(gè)算法問題 附帶源碼；
【1】最大子序列和問題的解（兩種解法——分治法+聯(lián)機(jī)算法（推薦）） 【1.1】分治法 1）intro：其思想是把問題分成兩個(gè)大致相等的子問題，然后遞歸地對它們進(jìn)行求解，這是“分”部分；“治”階段 將兩個(gè)子問題的?解合并到一起并可能再做些少量的附加工作，最后得到整個(gè)問題的解；
2）算法idea 描述：在我們的例子中（求最大子序列和的問題），最大子序列和可能出現(xiàn)在三個(gè)地方——或者整個(gè)出現(xiàn)在輸入數(shù)據(jù)的左半部、或者整個(gè)出現(xiàn)在 右半部、或者跨越輸入數(shù)據(jù)的中部從而占據(jù)左右兩半部分； 3）如何求其解呢？ ?前兩種情況，可以遞歸求解，第3種情況的最大和可以通過求出前半部分的最大和（包含前半部分的最后一個(gè)元素）以及 后半部分的最大?和（包含后半部分的第一個(gè)元素）而得到。然后將這兩個(gè)和加在一起；

4）算法流程演示和源碼如下： #include<stdio.h>#define ElementType intint max3(int i, int j, int k) {if(i < j){i = j;}if(i < k){i = k;}return i; }// compute the maximum sum of sebsequence. // 3 in mxSubSum3 means 3 possibilities. int maxSubSum3(int A[], int left, int right) {int onlyLeftSum, onlyRightSum; // just only left or right sum without center.int centerLeftSum, centerRightSum; // the 3rd is passing center.int tempSum;int center, i;if(left==right){if(A[left] > 0){return A[left];}else{return 0;}}center = (left+right)/2; onlyLeftSum = maxSubSum3(A, left, center);onlyRightSum = maxSubSum3(A, center + 1, right);centerLeftSum = 0; tempSum = 0; for(i=center; i>=left; i--) { tempSum += A[i];if(tempSum > centerLeftSum){centerLeftSum = tempSum;}}centerRightSum = 0;tempSum = 0;for(i=center+1; i<=right; i++) { tempSum += A[i];if(tempSum > centerRightSum){centerRightSum = tempSum;}}printf("onlyLeftSum=%d, onlyRightSum=%d, centerLeftSum + centerRightSum=%d \n", onlyLeftSum, onlyRightSum, centerLeftSum + centerRightSum);return max3(onlyLeftSum, onlyRightSum, centerLeftSum + centerRightSum); } int main() {int N = 8, maxSum = 0; ElementType A[] = {4, -3, 5, -2, -1, 2, 6, -2}; maxSum = maxSubSum3(A, 0, N-1); printf("the maximum sum of array {4, -3, 5, -2, -1, 2, 6, -2} is: %d \n", maxSum); } 【1.2】聯(lián)機(jī)算法 1）intro：在任意時(shí)刻，算法對要操作的數(shù)據(jù)只需要讀入一次，一旦被讀入處理，它就不再需要被記憶了。而在處理過程中，算法對已讀入的數(shù)據(jù)給出了正確的答案，具有這種特性的算法叫聯(lián)機(jī)算法； 2）利用 聯(lián)機(jī)算法求最大子序列和問題的解，源碼如下（比 分治法效率高）
#include<stdio.h>#define ElementType int// 聯(lián)機(jī)算法計(jì)算最大子序列和問題. int maxSubSequenceSum(int A[], int N) {int thisSum=0, maxSum=0;int j; for(j = 0; j < N; j++) {thisSum += A[j];if(thisSum > maxSum){maxSum = thisSum;}else if(thisSum < 0){thisSum = 0;}}return maxSum; }int main() {int N = 8, maxSum = 0; ElementType A[] = {4, -3, 5, -2, -1, 2, 6, -2}; maxSum = maxSubSequenceSum(A, N);printf("the maximum sum of array {4, -3, 5, -2, -1, 2, 6, -2} is %d \n", maxSum); return 0; } 【2】運(yùn)行時(shí)間中的對數(shù) 【2.1】荔枝1——二分查找? #include<stdio.h>#define ElementType int #define NOTFOUND -1/* 二分查找，A[]升序排列 */ int binarySearch(ElementType A[], ElementType x, int N) {int low, mid, high;low = 0;high = N - 1;while (low <= high){mid = (low + high) / 2;if(A[mid] < x){low = mid + 1;}else if(A[mid] > x){high = mid - 1; }else {return mid;}}return NOTFOUND; } main() {int A[]={4, 5, 67, 67, 109, 876};int N=6, x=109; printf("\narray[] = {4, 5, 67, 67, 109, 876}");printf("\nthe position whose value equals to %d is %4d\n", x, binarySearch(A, x, N)); } 【2.1】荔枝2——計(jì)算最大公因數(shù)（歐幾里得 算法）
#include<stdio.h>#define ElementType int #define NOTFOUND -1/* 求兩個(gè)數(shù)的最大公因數(shù)（greatest common divisor） */ int gcd(int M, int N) {int rem;printf("remainder sequence: ");while (N > 0){rem = M % N;M = N;N = rem;printf("%4d", rem);}return M; }main() {int N = 1989, M = 1590; int gcd_value;printf("\t\t\t ========== test for greatest common divisor ==========\n\n"); gcd_value = gcd(M, N);printf("\nthe greatest common divisor between %4d and %4d is %4d\n", M, N, gcd_value);} 【2.1】荔枝3——高效率的冪運(yùn)算
1）減少乘法次數(shù)：如 X^62 只用到了9次乘法： X^3=(X^2)*X ,?X^7=(X^3)^2*X ,?X^15=(X^7)^2*X ,?X^31=(X^15)^2*X ,?X^62=(X^31)^2 2 + 2 + 2 + 2 + 1 == 9次；? #include<stdio.h>int isEven(int N) {return N % 2 == 0 ? 1 : 0; }int pow(int x, int N) {if(N == 0){return 1;}else if(N == 1){return x;}else if(isEven(N)) /* if(x) == if(N!=0) */{return pow(x * x, N / 2);}else{return pow(x * x, N / 2) * x;} }void main() {int x = 2, N = 7;long pow_ = pow(x,N);printf("\t\t\t ========== test for computing pow ==========\n");printf("\t\t\t result of %d^%d is %-6d\n", x, N, pow_); }

總結(jié)

以上是生活随笔為你收集整理的ReviewForJob(2)算法分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。