题目8：找出这个1000位数字中连续13个数字乘积的最大值

阿bang

1. import time
   
2. 
   
3. 
   
4. series = '''
   
5. 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'''
   
6. 
   
7. 
   
8. def product(str1):
   
9.     result = 1
   
10.     if '0' in str1:
    
11.         return 0
    
12.     else:
    
13.         for i in str1:
    
14.             result *= int(i)
    
15.         return result
    
16. 
    
17. 
    
18. start = time.time()
    
19. maxresult = product(series[1:14])
    
20. for i in range(2, len(series) - 13):
    
21.     str1 = series[i:i+13]
    
22.     maxresult = max(maxresult, product(str1))
    
23. print maxresult
    
24. print time.time() - start

复制代码

还有可优化的点是，如果新加入的数比之前剔除的数小，那么新的这组数的乘积就不用算了。

<url>http://canadianpharmaciesrxbest.com/|pharmacy online</url>, <url>http://canadianonlinepharmacygen.com/|canadian drugstore online</url>, <url>http://canadianpharmaciesdiscount.com/|discount pharmacy</url>, <url>http://canadianpharmacieslink.com/|ed meds online</url>

refracted_ray

题目中的1000位数字怎么复制进代码啊，不让复制啊

refracted_ray

1. a=7316717653 # 10位数
   
2. a_s=str(a) # 转换为字符串
   
3. a_list=list(a_s) # 转换为列表
   
4. b=[] # a_list的每个项转换为数值的列表
   
5. for i in a_list:
   
6.         j=int(i)
   
7.         b.append(j)
   
8. 
   
9. c=[] # 存储m以及对应的b[k]
   
10. for k in range(2,10):
    
11.         m=b[k]*b[k-1]*b[k-2]
    
12.         c.append((m,k))
    
13. c.sort(reverse=True) # 以m的大小为准，从大到小排列
    
14. 
    
15. """
    
16. c[0][0]=m，c[0][1]=k
    
17. """
    
18. print ('%d=%d*%d*%d'%(c[0][0],b[c[0][1]],b[c[0][1]-1],b[c[0][1]-2]))
    
19. 
    
20. 1000位数和10位数无本质区别，这里为了方便，只取本题1000位数的前10位，求连续3个数乘积的最大值
    
21. 
    
22. 结果是210=7*6*5

复制代码

塔利班

1. b="7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
   
2. 
   
3. index=0
   
4. m=0
   
5. for i in range(989):
   
6.     c=b[i:i+13]
   
7.     if '0' in c:
   
8.         continue
   
9.     t=eval('*'.join(list(c)))
   
10.     if t>m:
    
11.         m=t
    
12.         index=i
    
13. 
    
14. print('目标字符串',m,'：最大结果',b[index:index+13])

复制代码

山有扶苏啊

1. def find_max(x):
   
2.     i = 0
   
3.     result = []
   
4.     while i <= len(str(x)) - 13:
   
5.         s = 1
   
6.         for t in str(x)[i : i+13]:
   
7.             s = s * int(t)
   
8.         i += 1
   
9.         result.append(s)  
   
10.     print(max(result))
    
11. 
    
12. find_max(7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450)
    
13.             

复制代码

答案是23514624000
做之前试了一下采集的数据数量，看来数学不大好

cupbbboom

1. # 实现求一个1000位数字组成的数中
   
2. # 连续13位数乘积最大的序列及其乘积
   
3. 
   
4. str_a = '''
   
5. 73167176531330624919225119674426574742355349194934
   
6. 96983520312774506326239578318016984801869478851843
   
7. 85861560789112949495459501737958331952853208805511
   
8. 12540698747158523863050715693290963295227443043557
   
9. 66896648950445244523161731856403098711121722383113
   
10. 62229893423380308135336276614282806444486645238749
    
11. 30358907296290491560440772390713810515859307960866
    
12. 70172427121883998797908792274921901699720888093776
    
13. 65727333001053367881220235421809751254540594752243
    
14. 52584907711670556013604839586446706324415722155397
    
15. 53697817977846174064955149290862569321978468622482
    
16. 83972241375657056057490261407972968652414535100474
    
17. 82166370484403199890008895243450658541227588666881
    
18. 16427171479924442928230863465674813919123162824586
    
19. 17866458359124566529476545682848912883142607690042
    
20. 24219022671055626321111109370544217506941658960408
    
21. 07198403850962455444362981230987879927244284909188
    
22. 84580156166097919133875499200524063689912560717606
    
23. 05886116467109405077541002256983155200055935729725
    
24. 71636269561882670428252483600823257530420752963450
    
25. '''
    
26. import re
    
27. str_a = re.sub('\n','',str_a)
    
28. result =[]
    
29. x = 0
    
30. while x < len(str_a) - 11:
    
