算法系列（一） Google方程式

算法系列（一） Google方程式2014-04-30 csdn博客吹泡泡的小猫有一个字符组成的等式：WWWDOT - GOOGLE = DOTCOM，每个字符代表一个0－9之间的数字，WWWDOT 、GOOGLE和DOTCOM都是合法的数字，不能以0开头。请找出一组字符和数字的对应关系，使它们互相替换，并且替换后的数字能够满足等式。这个字符等式是Google公司能力倾向测试实验室的一道题目，这种题目主要考察人的逻辑推导能力和短期记忆能力，通常棋下的好的人解决这类问题会更得心应手一些（飞行棋例外）。此类型的题目有很多变种，各种编程比赛中常常能见到它们的身影。比如2005 年的GOOGLE中国编程挑战赛第二轮淘汰赛有一道名为“SecretSum”的500分的竞赛题，与本题如出一辙，只不过字母都是三个，而且用的是加法计算。现在言归正传，先看看如何分析这个问题。

以人的思维方式分析问题

将横式改成竖式可能更直观一些：

根据以上竖式减法，从左向右依次可以得到6个算式，分别是：

W – G = D （算式 1）

W – O = O （算式 2）

W – O = T （算式 3）

D – G = C （算式 4）

O – L = O （算式 5）

T – E = M （算式 6）

根据以上6个算式可以分析出两个关键信息：一个是W要足够大，因为考虑到它可能被借位的情况还要等于G和D的和；另一个则是本问题的突破口，就是算式2和算式3两次出现的W – O计算。现在分析算式2和算式3，根据是否需要借位，算式2和算式3一共有四种借位组合结果，下面分别对这四种借位组合结果进行分析。

1. W – O = T不需要借位，W – O = O也不需要借位

由于W – O = T和W – O = O都不需要借位，则可由算式2变形得到算式1.1：

W = 2O （算式1.1）

将算式1.1带入算式 3，又可以得到算式1.2:

O = T （算式 1.2）

根据算式1.2，O和T代表的数字是同一个数字，这与题目要求不符，因此，这种借位组合不能得到正确的结果。

2. W – O = T需要借位，W – O = O不需要借位

根据借位情况，对算式2和算式3进行借位修正，得到两个修正算式：

W – 1 – O = O （算式2.1）

W + 10 – O = T （算式2.2）

由算式2.1变形得到算式2.3：

W = 2O + 1 （算式2.3）

将算式2.3带入算式2.2可以得到算式2.4：

T = O + 11 （算式2.4）

对算式2.3分析，由于W是个位数，最大值是9，所以O的取值只能是1 －4，但是无论如何，由算式2.4计算出的T都超过9，这与题目要求不符，因此，这种情况也是无解的情况。