Python中的欧拉计划第8题

Question

Python中的欧拉计划第8题

5

在这个1000位数中，找出五个连续数字的最大乘积：

import time

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

biggest = 0
i = 1
while i < len(num):
    one = int(num[i]) 
    two = int(num[i+1])  
    thr = int(num[i+2]) 
    fou = int(num[i+3])
    fiv = int(num[i+4])
    product = one*two*thr*fou*fiv
    if product > biggest:
        biggest = product
    i += i+1 
 print(product)

 start = time.time()
 elapsed = (time.time() - start)
 print("This code took: " + str(elapsed) + " seconds")

这段代码给出的答案是7054，远远低于预期，并且在计算过程中只计算了9个乘积。我的问题是：是什么原因导致我的代码偏离了其预期目的，另外，我该如何优化计算"one"、"two"等内容以计算乘积的代码部分？

- user2865027

此答案中的代码（https://dev59.com/ZnfZa4cB1Zd3GeqPWM7d#74454124）对系列进行单次遍历以查找最大乘积。 - cottontail

11个回答

3

你的问题在这里：

i += i+1

您遍历列表的速度过快。您应该这样做：

i += 1

我会这样编写代码：

import operator

# Return the product of all the digits in `series` converted to integers
def numprod(series):
    # Convert the series of digits into a list of integers
    digits = [int(c) for c in series]

    # This applies the multiplication operator to all the digits,
    # starting with 1
    return reduce(operator.__mul__, digits, 1)

# Produce every string of length 5
# This uses a generator but could just as easily use a list comprehension:
# numiter = [num[i : i + SERIES_SIZE] for i in range(len(num) - SERIES_SIZE + 1)]
SERIES_SIZE = 5
numiter = (num[i : i + SERIES_SIZE] for i in range(len(num) - SERIES_SIZE + 1))

# Calculate all the products
allnumprods = [numprod(series) for series in numiter]

# Find the maximum of all the products
print max(allnumprods)

一个更简单的计算乘积的方法是这样的：

def numprod(series):
    product = 1
    for c in series:
        product *= int(c)
    return product

- hughdbrown

1

也可以使用函数式编程来大大简化问题：

def foo():
    max_product = 0
    num = "string of input number"
    for e,n in enumerate(num):
        product = reduce((lambda x,y: x*y),map(int,(num[e:e+13])))
        if product > max_product: 
            max_product = product
    return max_product

试一下吧！

- Benedict K.

0

import string
numbers=list()
fo=open("C:/python34/libs/maths2.txt","r+")
for eachline in fo:
    for char in eachline:
        if char.isdigit():
            A=char
            numbers.append(int(A))

print(numbers)
list1=list()
for i in range(0,len(numbers)-4):
    x=numbers[i]*numbers[i+1]*numbers[i+2]*numbers[i+3]*numbers[i+4]
    list1.append([x])
print(list1)
print(max(list1))

- Ashan Lahiru

1

您能否详细阐述一下您的答案，并对您提供的解决方案进行更多描述？ - abarisone

0

再次强调，这并不是最优化的解决方案，但对于13位数字来说是可行的。

import time
start_time = time.time()
num = "73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450"
i = 0
j = 0
k = 0
while i < len(num) - 13:
    one = int(num[i])
    two = int(num[i + 1])
    three = int(num[i + 2])
    four = int(num[i + 3])
    five = int(num[i + 4])
    six = int(num[i + 5])
    seven = int(num[i + 6])
    eight = int(num[i + 7])
    nine = int(num[i + 8])
    ten = int(num[i + 9])
    eleven = int(num[i + 10])
    twoelve = int(num[i + 11])
    thirteen = int(num[i + 12])
    j = one * two * three * four * five * six * seven * eight * nine * ten * eleven * twoelve * thirteen
    i = i + 1
    if k < j:
        k = j
print(k)
print(time.time() - start_time," seconds")

- jackson jones

0

为了优化代码，我认为最好通过“0”来分割字符串。然后，如果字符串长度大于相邻数字，则找到乘积。

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

no_of_adjacent = 13

