《编程之美》2.20程序理解和时间分析

时间:2021-09-06 12:12:48

改用java代码写的如下:

public class BeautyOfCode20 {
public static void main(String[] args){

int[] rg = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31 };
for ( i = 1L; i < Long.MAX_VALUE; i++) {
int hit = 0;
int hit1 = -1;
int hit2 = -1;
for (int j = 0; j < rg.length && hit <= 2; j++) {
if ((i % rg[j]) != 0) {
hit++;
if (hit == 1)
hit1 = j;
else if (hit == 2)
hit2 = j;
else
break;
}
}
if (hit == 2 && (hit1 + 1) == hit2)
System.out.println(i);
}
}

}

从代码中可以看出要求的这个数满足连个条件:

1.只能被2-31中的两个数整除

2.而且这两个数是相邻的

 

我们可以试着推敲这两个相邻的数,相对不容易被整除的这两个数应该具有这样的特征,一个数的高次幂或者是个大一点的素数。由于只能被2-31中的两个数整除,所以可以排除很多的数,比如6可以由前面的23相乘得到,类似这样的数可以排除很多,首先可以确定一些较大的素数1719232931,高次幂的数有16,2527,而这些数中相邻的只有1617;所以要求的这个数是剩下的28个数的最小公倍数:8(23次方)*27(33次方)*25(52次方)*7*11*13*19*23*29*31 计算后的值为2123581660200(用上面的代码已验证过)

 

第三问估算时间不会,看的别人的分析:

我们先确定一个原子操作(或者说原子过程更合适),这里我们取内层for循环里的整个if语句块,该段程序主要包括一个取模操作和一个判断,如果进入if语句的话,还包括1次加法操作,1~2次判断和一次赋值操作。

    我们知道加法、判断等操作基本都在几个时钟周期内就可以完成,而除法操作却需要数十个时钟周期,而取模操作也是通过除法操作得到的(还记得汇编语言里,执行除法操作之后,一个寄存器里存结果,另一个寄存器里存余数),另外,对64位整数的除法明显要慢于32位整数,综合这些因素,我们可以假设该原子操作需要100个时钟周期。因此2GHzCPU1秒内能跑2*10^9 / 100 = 2*10^7 2000万次原子操作,做过ACM的同学就会有一个直观概念,这和我们通常做时限为1S的题时估算的计算次数差不多。

    接下来估算原子操作执行的次数:外层循环跑了2123581660200次,内层循环取决于 的情况,当i为奇数的时候,内层最多跑5次即可结束,因为246都不能整除奇数;当i为偶数的时候,情况要复杂一些,但是也可以一个一个的详细分析。这里我们粗略估计,就算内层循环平均可以跑10次,外层循环少跑一些,去掉零头,总的原子操作执行了2*10^13次。

所以需要 2*10^13 / (2*10^7) = 10^6秒约为277个小时。

参考

http://hi.baidu.com/silverxinger/item/4fd323b7c4803a98194697a5