project Euler第八题

62 阅读 0 评论 41 点赞

我是靠谱客的博主火星上板凳，最近开发中收集的这篇文章主要介绍project Euler第八题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

算法：

#!usr/bin/env python
#coding=utf-8
import time

start = time.time()

sub = []
res = 1
str = '''73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450'''

str = str.replace('n', '')
for i in xrange(0,996):
    temp = str[i:i+5]
    if not '0' in temp:
        sub.append(str[i:i+5])

for index,item in enumerate(sub):
    temp = 1
    for l in item:
        temp *= int(l)
    res = temp if temp > res else res

print res

end = time.time()
print end - start

结果：40824

这个算法也比较简单，先把这一千个数字分组，每连续五个的分成一组，然后把其中含有0的分组给去掉，再把所有的分组相乘并找出最大值，得出结果。

其实算法还是可以优化的，建立一个长度为5的队列、用一个变量保存结果，每次算出队列里数字的乘积，如果乘积大于原有结果，就替换结果，如果发现0，就直接跳过0附近的数字，队列清空，重新建立，这样子做代码比上边那个麻烦点，就先用上边的算法算出结果，等以后用java实现这个算法。