to do
分治法在每一層遞歸上都有三個步驟：
step1 分解：將原問題分解為若干個規(guī)模較小糊肠，相互獨立惭笑，與原問題形式相同的子問題鼎兽；
step2 解決：若子問題規(guī)模較小而容易被解決則直接解熊咽，否則遞歸地解各個子問題
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的規(guī)模；n0為一閾值阱高，表示當問題P的規(guī)模不超過n0時赚导，問題已容易直接解出，不必再繼續(xù)分解赤惊。
- ADHOC(P)是該分治法中的基本子算法吼旧，用于直接解小規(guī)模的問題P。因此未舟，當P的規(guī)模不超過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;
}