31.         l = str_a[x:x+13]
    
32.         y = 0
    
33.        
    
34.         if '0' not in l:  # 跳过包含0的
    
35.                 z = 1
    
36.                 while y < len(l):
    
37.                         z *= int(l[y])
    
38.                         y += 1
    
39.                 result.append(z)
    
40.         x += 1
    
41. print(max(result))

复制代码

23514624000

愿你

1. #include <stdio.h>
   
2. typedef unsigned long long  ull;
   
3. main()
   
4. {
   
5.         char a[1000]={"7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"};
   
6.         ull max,i,j,t;
   
7.         j=0,max=0;
   
8.         for(i=0;i<987;i++)
   
9.         {
   
10.                 t=1;
    
11.                 j=0;
    
12.                 while(j<13)
    
13.                 {
    
14.                         t=t*(a[i+j]-48);
    
15.                         j++;
    
16.                 }
    
17.                 if(t>max)
    
18.                 {
    
19.                         max=t;
    
20.                 }
    
21.         }
    
22.         printf("%ull", max);
    
23. }
    

复制代码

不知道为什么我答案算错了

王小召

运行结果：('5576689664895', 23514624000)

                               
登录/注册后可看大图

1. 
   
2. def get_max(tar):
   
3.     slice_str = []
   
4.     str_val = []
   
5.     str_range = len(tar)
   
6. 
   
7.     for i in range(str_range):
   
8.         if i <= str_range - 13 and "0" not in str_t[i:(i+13)]:
   
9.             result = 0
   
10.             for x in range(2, 10):
    
11.                 result += (str_t[i:(i+13)].count(str(x)))*x
    
12.             slice_str.append(str_t[i:(i + 13)])
    
13.             str_val.append(result)
    
14.     target = slice_str[str_val.index(max(str_val))]
    
15.     result = 1
    
16.     for each in target:
    
17.         result *= int(each)
    
18. 
    
19.     return target, result
    
20. 
    
21. str_t = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843" \
    
22.         "8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557" \
    
23.         "6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749" \
    
24.         "3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776" \
    
25.         "6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397" \
    
26.         "5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474" \
    
27.         "8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586" \
    
28.         "1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408" \
    
29.         "0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606" \
    
30.         "0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
    
31. 
    
32. print(get_max(str_t))

复制代码

永恒的蓝色梦想

Python

1. from math import prod
   
2. num = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
   
3. print(max(prod(map(int, num[i - 13 : i])) for i in range(13, len(num))))

复制代码

1666194196

#include <stdio.h>
void main(){
        //73167176531330624919225119674426574742355349194934
        //96983520312774506326239578318016984801869478851843
        //85861560789112949495459501737958331952853208805511
        //12540698747158523863050715693290963295227443043557
        //66896648950445244523161731856403098711121722383113
        //62229893423380308135336276614282806444486645238749
        //30358907296290491560440772390713810515859307960866
        //70172427121883998797908792274921901699720888093776
        //65727333001053367881220235421809751254540594752243
        //52584907711670556013604839586446706324415722155397
        //53697817977846174064955149290862569321978468622482
        //83972241375657056057490261407972968652414535100474
        //82166370484403199890008895243450658541227588666881
        //16427171479924442928230863465674813919123162824586
        //17866458359124566529476545682848912883142607690042
        //24219022671055626321111109370544217506941658960408
        //07198403850962455444362981230987879927244284909188
        //84580156166097919133875499200524063689912560717606
        //05886116467109405077541002256983155200055935729725
        //71636269561882670428252483600823257530420752963450
        //在这个 1000位正整数中，连续4个数字的最大乘积是 9 × 9 × 8 × 9 = 5832。
        //找出这个 1000位正整数中乘积最大的连续13个数字。它们的乘积是多少？
       
        char a[]={"7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"};
        int i;
        long long max=0;
        for(i=0;i<1000;i++){
                int j;
                long long chengji = 1;
               
                if(i<=987){//i<=987  j<987+13
                        for(j=i;j<13+i;j++){ //j:0-3 1-4 2-5...996-999
                                chengji*=a[j]-48;  //四个数一组的乘积 （数组定义的是 char类型 里面的数是字符 字符 0的 ASCII码值-48=0...）
                        }
                        if(chengji>max){//比较找出乘积最大的值
                                max=chengji;
                        }
                }
        }
        printf("max=%lld\n",max);
}

foxiangzun

首先，这么长的一段数字里，有 0
其次，将这个数字阵列以 13 个为一个单位来切割，分配到不同的列表中
最后，在列表中没有 0 的前提下，相加的最大值就是相乘的最大值

有了以上三条思路，那么接下来就方便多了，代码如下：

1. numStr = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
   
2. list1 = []
   
3. numDict = {}
   
4. for i in range(987) :
   
