今日面试题:周长最长

n根长度不一的棍子,判断是否有三根棍子可以构成三角形,并且找到周长最长的三角形。

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

找到最大数分析

原题

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

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

分析

首先,这个最大的数存在么?一定存在的。因为,abc、bcd、cde等都是不同的素数。并不会出现环。总会结束。

其次,面试题做得多了,要能够令灵活运用。并不是一定要有多么巧妙的方法,当然,一个大家都会追求一个巧妙的思路。但不好觉得暴力的方法,在任何条件下,都是拒之千里的。这个题目首先想到暴力解决,是没有问题的。三位的素数是有限的。这是可以暴力的基础。

那么,出了暴力之外,还可以如何改进呢?我们首先对这个题目进行建模,构造一个有向图G。G中的节点就是三位素数,比如abc,bcd,def都是三位素数,则他们都是有向图G中的节点。其中,abc和bcd之间有abc指向bcd的边。abc、bcd则与def之间没有边。如此,构造完整G。大家可以在纸上画一画。所有的三位素数如下:

101, 103, 107, 109, 113,

127, 131, 137, 139, 149, 151, 157, 163, 167, 173,

179, 181, 191, 193, 197, 199, 211, 223, 227, 229,

233, 239, 241, 251, 257, 263, 269, 271, 277, 281,

283, 293, 307, 311, 313, 317, 331, 337, 347, 349,

353, 359, 367, 373, 379, 383, 389, 397, 401, 409,

419, 421, 431, 433, 439, 443, 449, 457, 461, 463,

467, 479, 487, 491, 499, 503, 509, 521, 523, 541,

547, 557, 563, 569, 571, 577, 587, 593, 599, 601,

607, 613, 617, 619, 631, 641, 643, 647, 653, 659,

661, 673, 677, 683, 691, 701, 709, 719, 727, 733,

739, 743, 751, 757, 761, 769, 773, 787, 797, 809,

811, 821, 823, 827, 829, 839, 853, 857, 859, 863,

877, 881, 883, 887, 907, 911, 919, 929, 937, 941,

947, 953, 967, 971, 977, 983, 991, 997

有向图G构造完毕之后,该如何找到最大的数呢?其实就是找到G中,最长的路径。可以采用动态规划来解决。dp[i]表示,到节点i为止的最长路径。状态转移方程可以表示为:

dp[i] = max(dp[j] + 1), 其中, 节点j是有边指向i的所有节点。

在实现过程中,要注意保存路径,这样才能得到最大数。例如,得到最大的j为j1,则 保存prev[i] = j1。

通过计算,最终得到最大数为:

9419919379773971911373313179

【分析完毕】

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