由一道小学题想到的

31 March 2013

1.题目重现

这是新浪sae发的一条微博

题目原图

说的是一个小学生的课后作业,具体的内容是

学习*学=好好好;
学,习,好,各代表什么数字。

2.万能解法

我想如果我是小学生的话,真的好困难,这个怎么会做嘛,老师没有教到这方面的知识呀。估计家长也很难做出来吧。

现在站在程序员的角度再去想这个问题,当然一上来最不用思考的办法就是暴力破解,就是试遍所有情况,把好,学,习 这三个字分别从0-9遍历一次,这是肯定能找出答案的方法,因为我们知道,如果有解,解必然在这10^3次遍历中,否则,无 解。也就是说,我们能确定的是,在这1000次遍历之外的数的组合是肯定无解的,我们只要全部试试,能不能解就当然知道了。

上面这种暴力解法很普遍,几乎能解决大部分的问题,但是里面却藏有一个小问题,那就是这样做所消耗的时间也是很巨大, 可能1000次对于计算机来说不算什么,但是为什么要让计算机去做无用的功呢?

3.思考

转换成代数吧,先设学为a,习为b,好为c。

我们分析一下,好好好是一个三位数,因此,学不可能是1和2,学的范围就是[3,9].

再来确定一下一个衡等式,

学习*学=好好好

转换成代数语言就是

(a*10+b)*a=a*a*10+a*b=c*100+c*10+c=111c

a*b肯定是小于100的,这个很容易知道,于是

a*b=a*a*10-111c<100
a*a*10+100<111c
a*a*10+a*a<111c
a*a*11<111c

我们先来遍历a的话,对于这个式子来说,a是确定的已知数,b和c是为知数,我们来看看b可以用式子来表示成什么

b=111c/a-a*10

题目中有一个隐含的条件我们可以用上,那就是a,b,c都是整数哦。在上面的式子中,要保证b是整数,111c/a就必须是一个整数, ,这样我们就可以分析得出111能被a整除,c能被a整除。



tags:    it   
回到首页