to do
分治法在每一层递归上都有三个步骤：
step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
step3 合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
7. return(T)
- 其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。
- ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。
- 算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。
11.1] Pow(x, n)
careful with what the smallest subproblems have to be in order to work. Used myPowR to calculate the power to the 2 but will stuck in loop if didn't add base case if n==1 return x.
Also note to take care of negative n cases.
double myPowR(double x, int n) {
if (!n) return 1;
// if (n==1) return x;
int n_sub = n/2;
double inner = myPowR(x, n_sub);
return n%2 ? x*inner*inner : inner*inner;
}
double myPow(double x, int n) {
bool neg = n<0;
return neg? 1/myPowR(x, abs(n)) : myPowR(x, abs(n));
}
11.2] Sqrt(x)
take care of special cases. Careful not to overflow: use divide instead of multiple in order to compare.
int mySqrt(int x) {
if (x<2) return x;
int mid;
// took care of 0 case because can't divide by 0
for (int l=1, r=x; l<=r; ) {
mid=(l+r)/2;
if (mid==x/mid || (mid<x/mid && (mid+1)>x/(mid+1))) break;
if (mid>x/mid) {
r=mid-1;
} else {
l = mid+1;
}
}
return mid;
}