5.         list1 = [int(j) for j in list(numStr[i: i + 13])]
   
6.         if 0 not in list1 :
   
7.                 numDict[sum(list1)] = list1
   
8. sorted(numDict)
   
9. print(max(numDict), numDict[max(numDict)])

复制代码

最终运行起来，只花费 0.0135s，结果是：85 [9, 7, 5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7]

永恒的蓝色梦想

foxiangzun 发表于 2019-11-5 19:47
首先，这么长的一段数字里，有 0
其次，将这个数字阵列以 13 个为一个单位来切割，分配到不同的列表中
最 ...

最后，在列表中没有 0 的前提下，相加的最大值就是相乘的最大值

所以你错了

foxiangzun

永恒的蓝色梦想 发表于 2020-5-2 16:26
所以你错了

确实错了。。1 在这个序列中，也会拉低最终的乘积值，所以 1 也不能在里面。。修改后的代码如下：

1. numStr = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
   
2. list1 = []
   
3. numDict = {}
   
4. for i in range(987) :
   
5.         list1 = [int(j) for j in list(numStr[i: i + 13])]
   
6.         if 0 not in list1 and 1 not in list1 :
   
7.                 numDict[sum(list1)] = list1
   
8. sorted(numDict)
   
9. print(max(numDict), numDict[max(numDict)])
   
10. flag = 1
    
11. for i in numDict[max(numDict)] :
    
12.     flag *= i
    
13. print(flag)

复制代码

永恒的蓝色梦想

foxiangzun 发表于 2020-5-3 09:26
确实错了。。1 在这个序列中，也会拉低最终的乘积值，所以 1 也不能在里面。。修改后的代码如下：

根本就不是这么回事，3和8，5和5 ，哪对和大？哪对积大？你的思路本身就是错误的

foxiangzun

永恒的蓝色梦想 发表于 2020-5-3 09:41
根本就不是这么回事，3和8，5和5 ，哪对和大？哪对积大？你的思路本身就是错误的

所以这里必须全部剖成 13 个一组的数，然后算出它们的乘积，最后再来比较结果么。。感觉这样好费内存的说

永恒的蓝色梦想

foxiangzun 发表于 2020-5-3 21:47
所以这里必须全部剖成 13 个一组的数，然后算出它们的乘积，最后再来比较结果么。。感觉这样好费内存的说 ...

是的。
可能你对内存没什么概念，这点内存啥也算不上

leon0149

max = 23514624000
0.000 s

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. long long mul = 1;
   
5. 
   
6. int ToString(char num){
   
7.     int n = ((int)num) - 48;
   
8.     return n;
   
9. }
   
10. 
    
11. int main(void)
    
12. {
    
13.     clock_t start, finish;
    
14.     double duration;
    
15.     char num[1000] = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    
16.     int n;
    
17.     long long max = 0;
    
18. 
    
19.     start = clock();
    
20.     for (int j = 0;j < 1000 - 13;) {
    
21.         for (int i = j; i < j + 13; ++i) {
    
22.             if (num[i] != '0') {
    
23.                 n = ToString(num[i]);
    
24.                 mul = mul * n;
    
25.             }
    
26.             else {
    
27.                 j = i + 1;
    
28.                 goto here;
    
29.             }
    
30.         }
    
31.         max = max > mul ? max : mul;
    
32. 
    
33.         mul = 1;
    
34.         j ++;
    
35.         continue;
    
36.         here:
    
37.         mul = 1;
    
38.     }
    
39.     finish = clock();
    
40. 
    
41.     printf("max = %lld\n", max);
    
42.     duration = (double )(finish - start) / CLOCKS_PER_SEC;
    
43.     printf("%.3f s", duration);
    
44.     return 0;
    
45. }

复制代码

yhhpf

1. num = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
   
2. num1 = []
   
3. for i in range(len(num) - 12):
   
4.     value = 1
   
5.     for a in range(13):
   
6.         value *= int(num[i+a])
   
7.     num1.append(value)
   
8. print(max(num1))

复制代码

快是很快...但，感觉解法太简单了0 0？

4444567

1. sn='7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
   
2. list1 = []
   
3. dict1 = {}
   
4. for i in range(0,989):
   
5.     k = 1
   
6.     for n in sn[i:i+13]:
   
7.         if int(n) == 0:
   
8.             break
   
9.         else:
   
10.             k = k * int(n)
    
11.      
    
12.     list1.append(k)
    
13.     dict1[i] = k
    
14.    
    
15. def get_value(i,k):#根据字典的值来查找键
    
16.     for i,k in dict1.items():
    
17.         if k == max(list1):
    
18.             print('所求数中连续的13位数字是：%s' % sn[i:i+13])
    
19. 
    
20. get_value(i,k)
    
21. print('最大乘积为：%s' % max(list1))
    
22.    
    

复制代码