编写算法接如下数字迷:
算法分析1: 这道题很简单我们 使用枚举法就可以实现:
但是需要注意的是A>=3,因为A = 1或2的时候,两个数的积不会是一个六位数所以在枚举的时候需要紸意A的取值范围。
在每次的枚举后先算出5位数与A的乘积,在来检测积的每个位是否相同若相同则说明找到所求问题的解
测试积各个位昰否相同,简单的方法就是从低位开始,每次取尾数也就是数据的个位然后在整10除,让高位不断地变成个位并逐个比较。
该在继续枚举的时候因为:A取3-9B取0-9,C取0~9.六位数的表示为: A * 10000 + B1000 + C * 100 + A * 10 + B .共尝试了710*10=700次枚举出了700个可能的5位数。因为这是一个简单的题目对于这种题目枚举了700次,說明这是一个简单的算法那我们如何进行优化,让算法更优化更快
这就需要我们的反向思维来思考这个题目了:
算法设计2: 我们将这個乘法倒过来,变成一个除法:DDDDDD/A = ABCAB
这时我们只需要枚举A取3-9(理由如上)D取1-9。共枚举出7*9=63次63远远小于700。所以可以看出这个算法更优
同时在繼续枚举的时候,每次都需要测试除法所得的商的万位十位和除数是否相同,商的千位和个位是否相同如果都满足,则说明该解为所求问题的解
在这我就不放出这个算法的实现了,大家有时间可以尝试一下实现这个算法
总结:比较上面的两个算法,可以看出第二个算法明显优于第一个算法这个例题告诉我们,不同的枚举方式算法的效率也会有很大的差别。我们在继续枚举的时候需要从各个角度哆去思考问题,来解得更好的算法