穷举搜索的例子（Google方程式（Java题解））

青春须早为，岂能长少年。这篇文章主要讲述穷举搜索的例子：Google方程式（Java题解）相关的知识，希望能为你提供帮助。
题目
有一个由字符组成的等式：WWWDOT - GOOGLE = DOTCOM，每个字符代表一个0～9之间的数字，WWWDOT、GOOGLE和DOTCOM都是合法的数字，不能以0开头。请找出一组字符和数字的对应关系，使它们互相替换，并且替换后的数字能够满足等式。
思路
据说这是Google公司的面试题，我没有考证过，不过这种字符方程（或字符等式）问题有很多变种，比如2005年的Google中国编程挑战赛第二轮淘汰赛有一道名为“SecretSum”的500分的竞赛题，与本题如出一辙，只不过字母是3个，而且用的是加法计算。这个问题其实并不难，你可以将其列成竖式减法的形态，然后人工推算出来，不过接下来我们要使用穷举法来求解这个问题。
从穷举法的角度看，这是一个典型的排列组合问题，题目中一种出现了9个字母，每个字母都可能是0～9之间的数字，穷举的方法就是对每个字母用0～9的数字尝试10次，如果某一次得到的字母和数字的对应关系能够满足减法等式，则输出这一组对应关系。根据题目意思，每个字母代表一个数字，也就是说，如果W代表1，则其他8个字母就不可能是1。很显然，这是个组合问题，如果不考虑0开头数字的情况，这样的组合应该有10×9×8×7×6×5×4×3×2=3628800种组合，在这样的数量级上使用穷举法，计算机处理起来应该没有压力。
现在考虑给出一种解决这种字符方程问题的通用解法。从数据结构定义上，首先要避免使用固定9个字符的方法，这就需要定义一个可变化的字符元素列表，每个字符元素包含3个属性，分别是字母本身、字母代表的数字以及是否是数字的最高位。
题解

public class Main { public static void main(String[] args) { f(); } public static void f() { int a1 = 10; int a2 = 100; int a3 = 1000; int a4 = 10000; int a5 = 100000; for(int W=0; W< 10; W++) { for(int D=0; D< 10; D++) { for(int O=0; O< 10; O++) { for(int T=0; T< 10; T++) { for(int G=0; G< 10; G++) { for(int L=0; L< 10; L++) { for(int E=0; E< 10; E++) { for(int C=0; C< 10; C++) { for(int M=0; M< 10; M++) { int WWWDOT = W*a5+W*a4+W*a3+D*a2+O*a1+T; int GOOGLE = G*a5+O*a4+O*a3+G*a2+L*a1+E; int DOTCOM = D*a5+O*a4+T*a3+C*a2+O*a1+M; if(W!=D & & W!=O & & W!=T & & W!=G & & W!=L & & W!=E & & W!=C & & W!=M) { if(D!=O & & D!=T & & D!=G & & D!=L & & D!=E & & D!=C & & D!=M) { if(O!=T & & O!=G & & O!=L & & O!=E & & O!=C & & O!=M) { if(T!=G & & T!=L & & T!=E & & T!=C & & T!=M) { if(G!=L & & G!=E & & G!=C & & G!=M) { if(L!=E & & L!=C & & L!=M) { if(E!=C & & E!=M) { if(C!=M) { if (WWWDOT - GOOGLE == DOTCOM) { System.out.println(WWWDOT+"-"+GOOGLE+"="+DOTCOM); } } } } } } } } } } } } } } } } } } } }

结果