王晓东的《计算机算法设计分析》快速排序代码问题

与归并排序一样,快速排序也使用了分治思想。下面是对一个典型的子数组A[p..r] 进行快速排序的三步分治过程:


分解:数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[q+1..r]中的每个元素。其中,计算下标q也是划分过程的一部分。


解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]进行排序。


合并:因为子数组都是原址排序的,所以不需要合并操作:数组A[p..r]已经有序。


Paxos 算法

在常见的分布式系统中,总会发生诸如机器宕机或网络异常(包括消息的延迟、丢失、重复、乱序,还有网络分区)等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中,快速且正确地在集群内部对某个数据的值达成一致,并且保证不论发生以上任何异常,都不会破坏整个系统的一致性


信息熵最大值的证明

证明:当概率均等时信息熵最大。即当 $p_i=\frac{1}{n}$ 时,下面的 H 取得最大值。


\[H=-\sum\limits_{i=1}^{n} p_i log {p_i}=\log n\]


n 皇后问题

"教主" 楼天城 ony.ai CTO 在量子位微信公众号上出了一个问题:17皇后有多少组解?


我自己写了一份代码,代码如下


鸵鸟蛋测试

一场活动要测试鸵鸟蛋的坚固性。要让蛋从高楼上落下而不破,进而依据不破的最高楼层决定蛋的硬度。测试的高楼共101层。测试员意识到,如果他只带一颗鸵鸟蛋的话,他需要从第1层开始往上依次每一层把蛋投下以判定蛋的硬度。

如果他带两颗鸵鸟蛋(假定坚固性一样),那么在最坏的情况下他需要测试多少次呢?