序章　解答谜题的技巧

掌握典型的处理方式

假设我们现在要实现一个业务系统。有时客户会提供现成的计算公式，我们只要按照公式去实现就可以了，但有时又需要我们自己去思考如何计算，这时就必须考虑算法的效率问题了。

如果遇到的是未知的问题，想出一个新的算法简直难于登天。好在大多数时候，我们可以直接使用研究人员已经发现的那些高效的算法，毫不费力地进行编程。但是，要想使用那些算法，也必须提前了解各种问题的解题方法才行。

以入学考试为例，我们在备考期间做历年真题的意义就在于此。如果事先知道“有没有类似的问题”“需要花多长时间才能解决”，就能判断出某个程序是否可以实现，并估算出实现需要花费的时间。

但是，针对某个问题，如果完全没见过与之类似的问题，那么可能就很难去解决了。比如在解答谜题时，如果连下面这些基本的算法知识都不懂，解题所花的时间可能就会超乎想象。

● 排序（选择排序、冒泡排序、快速排序、归并排序等）

● 搜索（线性搜索、二分查找、深度优先搜索、广度优先搜索、双向搜索等）

● 最短路径问题[迪杰斯特拉（Dijkstra）算法、贝尔曼 - 福特（Bellman-Ford）算法等]

如果你没有听说过这些名词，最好在阅读本书之前看一下其他的算法入门书。对于学过这些算法的读者，本书的练习能够帮助你进一步学习算法。

例题 1　内存化和动态规划算法

在解答谜题时，很多处理会重复相同的计算，尤其是在解决递归问题时。将计算过一次的结果用在其他地方，可以提高程序的处理速度。

例如，我们来思考下面的问题。虽然单纯用递归处理也能解决，但如果用一些技巧，能大幅度缩短处理时间。

例题

一群人去餐厅用餐，决定分桌坐，在分桌时要避免出现 1 张桌子只有 1 个人的情况。

此时，如果只考虑基于人数的分法，不考虑谁坐在哪一桌，那么以 6 人为例，共有以下 4 种分法。

● 2 人+2 人+2 人

● 2 人+4 人

● 3 人+3 人

● 6 人

如果 1 张桌子最多能坐 10 人，那么当有 100 人需要分桌坐时，有多少种分法？

思路

如果给第 1 张桌子分配的人数已定，那么剩下的人只能被分配到剩余的桌子上。这时，桌子数要减去 1，剩下的人数则是总人数减去分配到第 1 张桌子的人数（图 0.1）。

由于桌子的数量没有上限，所以只要考虑人数的分配方式即可。因此，我们来考虑接下来是分配与之前那桌相等的人数，还是分配多于之前那桌的人数。

换句话说，只要知道剩余人数和之前那桌分配的人数，就可以递归地进行搜索。这样一来，我们就能知道程序的处理可以用“剩余人数”和“之前那桌分配的人数”这两个参数来实现。

我们先根据问题描述来实现程序，请看代码清单 pre01.01 和代码清单 pre01.02。

代码清单 pre01.01（pre1_1.rb）

M, N = 10, 100

def check(remain, pre)
  # 没人可分配则结束
  return 0 if remain < 0
  return 1 if remain == 0

  cnt = 0
  pre.upto(M) do |i| # 分配到桌子的人数
    cnt += check(remain - i, i)
  end
  cnt
end

puts check(N, 2)

代码清单 pre01.02（pre1_1.js）

M = 10;
N = 100;

function check(remain, pre){
  // 没人可分配则结束
  if (remain < 0) return 0;
  if (remain == 0) return 1;
  var cnt = 0;
  for (var i = pre; i <= M; i++){ // 分配到桌子的人数
    cnt += check(remain - i, i);
  }
  return cnt;
}

console.log(check(N, 2));

答案　437 420 种

按照上面的方式虽然可以求出答案，但随着人数的增加，处理时间会呈指数级增长。这种处理方式的问题在于重复进行了相同人数的计算。我们可以试着改一下，把用过一次的值保存起来，在下次需要给同一个参数赋值时，直接返回保存的值就可以了（代码清单 pre01.03 和代码清单 pre01.04）。

代码清单 pre01.03（pre1_2.rb）

M, N = 10, 100

@memo = {}
def check(remain, pre)
  # 如果前面计算过，则返回前面计算后得到的值
  return @memo[[remain, pre]] if @memo[[remain, pre]]

  # 没人可分配则结束
  return 0 if remain < 0
  return 1 if remain == 0

  cnt = 0
  pre.upto(M) do |i|
    cnt += check(remain - i, i)
  end
  # 保存计算结果
  @memo[[remain, pre]] = cnt
end

puts check(N, 2)

代码清单 pre01.04（pre1_2.js）

M = 10;
N = 100;

var memo = {};
function check(remain, pre){
  // 如果前面计算过，则返回前面计算后得到的值
  if (memo[[remain, pre]]) return memo[[remain, pre]];

  // 没人可分配则结束
  if (remain < 0) return 0;
  if (remain == 0) return 1;

  var cnt = 0;
  for (var i = pre; i <= M; i++){
    cnt += check(remain - i, i);
  }
  // 保存计算结果
  return memo[[remain, pre]] = cnt;
}

console.log(check(N, 2));

上述例子都在处理的最后保存了计算结果，这样一来，在后面的处理中，只要在处理的开头让程序返回保存的那个值就可以了。像这样使用存储好的值，可以迅速提升处理速度。在进行递归处理时，保存执行的结果，并在之后的处理中重复使用该结果的方法叫作内存化。

