app手机网站开发,网站建设教程.,凡科网站案例,福州企业建设网站【0】README1)本文旨在review 算法分析的几个算法问题 附带源码#xff1b;【1】最大子序列和问题的解#xff08;两种解法——分治法联机算法#xff08;推荐#xff09;#xff09;【1.1】分治法1#xff09;intro#xff1a;其思想是把问题分成两个大致相等的子问题【1】最大子序列和问题的解两种解法——分治法联机算法推荐【1.1】分治法1intro其思想是把问题分成两个大致相等的子问题然后递归地对它们进行求解这是“分”部分“治”阶段 将两个子问题的 解合并到一起并可能再做些少量的附加工作最后得到整个问题的解 2算法idea 描述在我们的例子中求最大子序列和的问题最大子序列和可能出现在三个地方——或者整个出现在输入数据的左半部、或者整个出现在右半部、或者跨越输入数据的中部从而占据左右两半部分3如何求其解呢 前两种情况可以递归求解第3种情况的最大和可以通过求出前半部分的最大和包含前半部分的最后一个元素以及 后半部分的最大 和包含后半部分的第一个元素而得到。然后将这两个和加在一起4算法流程演示和源码如下#includestdio.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(leftright){if(A[left] 0){return A[left];}else{return 0;}}center (leftright)/2; onlyLeftSum maxSubSum3(A, left, center);onlyRightSum maxSubSum3(A, center 1, right);centerLeftSum 0; tempSum 0; for(icenter; ileft; i--) { tempSum A[i];if(tempSum centerLeftSum){centerLeftSum tempSum;}}centerRightSum 0;tempSum 0;for(icenter1; iright; 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】联机算法1intro在任意时刻算法对要操作的数据只需要读入一次一旦被读入处理它就不再需要被记忆了。而在处理过程中算法对已读入的数据给出了正确的答案具有这种特性的算法叫联机算法2利用 联机算法求最大子序列和问题的解源码如下比 分治法效率高 #includestdio.h#define ElementType int// 联机算法计算最大子序列和问题.
int maxSubSequenceSum(int A[], int N)
{int thisSum0, maxSum0;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】运行时间中的对数【2.1】荔枝1——二分查找 #includestdio.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 N6, x109; 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——计算最大公因数欧几里得 算法 #includestdio.h#define ElementType int
#define NOTFOUND -1/* 求两个数的最大公因数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——高效率的幂运算 1减少乘法次数如 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)^22 2 2 2 1 9次 #includestdio.hint 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_);
}
