今日面试题:找到最大数

请构造程序,找到满足如下条件的最大数:

假设最大数表示为,abcdefghihk..... 每一个字母表示一位,其中abc,bcd,cde...以此类推,每三个一组,构成的数字是素数,也就是说abc, bcd, cde,等,都是素数,而且这些素数是互不相同的。

=====================================

序列生成分析

原题

给定一个表达式2^i*2^j,其中i,j为非负整数。请找到一种方法,生成如下序列:

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25
...
...
...

请大家开动脑筋,找到更多的方法。

分析

阅读题目,要得到生成的数字序列是有序的,尽管题目中,并没有明说。这个题目的方法,是比较多的。我们在这里介绍几个。

一个简单的方法

很多同学,应该接触过丑数那个题目吧?这个题目相比之下,还要简单一些。i,j分别是2和5的指数, 则方法的过程如下:

i,j 从0开始,记录较小的值作为序列的当前生成值。则i=j=0时,最小值为1,就是第一个元素;

两个值都是最小元素,所以i和j,都自增1,在最小值1的基础之上乘以2和5得到2,5, 取较小的2作为序列的值,即2,第二个;

此时,只对i进行变化,自增1,在其上一个值的基础之上乘以2,即,2*2=4,再与5比较最小值

依次类推

这个方法的关键是i和j何时递增,以及用数组保存i和j计算的结果。 代码如下:

enter image description here

其他方法

上面方法的变种,还是比较多的。关键就是围绕着怎么每次产生最小的值。有的同学采用最小堆,有的同学采用栈。都是可以得到最终的结果的,但都没有上面的方法精炼。

还有的同学提到用动态规划的方法,这也是一种很好的思路。对于dp[n],判断其是否能够表示为2^i*5^j的形式,可以表示为如下的递归形式

dp[n] = ((n % 2 == 0) && (dp[n/2])) || ((n % 5 == 0) && (dp[n/5]))

并且,显而易见,存在重复利用的递归子过程。但是这个方法,对于n比较大的时候,空间会比较大。因为中间有太多的n不满足条件,我们仍然做了存储,进行了计算。

【分析完毕】

本文来自微信:待字闺中,2013-08-10发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。