def find_greatest_product(num, adj):
    greatest = 1
    for i in range(adj):
        greatest *= int(num[i])
    
    prv_temp = greatest    
    for i in range(adj, len(num)):
        temp = (prv_temp // int(num[i-adj])) * int(num[i])
        prv_temp = temp
        
        if (temp > greatest):
            greatest = temp
    
    return greatest


fractions = number.split("0")
greatest_product = 1

for frac in fractions:
    if len(frac) >= no_of_adjacent:
        temp = find_greatest_product(frac, no_of_adjacent)
        if temp > greatest_product:
            greatest_product = temp

print(greatest_product)

- Nadeera Gayashan

0

问题在这里：

i += i+1

你每次都将i加倍，并加上1。所以如果i是1，你会使它变成3。如果是3，你会使它变成7。如果是7，你会使它变成15，依此类推。但这意味着你的索引缺少很多位置，不是吗！

这会导致你跳过数字中许多位置。你需要使用：

i += 1

这意味着将 1 加到 i。或者你也可以这样做：

i = i+1

这意味着将i设为i+1。

- Joseph

0

这里的解决方案在每次迭代时对系列和窗口（子系列）进行迭代，使它们在大窗口大小下非常缓慢。

下面的解决方案通过使用前一次迭代的乘积来计算每次迭代中的乘积，因此无需重新计算大部分乘积（节省了对每个窗口的循环）。为此，它使用内置的collections模块中的deque来保持一个运行窗口，允许有效地从每个窗口中删除元素。

基本思想是，在每次迭代中，将上一次迭代的乘积除以其计算中使用的第一个数字，并将其乘以当前迭代中的数字-类似于将窗口向右移动一个插槽。

主要困难在于任何数乘以0都是0，因此一旦0进入窗口，剩余数字的乘积就会丢失。为了恢复它，每次迭代中保留两个单独的乘积：prod（即真正的运行乘积）和after_zero（即0后的非零数字的乘积），并且一旦窗口不再包含0，则将after_zero重新分配给prod。

from collections import deque

def compute_window(new_digit, prod, no_zero_prod, window, old_digit=1):

    # compute product for this window
    prod = prod // old_digit * new_digit
    # if the new digit is zero, restart everything (because 0*number=0)
    if new_digit == 0:
        window, prod, no_zero_prod = deque(), 0, 1
    else:
        window.append(new_digit)
        no_zero_prod = no_zero_prod // old_digit * new_digit

    return prod, no_zero_prod, window


def greatest_product(num, window_size):

    # initialize variable
    running_window = deque()
    prod = after_zero = 1

    # calculate the initial product
    for d in num[: window_size]:
        prod, after_zero, running_window = compute_window(int(d), prod, after_zero, running_window)
    # max value to beat
    max_so_far = prod

    for d in num[window_size :]:

        # in each iteration, if the window is full, pop the element that was first entered
        current_window_size = len(running_window)
        prev = running_window.popleft() if current_window_size == window_size else 1

        # if a single element is missing from window, assign the after_zero value to prod
        # (which allows us to use it for this round's product computation)
        if current_window_size == window_size - 1:
            prod = after_zero

        # computations for this iteration
        prod, after_zero, running_window = compute_window(int(d), prod, after_zero, running_window, prev)

        # update max_so_far
        if prod > max_so_far:
            max_so_far = prod

    return max_so_far

如果num是整数而不是字符串，以下方法的工作方式非常相似；只是它从末尾开始，通过反复将整数除以10来获取单个数字；因此，它不是将窗口向右移动，而是在每次迭代中将其向左移动。

def greatest_product(num, window_size):

    n = num
    prod = after_zero = 1
    max_so_far = -1
    running_window = deque()

    while n:

        n, r = divmod(n, 10)
        current_window_size = len(running_window)
        prev = running_window.popleft() if current_window_size == window_size else 1

        if current_window_size == window_size - 1:
            prod = after_zero

        prod, after_zero, running_window = compute_window(r, prod, after_zero, running_window, prev)

        # update max_so_far
        if prod > max_so_far:
            max_so_far = prod

    return max_so_far

输出：

print(greatest_product(num, 13))
# 23514624000

- cottontail

0

# 8 Largest product in a series

from functools import reduce

the_num = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

the_num_lst = []
for n in the_num:
    the_num_lst.append(int(n))

x = 0
y = reduce((lambda a, b: a * b), the_num_lst[x:x + 13])
while x < 1000 - 13:
    x += 1
    z = reduce((lambda a, b: a * b), the_num_lst[x:x + 13])
    if z > y:
        y = z
print(y)

- Ami

0

我的解决方案

s = '''7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'''


t = list(s)
#len(t) = 1000
#t[::-1] = t[999]

r = []
q = 0
while q <= 999:
    w = int(t[q])
    r.append(w)
    q += 1

a = 0
b = 1
c = 2
d = 3
e = 4
f = 5
g = 6
h = 7
i = 8
j = 9
k = 10
l = 11
m = 12

y = []

while m<=999:
    n = r[a]*r[b]*r[c]*r[d]*r[e]*r[f]*r[g]*r[h]*r[i]*r[j]*r[k]*r[l]*r[m]
    y.append(n)
    a += 1
    b += 1
    c += 1
    d+= 1
    e+= 1
    f+= 1
    g+= 1
    h+= 1
    i+= 1
    j+= 1
    l+= 1
    k+= 1
    m+= 1
    if m >= 1000:
        break

print(y)
print(max(y))

- João Cunha

1

这不是计算五个连续数字的乘积，而是对十三个数字进行某种操作。在这里使用13个单独的变量，它们之间有一个固定的关系，这不是最理想的做法，因为可以重构代码，使用一个变量代替这些13个变量。 - Jason Aller

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shashank · Accepted Answer

有几个问题。

你打印的是 product 而不是 biggest。一定要打印正确的变量！
当你进行乘积计算时，你应该只在范围内迭代 [0..len(num) - 4)，而不是整个字符串长度，以避免出现 IndexError。
你错误地递增了 i 变量。你想让它每次循环都增加 1，所以只需执行 i += 1 或 i = i + 1。代码 i += i + 1 等同于 i = i + i + 1。我觉得你不想在 while 循环的每次迭代中使 i 加倍。 :)
在 Python 中，序列从 0 开始索引。这意味着当你迭代一组索引时，第一个元素总是位于 seq[0]，直到元素持续到 seq[n-1]。因此，你应该将 i 变量从 0 开始，而不是 1！
你没有正确测量时间。你需要在所有代码执行之前将 start 时间赋值，以便正确测量 elapsed 时间。

以下是你修复后的代码：

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

import time
start = time.time()

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

biggest = 0
i = 0
while i < len(num) - 4:
    one = int(num[i]) 
    two = int(num[i+1])  
    thr = int(num[i+2]) 
    fou = int(num[i+3])
    fiv = int(num[i+4])
    product = one*two*thr*fou*fiv
    if product > biggest:
        biggest = product
    i = i + 1 
print(biggest)

elapsed = (time.time() - start)
print("This code took: " + str(elapsed) + " seconds")