另外，上面这个解题方法是用递归函数来实现的，我们也可以用循环的方式来实现。如果用两个轴来表示就餐人数和每张桌子可分配人数的最大值，并像图 0.2 那样统计分法，那么就可以通过从比较小的数（图 0.2 的左上角）开始，按顺序填入的方式来实现。

也就是说，先把就餐人数是 0 的那一列赋为 1，然后从每张桌子可分配人数的最大值为 2 开始，反复计算所求单元格左边的数和上边的数之和，就能得到上面的表。

代码清单 pre01.05 和代码清单 pre01.06 是基于二重循环编写的示例代码，非常简洁。

代码清单 pre01.05（pre1_3.rb）

M, N = 10, 100

table = Array.new(M + 1){Array.new(N + 1){0}}

0.upto(M){|i| table[i][0] = 1}

1.upto(M) do |i|
  2.upto(N) do |j|
    if (i >= 2) && (j >= i)
      table[i][j] = table[i][j - i]
    end
    table[i][j] += table[i - 1][j] if i > 2
  end
end

puts table[M][N]

代码清单 pre01.06（pre1_3.js）

M = 10;
N = 100;

var table = new Array(M + 1);
for (var i = 0; i <= M; i++){
  table[i] = new Array(N + 1);
  for (var j = 0; j <= N; j++) table[i][j] = 0;
}

for (var i = 0; i <= M; i++)
  table[i][0] = 1;

for (var i = 1; i <= M; i++){
  for (var j = 2; j <= N; j++){
    if ((i >= 2) && (j >= i))
      table[i][j] = table[i][j - i];
    if (i > 2) table[i][j] += table[i - 1][j];
  }
}

console.log(table[M][N]);

这种方法叫作动态规划算法。听起来好像有点难，但如果你把它理解成就是将用过一次的计算结果存储起来，也就不难了。

本书会多次用到内存化这一实现方式。

例题 2　排列组合

我们再来看看排列组合，它们经常作为数学类解题方法被用来破解谜题。高中数学中经常出现“从个物品里取出个”这类问题。这类问题可以分为考虑排列顺序的“排列”和考虑选取方法的“组合”。

排列通常写作，通过简单的乘法就能求解。例如。一般来说，排列可以用下面的数学公式计算出来。

这部分按顺序相乘即可，用简单的处理逻辑就能实现（代码清单 pre02.01 和代码清单 pre02.02）。

代码清单 pre02.01（pre2_1.rb）

def nPr(n, r)
  result = 1
  n - r + 1.upto(n) do |i|
    result *= i
  end
  result
end

代码清单 pre02.02（pre2_1.js）

function nPr(n, r){
  var result = 1;
  for (var i = n - r + 1; i <= n; i++){
    result *= i;
  }
  return result;
}

组合个数的计算则相对复杂一些，我们可以用多种编程方式来实现。组合通常写作，可以用下面的数学公式计算出来。

如果用 Ruby 或 JavaScript 通过递归处理内存化的方式来实现，则程序如代码清单 pre02.03 和代码清单 pre02.04 所示。

代码清单 pre02.03（pre2_2.rb）

@memo = [1]
def factorial(n)
  return @memo[n] if @memo[n]
  @memo[n] = n * factorial(n - 1)
end

def nCr(n, r)
  factorial(n) / (factorial(r) * factorial(n - r))
end

代码清单 pre02.04（pre2_2.js）

var memo = [1];
function factorial(n){
  if (memo[n]) return memo[n];
  return memo[n] = n * factorial(n - 1);
}

function nCr(n, r){
  return factorial(n) / (factorial(r) * factorial(n - r));
}

但是，在使用这种方法的情况下，如果的值变大，分母和分子的值就会变大，在使用某些编程语言时就无法正确地进行计算。例如，在使用 JavaScript 的情况下，计算中途会变成对浮点型数据的计算。

因此，在编程中也经常用到下面这种递归的定义。这种方法可以使程序更加简洁，把程序的大小控制在一定范围内，所以本书中大量采用了这种定义。具体实现如 pre02.05 和代码清单 pre02.06 所示。

代码清单 pre02.05（pre2_3.rb）

@memo = {}
def nCr(n, r)
  return @memo[[n, r]] if @memo[[n, r]]
  return 1 if (r == 0) || (r == n)
  @memo[[n, r]] = nCr(n - 1, r - 1) + nCr(n - 1, r)
end

代码清单 pre02.06（pre2_3.js）

var memo = {};
function nCr(n, r){
  if (memo[[n, r]]) return memo[[n, r]];
  if ((r == 0) || (r == n)) return 1;
  return memo[[n, r]] = nCr(n - 1, r - 1) + nCr(n - 1, r);
}

但这种方法也有缺陷：由于递归层级较深，所以如果的值变大，就会导致栈空间不足。因此，有时也会使用下面这种递推公式来实现。当使用递推公式实现的时候，可以通过循环处理来实现，这样就不会消耗栈空间了。

如果处理会反复用到，我们还可以考虑像代码清单 pre02.07 和代码清单 pre02.08 这样让处理内存化。

代码清单 02.07（pre2_4.rb）

def nCr(n, r)
  result = 1
  1.upto(r) do |i|
    result = result * (n - i + 1) / i
  end
  result
end

代码清单 02.08（pre2_4.js）

function nCr(n, r){
  var result = 1;
  for (var i = 1; i <= r; i++){
    result = result * (n - i + 1) / i;
  }
  return result;
}

读者可以从下一章开始试着用本章列举的技巧来解决实际问题。另外，本书中的源代码仅用作示例，不排除有更高效的实现方式。各位不妨开动脑筋想一想。