Q 05　杨辉三角

IQ　70
目标时间：20 分钟

我们在学习规律性时经常能看到杨辉三角。每行左右两端的数都是 1，其他位置上的数等于其左上和右上两数之和，通过这种方式形成的就是杨辉三角。

现在我们假设杨辉三角中的数表示金额（以日元为单位）。例如，“1”是 1 日元，“2”是 2 日元，“10”是 10 日元。针对第行中的各个数，思考每个数表示的金额需要用到的纸币和硬币的数量的最小值，然后求该行中纸币和硬币的数量之和。

例如，当时，数组为 [1, 4, 6, 4, 1]，因为 1 日元 =1（1 枚硬币），4 日元 =4（4 枚硬币），6 日元 =2（1 枚 5 日元的硬币 + 1 枚 1 日元的硬币），所以纸币和硬币的数量加起来一共是 12。同样，当时，纸币和硬币的数量一共是 48（图 1.7）。

另外，本题中可以使用的日元包括 1 日元、5 日元、10 日元、50 日元、100 日元和 500 日元的硬币，以及 1000 日元、2000 日元、5000 日元和 10 000 日元的纸币。

问题

当时，纸币和硬币的数量之和是多少？

思路

本题我们分 3 步来求解。第 1 步，生成杨辉三角；第 2 步，以杨辉三角中第行的数为元素创建数组，针对数组中的各个数值，计算最少需要多少张纸币和多少枚硬币；第 3 步，把该行每个数所需纸币和硬币的最低数量加起来，求和。

如图 1.8 所示，预设好数组后按从右往左的顺序计算，根据上一行数组中的值可以计算出下一行数组中的值。

先从第 1 行开始按顺序进行加法运算，直到取得目标行的值，然后算出该行所需纸币和硬币的最低数量。将纸币和硬币的面额按照从大到小的顺序进行除法运算，得到的商就是所需纸币和硬币的数量。

以 178 日元为例。用 178 除以 100，商是 1，所以 100 日元的硬币有 1 枚。余数是 78，除以 50 后得到的商是 1，所以 50 日元的硬币有 1 枚。接着用余数 28 除以 10，得到的商是 2，即 10 日元的硬币有 2 枚。如此循环，就能求出纸币和硬币的数量总和。

实现这个算法的程序如代码清单 05.01 和代码清单 05.02 所示。

代码清单 05.01（q05.rb）

N = 45

def count(n)
  coin = [10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1]
  result = 0
  coin.each do |c|
    # 按照面额从大到小的顺序计算商和余数
    cnt, n = n.divmod(c)
    result += cnt
  end
  result
end

row = [0] * (N + 1);
row[0] = 1;
N.times do |i|
  # 每行都是从右往左赋值
  (i + 1).downto(1) do|j|
    # 前一行相应位置的值加上其左边的值
    row[j] += row[j - 1]
  end
end

# 计算总数
puts row.map{|i| count(i)}.inject(:+)

代码清单 05.02（q05.js）

N = 45;

function count(n){
  var coin = [10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1];
  var result = 0;
  for (var i = 0; i < coin.length; i++){
    // 按照面额从大到小的顺序计算商和余数
    var cnt = Math.floor(n / coin[i]);
    n = n % coin[i];
    result += cnt;
  }
  return result;
}

row = new Array(N + 1);
row[0] = 1;
for (var i = 1; i < N + 1; i++){
  row[i] = 0;
}
for (var i = 0; i < N; i++){
  // 每行都是从右往左赋值
  for (var j = i + 1; j > 0; j--)
    // 前一行相应位置的值加上其左边的值
    row[j] += row[j - 1];
}

// 计算总数
var total = 0;
for (var i = 0; i < N + 1; i++){
  total += count(row[i]);
}
console.log(total);

答案　3 518 437 540

数学小知识　贪心算法

在从多个选项中选择一个最优项的时候，我们可以使用遍历法比较所有选项，也可以根据问题制定基准，以此来轻松求得最优项。后者叫作贪心算法（greedy algorithm）。

本题中出现的“依据金额求纸币和硬币的数量之和的方法”就是贪心算法的典型示例。在求数量的最小值时，原本需要找出所有的组合方式。但是，在求最少要用多少张纸币和多少枚硬币时，按照面额从大到小的顺序组合使用它们就能求解，这种方法更加直观易懂。

这种方法虽然对于某些问题不能奏效，但是能以简单的程序快速得到答案，因此也经常被人们使用。