例题:
编写算法接如下数字迷:
算法分析1:
这道题很简单,我们 使用枚举法就可以实现:
但是需要注意的是A>=3,因为A = 1或2的时候,两个数的积不会是一个六位数,所以在枚举的时候需要注意A的取值范围。
在每次的枚举后,先算出5位数与A的乘积,在来检测积的每个位是否相同,若相同则说明找到所求问题的解
测试积各个位是否相同,简单的方法就是,从低位开始,每次取尾数也就是数据的个位,然后在整10除,让高位不断地变成个位,并逐个比较。
下面是该方法的实现:
/**
* 数字迷问题
*
*/
public class guessNum {
public static void main(String[] args) {
int flag;// 5 位的乘数
int sum;// 积
int q;
int type1, type2, a;// 中间量
for (int i = 3; i <= 9; i++) { // A需要大于3,积才能为6位数
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 9; k++) {
flag = i * 10000 + j*1000 + k * 100 + i * 10 + j; // 5 位的乘数
sum = flag * i;//积
a = sum;//将sum赋值给a
type1 = a % 10;
for (q = 0; q < 5; q++) {//五次循环确定积的六位数是否相等
type2 = type1;
a /= 10; //去除个位的数
type2 = a % 10;//取个位的数
if (type1 != type2) {
break;
}
}
if (q == 5) {//如果都相同则找到所需要的组合
System.out.println(flag + " * " + i + " = " + sum);
}
}
}
}
}
}
算法分析:
该在继续枚举的时候因为:A取3-9,B取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。所以可以看出这个算法更优。
同时在继续枚举的时候,每次都需要测试除法所得的商的万位,十位和除数是否相同,商的千位和个位是否相同,如果都满足,则说明该解为所求问题的解。
在这我就不放出这个算法的实现了,大家有时间可以尝试一下实现这个算法。
总结:比较上面的两个算法,可以看出第二个算法明显优于第一个算法,这个例题告诉我们,不同的枚举方式,算法的效率也会有很大的差别。我们在继续枚举的时候,需要从各个角度多去思考问题,来解得更好的算法。