EdmondFrank's 时光足迹

この先は暗い夜道だけかもしれない それでも信じて進むんだ。星がその道を少しでも照らしてくれるのを。
或许前路永夜,即便如此我也要前进,因为星光即使微弱也会我为照亮前途。
——《四月は君の嘘》

我的算法天梯之路之-穷举搜索

穷举搜索的例子-Google方程式

 问题描述

有一个由字符组成的等式,WWWDOT-GOOGLE = DOTCOM,每个字符代表一个0-9之间的数字,WWWDOT、GOOGLE和DOTCOM都是合法的数字,不能以零开头。请找出一组字符与数字的对应关系,使得他们可以互相转换,并且替换之后能够满足等式。

问题分析

从排列组合的角度来看,这道题是一道典型的排列组合问题,题目中一共出现了9个字母。

如果不考虑0开头的情况下,这样的组合应该有10x9x8x7x6x5x4x3x2=3628800种组合。

在这样的情况之下,计算机的穷举处理应该是毫无压力的。

问题求解

首先为了能够表示这样一种可变的字符元素列表,我们需要自定义一种数据结构。首先我们知道这个自定义结构中应该包含有三个属性,分别是 字符本身,字符代表的数字以及是否为数字的最高位,因为最高位是不能为0的,所以在这里我们要区别对待。

1
2
3
4
5
6
typedef struct tagCharItem
{
  char c;
  int value;
  bool leading;
}CHAR_ITEM;

接着我们初始化这个列表。=

1
2
3
4
5
CHAR_ITEM charItem[]={
{'W',-1,true},{'D',-1,true},{'O',-1,true},
{'T',-1,false},{'G',-1,true},{'L',-1,false},
{'E',-1,false},{'C',-1,false},{'M',-1,false}
};

因为这是一个组合问题,那么两个字母就不能被指定为相同的数字,这样我们需要定义额外的占用标识。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef struct tagCharValue
{
  bool isused;
  int value;
}CHAR_VALUE;

//穷举算法实现如下
void SearchingResult(CHAR_ITEM ci[],CHAR_VALUE cv[],
int index,CharListReadyFuncPtr callback)
{
if(index == max_char_count)
{
  callback(ci);
  return;
}
for(int i = 0;i<max_number_count;++i)
{
  if(IsValueValid(ci[index],cv[i]))
  {
      cv[i].isused= true;
      ci[index].value = cv[i].value;
      SearchingResult(ci,cv,index+1,callback);
      cv[i].isused = false;
  }
}
}

根据题目要求,W,G,D三者都不能为0,为了加快穷举速度可以对他们为0的情况进行剪枝。
IsValueValid是评估函数,在剪枝操作之后,callback的被调用次数可以减少约30%。

1
2
3
4
5
6
7
8
9
10
11
12
13
//callback代码实现
void OnCharListReady(CHAR_ITEM ci[])
{
  char * minuend = "WWWDOT";
  char * subtrahend = "GOOGLE";
  char * diff = "DOTCOM";
  int m = MakeIntegerValue(ci,minuend);
  int s = MakeIntegerValue(ci,subtrahend);
  int d = MakeIntegerValue(ci,diff);
  if((m-s)==d){
      std::cout << m << "-" <<s<< "=" << d << std::endl;
  }
}

问题答案
777589 - 188103 = 589486
777589 - 188106 = 589483