这两个东西在某一类问题里面是同质的。这就是以前说过的只有两个安全套又要4p的问题。（以下文字来自yueweitang）

岛国上流行一种极易接触传染的病
一旦染上该病1月后病发身亡
但该病可通外科手术治愈

岛上每个人都有已被传染的可能
国王怀疑自己得了该病
在该岛上找到了医术最高名的3个医生
并要求这3个医生在当天轮流给自己动手术
然而已消毒过的手术手套只有2双
怎样最安全

现在把问题一般化，假设岛上有n个医生，还有m个（非医生）居民。现在岛上流行一种极易接触传染的病。每个居民要想治愈传染病，必须得到这n个医生的治疗，治疗的顺序无所谓（先别管这种假设的由来）。怎么安排它们手术的次序和带手套的方案，使得所用的手术手套最少。

注一：医生也有可能已被传染，故他们之间也要防止相互感染。
注二：手套可以套着用…还可以反着用…

下面的解答作者是JtR，来自水母IQDoor版。

用{m/2}+{n/2}+{n/4}(m<=n)双手套即可。{}表示向上取整。

为了叙述方便，假设m是2的倍数，n是4的倍数，不是4的倍数时类似，只是手套的“利用率”没有那么高。可能可以通过优化减少一副到两副。

1.将医生平均分为两组，分别为A，B。各m/2人；
将病人分为三组，人数分别为a＝n/2，b=n/4，c=n/4

2.将m/2副手套分配给A，n/2副手套分配给a，A中的每一个医生检查a中的每一个病人；
检查前均在自己的手套外套上指定给该病人的手套；
注意所有的手套均只有一面污染。（假设医生之间也要防止相互感染）

3.将分配给a的n/2副手套中的一半翻转，两两一组套在一起，污染面互相接触，此时每一组手套内外均无污染；将这n/4组手套分配给b(n/4人）；
将剩下的未使用过的n/4只手套分配给c(n/4人）；

4.A中的每一位医生分别检查b，c中的病人，检查前均在自己的手套外套上指定给该病人的手套（或两只套在一起的手套）；
这样A中的医生完成对所有病人的检查，而且医生的手套外侧和指定给病人的手套内侧(注意有n/4是翻转过的)均无污染。

5.A中所有的医生将各自的手套翻转后给B中的医生戴上；
b中的病人把套在一起的手套里面的那只抽出来翻转后套入c组病人的手套中。此时c组的手套每一组相互接触的面都是干净的；

6.B中所有的医生按前述方法给b，c两组病人检查；

7.将c组的手套两两分开，把套在外面的手套翻转，这样得到n/2只外侧干净的手套重新分配给a组的病人。

8.B中的所有医生检查a组的病人。

这样就完成了所有医生对病人的检查。

如果医生的数量比病人多只要把医生和病人交换即可。在该问题中二者是对称的。

 

一个单位正方形的土地，其内（包括边界）建一些篱笆，使得任何与正方形相交的线段都被篱笆阻断（即与篱笆相交），问所建篱笆的总长度最少要多长？

 

肯定每个顶点都要有线通过。考虑三角形的情况，这很简单，因为每个底和高的组合都是最短的。那么扩展到多边形，首先一条对角线，划分为两个小的多边形，然后从其中一个多边形的顶点向该对角线画垂线。对于已有多条直角相交的划分线，那么与该“勾”和“股”对应的“弦”也是一条隐形的划分线。不过其长度不计算在内，但是新垂线和该“弦”垂直就行了。比如说，长和宽不相等的矩形，“篱笆”就不是两对角线，而是先做一条对角线，然后从剩下的两个顶点分别引垂线到对角线上，这三条线段长度之和就是“篱笆长度”。

--------------------------------------------------------------------------------------------

现在看来这是错误的。三角形的情况是费马点向顶点的连线。正方形的情况？估计是其中三个顶点做个费马点，然后从第四个点引垂线到对角线上。这样篱笆的长度应该最小。

----------------------------------------------------------------------------------------------

这个月的ponder this 答案出来了，哈，看来我的是对的。

答案网址：http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/July2007.html

a:设矩阵为A[m][n]现从A[0][0]进，从A[m-1][0]出，要求经历所有矩阵中的点，且不重复访问任何点，问总共有多少种路径？

 

b:有一个矩阵，每个元素是一个数，要求，从左上角出发到达右下角，每次只能向右或向下，要求全路线经过的元素和最小，求出路径及这个和的值。要求分别用递归和非递归方法实现之。

 

以上题目来自yueweitang

算法题一：Given 1 GB memory, input a file which contians 4 billion integers,
output one integer that is not in the file. What if you have only 10 MB
memory?

算法题二：There are 100 hundred sorted arrays, and each of them contains 100
numbers. Give an algorithm to merge them into a single sorted array, using
only one temporary array in the middle steps.

编程题：Input an integer array of size n and an integer k (k<=n), output all
subsets of size k.

以上题目来自著名博客yueweitang。