(learn&think)

不浮躁，不自傲，学习，思考，总结

Algorithm Design Manual Chapter 1

| Comments

Book Notes

Combinatorial Objects

  • Permutations - arrangements, or orderings, of items (“arrangement” “tour” “ordering” or “sequence” )
  • Subsets - selections from a set of items (“cluster” “collection” “committee” “group” “packaging” or “selection”)
  • Trees - hierarchical relationships between items (“hierarchy” “dominance relationship” “ancestor/descendant relationship” or “taxonomy”)
  • Graphs - relationships between arbitrary pairs of objects (“network” “circuit” “web” or “relationship”)
  • Points - locations in some geometric space (“sites” “positions” or “locations.)
  • Polygons - regions in some geometric spaces (“shapes” “regions” or “boundaries”)
  • Strings - sequences of characters or patterns. (“text” “characters” “patterns” or “labels”)

Recursive Objects

Big things that are made from smaller things of exactly the same type as the big thing. A decomposition rule describes how to get smaller things from big things.

As all combinatorial objects above are recursive objects here are a few possible decompositon rules for them:

  • Permutations - Deleting the first/last element of a permutation
  • Subsets - Deleting an element n if present
  • Trees - Deleting the root (results in a set of subtrees), deleting a leaf (a smaller tree)
  • Graphs - Deleting a vertex, dividing vertices to groups
  • Point - divide them to groups
  • Polygons - Inserting any internal chord between two nonadjacent vertices
  • Strings - Deleting a character (first or last)

Exercises

1-28.

Write a function to perform integer division without using either the / or * operators. Find a fast way to do it. 

void DivideCore(int m, int n, int *quot, int *rem) {
  rem = m;
  quot = 0;
  while (rem >= n) {
    rem -= n;
    quot++;
  }
}

void Divide(int m, int n, int *quot, int *rem) {
  int mult_n = 0;
  int last_n;
  while (m % n == 0) {
    last_n = n;
    n = n + n;
    mult_n++;
  }
  DivideCore(m, n, quot, rem);
  for (int i = 0; i < mult_n; ++i) {
    quot = quot + quot;
  }
}

1-29.

There are 25 horses. At most, 5 horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done.

7 次。

  1. 5 次：25 匹分成 5 组，比赛 5 次，得到前 5 名。
  2. 6 次：前 5 名比赛一次。因为只要得到前 3 名，这里剔除 5 名中的 2 名，剩下的 3 匹按比赛排名所在组为 G1，G2，G3。
  3. 7 次：G3 组只能去角逐第 3 名，派第一名 G31,G2 组只能去角逐第 2,3 名，派第一，二名，G21 和 G22。G1 组 G11 已经是第一名，去角逐第 2,3 名，派 G12,G13。最后 G12,G13，G21，G22 和 G31，得到第二，三名。

1-30.

How many piano tuners are there in the entire world?

需要把问题分解：1.世界有多少架钢琴;2.每位钢琴调音师能调多少台钢琴。

估算世界有多少架钢琴，需要知道：

  1. 世界的人口。
  2. 拥有钢琴的人口比例。
  3. 拥有钢琴的学校，教堂等场所的数量。

估算每位钢琴调音师能调多少台钢琴，需要知道：

  1. 每架钢琴平均多久需要调音一次。
  2. 对钢琴调音需要多长时间。
  3. 调音师的工作时间。
  4. 世界人口 70 亿，70×109 。
  5. 人口中弹奏乐器的人约占 10%（肯定大于 1%,小于 100%），其中最多 10%的人弹奏钢琴，而其中拥有钢琴的比例为 2%-3%，约人口总数 2×10-3 。每 5000-10000 个人有一座教堂，每座教堂有一架钢琴，每 500-1000 个学生有一所学校，每所学校有一架钢琴，每人大约拥有 3×10-3 架钢琴，所以钢琴数 70×109 × 3×10-3 = 2.1 * 108 。
  6. 钢琴调音的频率低于每月一次但多于 10 年一次，估计为一年一次。
  7. 调音所需时间多余 30 分钟，少于 1 天，估计为 2 小时。或钢琴有 88 个键，如果每个键花 1 分钟，需要 1.5 小时，若需 2 分钟，则需要 3 小时。
  8. 每天工作 8 小时，每周 5 天，每年工作 50 周，得出 8×5×50=2000 小时。2000 小时能调音大学 1000 架钢琴。
  9. 2.1 * 108 / 1000 = 2.1 × 105 个调音师。

1-31.

How many gas stations are there in the United States?

分解问题成：

  1. 每天大约有多少辆汽车去加油。
  2. 每天一个加油站能给多少辆汽车加油。
  3. 美国人口总数约 300×106 , 一家平均有 2 辆车左右，所以一共有车辆 150×106 ，每辆汽车每 5 天加油一次，一天有 30×106 辆车去加油。
  4. 一个加油站平均每小时最少为 1 辆，最多 100 多辆汽车加油，取平均 20-30 辆每小时，一个加油站工作时间大概 14 小时（7am-9am），每个加油站每天平均大约为 280 辆车加油。
  5. 30×106 / 280 = 1.07 × 105 个加油站。

1-32.

How much does the ice in a hockey rink weigh?

分解成：

  1. 冰的体积。
  2. 冰的密度。

做如下估算： 1.冰场的长度：70m; 2.冰场的宽度：30m; 3.冰的厚度：10cm=0.1; 4.冰的密度与水相当，估算 1000kg/m3 .

V = 70 * 30 * 0.1 = 210 m3 W = 210 *1000 = 210，000kg

1-33.

How many miles of road are there in the United States?

美国近似是一个矩形，高 1000mile 和长 3000mile。美国大部分地区是乡村，道路比较稀疏，平均下来可以把美国想成一个网状的道路结构，每隔 1mile 一条道路，最后如下网格，1000 条 3000mile 和 3000 条 1000mile 的路，总的 6,000,000mile 的路。

1-34.

On average, how many times would you have to flip open the Manhattan phone book at random in order to find a specific name?

假设电话本有 1000 页，也就是 500 个翻面。

简单答案：翻到正确页的概率是 1/500。

复杂点答案：上面没有考虑不断翻页，会翻到相同的页面。翻到错误页面的概率是 499/500，N 次后的错误概率是（499/500）N ,所以 N 次后的正确页面概率是 P=1- （499/500）N 。

那么： N=1 P = 0.002 N=2 P = 0.004 … N=1150 P = 0.89999

达到 90%的概率，所以需要 1150 翻页。

Comments