ProjectEuler Problem 8: Largest product in a series

ProjectEuler Problem 8: Largest product in a series

Mar 18, 2014
Coding
ProjectEuler

Problem 8: Largest product in a series #

https://projecteuler.net/problem=8

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

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

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

分析 #

找出1000个数字中,连续的13个数字,乘积最大,求该乘积

方法1 遍历 #

比如连续的13个数为:a1,a2,a3 … a11,a12,a13 product(a1,a13) = a1 * a2 * a3 … *a11 * a12 * a13

向后寻找时,我们不用每次都将13个数字相乘,比如查找一个连续的13个数 product(a2,a14) = a2 * a3 * a4 … *a12 * a13 * a14

一旦发现数字为0,则可以快速的向后跳跃 13个数字,因为 0 乘以任何数的乘积都是0

C++ #

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

const char * digits = 

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

int main()
{
    int     maxStartIdx = 0;
    int64_t maxProduct  = 0;

    for(int i=0; i < 1000-13; i++){
        int64_t product = 1;

        for(int j=i+12; j>=i; j --){ // 从后往前累乘,这样一旦发现 0,可以快速的跳到 0 的下一位。略过了 0 之前可能出现的0,跳的最远。
            if( digits[j] == '0') {
                i = j; // 快速往后移动。 本来应该是:i = j + 1, 但 for循环中已有 i++
                break;
            }
            product *= (int64_t)(digits[j]-'0');
        }

        if(product > maxProduct){
            maxProduct = product;
            maxStartIdx = i;
        }
    }

    printf("max product is: %lld\n", maxProduct);
    for(int i = maxStartIdx; i<maxStartIdx+13; i++){
        printf("%c ", digits[i]);
    }

    return 0;
}

Golang #

package main

import "fmt"

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

func main(){
	maxStartIdx, maxProduct := 0, int64(0)

	for i:=0; i < 1000-13; i++ {
		product := int64(1)
		for j:=i+12; j>=i; j-- { // 从后往前累乘,这样一旦发现 0,可以快速的跳到 0 的下一位。略过了 0 之前可能出现的0,跳的最远。
			if digits[j] == '0' {
				i = j // 本来应该是:i = j + 1, 但 for循环中已有 i++
				break
			}
			product *= int64(digits[j]-'0')
		}

		if(product > maxProduct){
			maxProduct = product
			maxStartIdx = i
		}
	}

	fmt.Printf("max product is: %v\n", maxProduct);
	for i := maxStartIdx; i<maxStartIdx+13; i++ {
		fmt.Printf("%c ", digits[i]);
	}
}

Python #

#coding=utf-8
#author: JarvisChu
#date:2014-3-18

from urllib.request import urlopen

def download_string():
    '''从网页上将1000个数字下载下来保存到一个字符串中'''
    url = 'http://projecteuler.net/problem=8'
    content = urlopen(url).read().decode('utf8')

    #从源码中,找出1000个数字字符
    start = content.find('73167176531330624919225119674426574742355349194934<br />')
    end = content.find('450<br />') + 8
    nums = content[start:end+1] #包含了每行结尾的HTML换行符 <br />,还有\n字符
    #print(nums)
    nums = nums.replace('<br />','') #去掉结尾的 HTML换行符 <br />
    nums = nums.replace('\n','') #去掉结尾的 \n
    #print(nums)
    return nums

def find_max(s):
    '''s是1000个数字的字符串,函数返回最大乘积'''

    maxStartIdx, maxProduct = 0, 0

    for i=0; i < 1000-13; i = i+1 :
        product = 1
        for j:=i+12; j>=i; j = j-1 : # 从后往前累乘,这样一旦发现 0,可以快速的跳到 0 的下一位。略过了 0 之前可能出现的0,跳的最远。
            if digits[j] == '0' :
                i = j # 本来应该是:i = j + 1, 但 for循环中 i++
                break
            product *= int(digits[j])
		}

		if product > maxProduct :
            maxProduct = product
			maxStartIdx = i
		}
	}

	print("max product is: ", maxProduct)
	for i = maxStartIdx; i<maxStartIdx+13; i = i+1 {
		print(digits[i], ' ')
	}
    return maxProduct

s = download_string()
print(find_max(s))

使用列表综合和reduce()函数,可以得到更简洁的方法


def download_string():
    '''从网页上将1000个数字下载下来保存到一个字符串中'''
    
    from urllib.request import urlopen
    url = 'http://projecteuler.net/problem=8'
    content = urlopen(url).read().decode('utf8')

    #从源码中,找出1000个数字字符
    start = content.find('73167176531330624919225119674426574742355349194934<br />')
    end = content.find('450<br />') + 8
    nums = content[start:end+1] #包含了每行结尾的HTML换行符 <br />,还有\n字符
    #print(nums)
    nums = nums.replace('<br />','') #去掉结尾的 HTML换行符 <br />
    nums = nums.replace('\n','') #去掉结尾的 \n
    #print(nums)
    return nums


s = download_string()
nums = [int(c) for c in s]
#print(nums)

# using lambda
from functools import reduce
print( max([reduce(lambda x,y: x*y, nums[i:i+13]) for i in range (len(nums) - 13 ) ]) )

# using mul
from operator import mul
print( max([reduce(mul, nums[i:i+13]) for i in range (len(nums) - 13 ) ]) )

先将字符串转换为int数组,再使用 reduce 统计连续13个数字的和,再使用 max 从所有连续的13个数字的和中找到最大的值

reduce() 函数原型为: reduce(function, sequence, initial=_initial_missing), 对序列sequence,每两个作为参数,执行function函数。如reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) 就等同于((((1+2)+3)+4)+5) 。

lambda表达式就是创建了一个简单的函数,如lambda x, y: x+y,就相当于 def foo(x,y): return x+y 。

本题中只使用了简单的累乘,所以,可以使用operator模块的mul 替换lambda表达式。

答案 #

23514624000

知识点 #

  • Python urllib模块使用
  • Python reduce()函数
  • Python Lambda