导读
王晓东的《计算机算法设计与分析》是一本很不错的书，里面算法题目很多而且很有难度，适合学习和练手。所以打算把它里面的习题都做完。
第二章
算法分析题
2-3 带上下界的折半查找
设$[ a[0:n] $[是已排好序的数组，请改写二分搜索算法，使得数据不存在时返回上界和下界。
template <typename ElemType>
int BoundBinarySearch(const ElemType data[], const ElemType &key, int len) {
if (len > 0) {
if (key < data[0]) return 0;
if (key > data[len - 1]) return len - 1;
int l = 0, r = len - 1;
while (l < r) {
int mid = (l + r) / 2;
//奇数个元素时，mid是中间元素，偶数个元素时则是偏左的那个中间元素。
if (key > data[mid]) l = mid + 1; //如果要查找的更大，则在右部分查找。
//注意这里必须+1，因为是偏左的元素，判断大于的话，就直接用mid的下一个元素，否则在0:1的适合会死循环
else r = mid; //否则在左部分查找
}
if (data[r] == key) return r;
else cout << r - 1 << " " << r << endl;
}
return -1;
}
2-4 大整数乘法的 $[\Theta (mn^{\log{\tfrac{3}{2}}} )$[ 算法
给定2个大整数$[u$[和$[v$[，他们分别有$[m$[位和$[n$[位数字，且 $[ m \leq n $[。 当m远小于n时，我们采用第二章的分治法，效率不高。试设计一个算法，在$[m$[远小于$[n$[时，用$[\Theta (mn^{\log{\tfrac{3}{2}}} )$[的时间求出$[uv$[的值。
答:当 $[m$[ 远小于 $[n$[ 时，将 $[v$[ 分成 $[n/m$[ 段，每段 $[m$[ 位。计算 $[uv$[ 需要 $[n/m$[ 次 $[m$[ 位乘法运算。每次 $[m$[ 位乘法耗时 $[\Theta (m^{\log{3}})$[。因此，算法所需要的计算时间是$[\Theta ((n/m)m^{\log{3}}) = \Theta (nm^{\log{\tfrac{3}{2}}})$[。
2-8 不动点问题的$[\Theta (\log{n})$[时间算法
设$[n$[个不同的整数排好序后存于$[T[0:n]$[中。若存在一个下标$[i$[, $[1\leq i<n$[,使得$[T[i] = i$[,设计一个算法找到这个下标。要求算法在最坏情况下的计算时间为$[\Theta (\log{n})$[。
答： 由于$[n$[个整数互不相同，假设 $[k_1,k_{2} \lbrack k_{1} < k_{2} \rbrack $[ 分别是2个数字的下标,则 $[T[k_{2}]-T[k_{1}] > k_2 - k_1 $[ 即 $[T[k_{2}] - k_2 > T[k_{1}] - k_1$[ 。这说明了$[T[i]-i$[随着$[i$[的增加而增加，所以可以采用折半查找法来求解。 注意要是该数组$[T[0:n]$[存在相同元素，则上式并不成立，也就不能采用折半查找法来求解了。
代码：
template<typename ElemType>
FindIdxEqualToElem(const ElemType data[], int len) {
if (len > 0) {
int l = 0, r = len - 1;
while (l < r) {
int mid = (l + r + 1)/2;
if (mid > data[mid]) l = mid + 1;
else r = mid;
}
if (data[l] == l) {return data[l];}
}
return -1;
}
2-9 有序主元素问题
设 $[T[0:n]$[ 是n个元素的数组，数组中元素具有序关系。对于任意元素 $[x$[ ,设 $[S_x = { i | T[i] = x}$[ 。当 $[ S_{x} > n/2$[ 时，称 $[x$[ 是 $[T$[ 的主元素。设计一个线性时间算法，确定 $[T[0:n]$[ 是否有一个主元素。
答： 如果 $[T$[ 有主元素 $[x$[ ,则 $[x$[ 是 $[T$[ 的中位数。 反之, 如果 $[T$[ 的中位数不是 $[T$[ 的主元素, 则 $[T$[ 没有主元素. 因此, 采用 线性时间选择算法 则可在线性时间内判定 $[T$[ 是否有主元素.
template<typename ElemType>
boolean Majority(ElemType T[], int len) {
ElemType m = Select(T, len/2); //Select是从数组T中选择第k大的元素
int count = 0;
for (int i = 0; i < len; ++i) {
if (T[i] == m) ++count;
}
if (count > len/2)
return count;
else
return -1;
}
2-10 无序主元素问题
在上面的2-9问题中, 如果数组 $[T$[ 中的元素不存在序关系, 即我们只能测试两个元素是否相等. 设计一个有效的算法, 确定 $[T$[ 中是否存在主元素. 算法复杂度应为 $[\Theta (n\log{n})$[ . 更进一步, 是否能找到一个线性时间的算法?
答:
- 我们用分治法来找 $[T[0:n]$[ 的主元素.
如果 $[x$[ 是 $[T$[ 的主元素, 则把数组等分为 $[T[0:\lfloor n/2 \rfloor]$[ 和 $[T[\lfloor n/2 \rfloor:n]$[ . 则主元素 $[x$[ 必然位于其中一个子数组. 反之, 如果两个子数组中都不存在主元素, 则合并之后的数组必然也没有主元素.
template<typename ElemType>
boolean isMajority(ElemType T[], int l, int r, ElemType m) {
int count = 0;
for (int i = l; i < r; ++i) {
if (T[i] == m) ++ count;
}
return count > (r - l + 1)/2;
}
template<typename ElemType>
ElemType* MajorityRecur(ElemType T[], int l, int r) {
if (r - l <= 3) {
for (int i = l; i < r; ++i) {
if (isMajority(T, l, r, T[i])) return &T[i];
}
return nullptr;
} else {
ElemType *lmain = MajorityRecur(T, l, (l + r + 1)/2);
if (isMajority(T, l, r, *lmain)
return lmain;
ElemType *rmain = MajorityRecur(T, (l + r + 1)/2, r);
if (isMajority(T, l, r, *rmain)
return rmain;
else
return nullptr;
}
}
template<typename ElemType>
boolean Majority(ElemType T[], int len) {
ElemType * pm = MajorityRecur(T, 0, len);
if (pm != nullptr) return isMajority(T, 0, len, *pm);
else return false;
}
- 采用以下策略可以在 $[\Theta (n)$[ 的时间内找到 $[T[0:n]$[ 的主元素.
我们将这些元素分成 $[n/2$[ 组. 例如我们这样分组(0,1), (2,3), (4,5)... 然后我们把每个组里面相同的那些元素留下来组成另一个数 $[Q$[ . 如果是奇数个元素,则最后一个元素也加入到 $[Q$[ 中. 则有以下结论:
如果 $[T$[ 有主元素 $[x$[, 则 $[x$[ 必然在 $[Q$[ 中.
简单描述该结论的正确性: 我们可以认为是去掉了不同的组的元素. 那不同的组的元素情况必然有以下2种情况.
1. 两个元素都不是主元素, 则去掉了之后,留下的部分必然主元素保持不变.
2. 有一个元素是主元素, 这种情况下, 非主元素和主元素都去掉了一个, 留下的部分的主元素还是保持不变.
故上面的结论成立.
我们注意到,其实该结论反过来并不一定可行,也就是说 $[Q$[ 有主元素,并不代表 $[T$[ 有主元素. 因为上面的第一种情况会导致一种情况: $[T$[不存在主元素,但是 $[Q$[ 存在主元素. 故我们采用折半方法找到主元素 $[x$[ 之后,必须重新遍历一边验证该元素是否是主元素.
//尾递归版本
template<typename ElemType>
ElemType *PossibleMajorityRecur(ElemType T[], int len) {
if (len <= 3) {
for(int i = 0; i < 1; ++i) {
if (isMajority(T, 0, len, T[i])) {
return &T[i];
}
}
return nullptr;
} else {
int pos = 0;
for (int i = 0; i < n/2; ++i) {
if (T[i] == T[i + n/2]) {
std::swap(T[pos], T[i]);
++pos;
}
}
return PossibleMajorityRecur(T, pos);
}
}
template<typename ElemType>
boolean Majority(ElemType T[], int len) {
ElemType * pm = PossibleMajorityRecur(T, len);
if (pm != nullptr) return PossibleMajorityRecur(T, 0, len, *pm);
else return false;
}
- 采用另一种策略,我们可以更好的完成这个题目, 策略如下:
令count = 1,并把第一个元素假设为主元素x, 从数组的第二个开始,如果与假定的主元素x相等,则count加1, 如果不相等,则减1. 如果count等于0, 则把这个位置的元素重设为主元素.
该方法其实本质上与第二种方法的原理是一致的. 我们考虑,第i次比较时,这时count等于0, 这说明前面已经比较过的部分的计数刚好一半是主元素,一半是非主元素, 或者 全部不是主元素, 或者 一半以下是主元素,还有一部分是一些相同的不是主元素的元素. 则主元素如果存在,则必然在这剩下的部分里面. 最终,我们可以找出主元素. 不过该算法也不能确保最后找到的一定是主元素. 我们可以再遍历一次,确认是否是主元素.
这种方法的代码特别简单, 这里就不提供了.
2-11 $[\Theta (1)$[ 空间数组换位问题
设 $[a[0:n]$[ 是一个n个元素的数组. $[k (1\leq k \leq n-1))$[ 是一个非负整数. 试设计一个算法,将数组 $[a$[ 中的 $[a[0:k]$[ 和 $[a[k:n]$[ 换位. 要求算法在最坏的情况下时间复杂度是 $[\Theta (n)$[ , 且只用到 $[\Theta (1)$[ 的辅助空间.
答:
- 手摇算法
首先将数组 $[a[0:n]$[ 反转一次, 然后再将 $[a[0:n-k]$[ 和 $[a[n-k:n]$[ 分别反转一次. 这样就可以得到最后的结果. 原理非常简单.举例如下
[0, 1, 2, 3, 4,|5, 6, 7] n=8; k = 5;
[7, 6, 5,|4, 3, 2, 1, 0] n-k=3;
[5, 6, 7, 0, 1, 2, 3, 4]
template<typename ElemType>
void Reverse(ElemType a[], int l, int r) {
if (r > l) {
int leftpos = l, rightpos = r - 1;
while(leftpos < rightpos) {
std::swap<ElemType>(a[leftpos], a[rightpos]);
--leftpos; --rightpos;
}
}
}
template<typename ElemType>
void RoundShift(ElemType a[], int len, int pos) {
if (pos > len || len < 0 || pos < 0) {
return;
}
Reverse<ElemType>(a, 0, len);
Reverse<ElemType>(a, 0, len - k);
Reverse<ElemType>(a, len - k, len);
}
- 排列循环算法
我们可以认为新数组是原来的数组的一个重新排列的过程. 因此这个新数组对应着原来数组的一个置换.
定理: 对于给定的数组 $[a[0:n]$[ 向后循环换位 $[n-k$[ 位运算, 可分解为恰好 $[\gcd({k},{n-k})$[ 个循环置换. 且 $[0, ..., \gcd(k, n-k)-1$[ 中每个数分别恰好属于一个循环置换.
$$\Gamma \Delta \Theta \Lambda \Xi \Pi \Sigma \Upsilon \Phi \Psi \Omega \alpha \beta \gamma \delta \epsilon \zeta \eta \theta \iota \kappa \lambda \mu \nu \xi \omicron \pi \rho \sigma \tau \upsilon \phi \chi \psi \omega \varepsilon \vartheta \varpi \varrho \varsigma \varphi \approx \cong \ge \geq \le \leq \ne \neq \ngeq \nleq \in $$