【USACO编程竞赛题】密码算术(Cryptarithms)

下面是密码算术最著名的一道密码加法题 – SEND MORE MONEY 的每个字母都代表一个数字,相同字母代表相同数字,不同字母代表不同数字,所有数字需要满足加法运算的结果。

cryptarithm-01

下面的图例演示了逻辑推理过程,大家看看是否可以理解为什么第一个破译的数字是1,第二个是0,…..,以此类推直到最后一个数字。

cryptarithm-02

  • 第一步:字母 M 替换为 1

cryptarithm-03

  • 第二步:字母 O 替换为 0

cryptarithm-04

  • 第三步:字母 S 替换为 9

cryptarithm-05

  • 第四步:字母 R 替换为 8

cryptarithm-06

  • 第五步:字母 E 替换为 5, 字母 D 替换为 7

cryptarithm-07

  • 第六步:字母 N 替换为 6, 字母 Y 替换为 2

【逻辑推理说明】

  • 第一步:因为两个个位数相加,最大的进位数为 1,所以字母 M 替换为 1。
  • 第二步:个位数加 1 最多等于 10,所以字母 O 替换为 0。
  • 第三步:个位数里面加1大于或等于10的数字就是 9,所以字母 S 替换为 9。
  • 第四步:这是最关键的一步,因为 E + 0 = N,而且 E 不等于 N,可以推断 E + 1 = N,因为 N+ R 的进位最多为 1,那么 N + R = E + 10,也就是 E + 1 + R = E + 10,或者个位数 D+ E 进位 1 导致 E + 1 + R + 1 = E+ 10,因为 9 已经被 S 占用,所以可以得出 R = 8。
  • 第五步:现在剩下的数字是:2、3、4、5、6、7,考虑 D +E = Y + 10,那么 D 和 E 只能是 5、6、7中的两个,5 + 6 = 11 不符合要求因为数字 1 已经被 M 占用,那么 D + E 只能是 5 + 7 或者 6 + 7。又因为 N = E + 1,所以 6 + 7 不符合要求,这样 N就会小于E,所以 D + E 必须是 5 + 7。这样可以推断 E 是 5,D是7。
  • 第六步:N = E + 1 所以 N 是 6,最后剩下一个数字,那么 Y 就是 2。