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

欧拉计划 · 发表于 2023-5-28 05:30:17

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

Largest product in a series

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 位数中，连续四个数字的最大乘积是 9 × 9 × 8 × 9 = 5832。

找出以下这个 1000 位的整数中连续 13 个数字的最大乘积。

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

视频讲解：

思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

学习编程中的Ben · 发表于 2023-5-28 06:37:17

嘿嘿嘿，我直接上暴力。

k = """7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"""
s = 0
for i in range(len(k) - 12):
    w = int(k[i]) * int(k[i+1]) * int(k[i+2]) * int(k[i+3]) * int(k[i+4]) * int(k[i+5]) * int(k[i+6]) * int(k[i+7]) * int(k[i+8]) * int(k[i+9]) * int(k[i+10]) * int(k[i+11]) * int(k[i+12])
    # print(w)
    if w > s:
        s = w

print(s)

学习编程中的Ben · 发表于 2023-5-28 06:43:37

对了，为啥我活跃的这几年都没看到你啊？
前面你加我好友我还是满脸愣

再一看你是版主——我更加懵了

不过好歹我知道了欧拉计划嘿嘿

所以你现在开始又要坚持发题了喽？
以后周末拿到电脑有空就来做你的题

zhangjinxuan · 发表于 2023-5-28 07:48:04

还好不是高精度，是高精度我人就崩溃了

#include <bits/stdc++.h>
using namespace std;

string s = "73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";
int len;
long long tmp = 1, res = 0;
const int p = 13;
int ans[15];

int main() {
        len = s.size();
        for (int i = p; i <= len; ++i) {
                tmp = 1;
                for (int j = i; j >= i - p + 1; --j) {
                        tmp *= (s[j] - '0');
                }
                if (tmp > res) {
                        int tot = 0;
                        for (int j = i - p + 1; j <= i; ++j) {
                                ans[++tot] = (s[j] - '0');
                        }
                        res = max(res, tmp);
                }
        }
        for (int i = 1; i <= p; ++i) {
                printf("%d", ans[i]);
                if (i != p) printf(" * ");
                else puts("");
        }
        printf("=%lld", res);
        return 0;
}
/*
553210953*/

5 * 5 * 7 * 6 * 6 * 8 * 9 * 6 * 6 * 4 * 8 * 9 * 5
=23514624000

zhangjinxuan · 发表于 2023-5-28 07:49:01

本帖最后由 zhangjinxuan 于 2023-5-28 07:52 编辑

滑动窗口我也想到了，但是 0 就不好处理

如果是 0 的话……指针就直接后移 13 位，遇到零就继续，在移动的过程中给顺便计算答案，嗯，好主意，O(N) 没错

元豪 · 发表于 2023-5-28 07:57:34

Python Code

def main():
        x = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
        ans = 0
        for i in range(len(x) - 12):
                ji = x[i: i + 13]
                tmp = 1
                for i in ji:
                        tmp *= int(i)
                        if tmp > ans:
                                ans = tmp
        print(ans)

C++ Code

#include <bits/stdc++.h>
using namespace std;

long long ans, tmp;
string a = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";

int main(){
        for (int i = 0; i < a.size() - 12; i++){
                tmp = 1;
                for (int j = 0; j < 13; j++){
                        int ii = j + i;
                        tmp *= a[ii] - '0';
                        if (tmp > ans) ans = tmp;
                } 
        }
        printf("%lld\n", ans);
        
        return 0;
}

liuhongrun2022 · 发表于 2023-5-28 08:29:57

n = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
p, max_p = 0, 0
for i in range(len(n)-12):
    p = eval('*'.join(n[i:i+13]))
    if p > max_p:
        max_p = p
print(max_p)

傻眼貓咪 · 发表于 2023-5-28 10:49:19

本帖最后由傻眼貓咪于 2023-5-28 10:51 编辑

numbers.txt

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

main.py（四行代码）

FILE = open("numbers.txt")
numbers = "".join([each for each in FILE.read().split('\n')])
print(max([eval('*'.join([each for each in numbers[n : n + 13]])) for n in range(len(numbers) - 13)]))
FILE.close()

wuliangtdi · 发表于 2023-5-28 12:39:28

本帖最后由 wuliangtdi 于 2023-5-28 15:03 编辑

C# Code:

internal class Program
    {
        static void Main(string[] args)
        {
            long max = GetMax();
            Console.WriteLine($"相邻的13个数字相乘最大的数为:{max}");
            Console.ReadLine();
        }


        public static long GetMax()
        {

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

            
            char[] chars = digits.ToCharArray();

            int slidWidowSize = 13;

            long Max = 0;

            for (int i = 0; i < chars.Length - slidWidowSize; i++)
            {
                //进行相乘的，
                long multiplySum = 1;

                for (int j = 0; j < slidWidowSize; j++)
                {
                    //chars[i+j] - 48,其中chars[i+j]是字符，转化为整数再减去48就是阿拉伯数字
                    int currentNum = ((int)chars[i+j] - 48);

                    multiplySum = (multiplySum * currentNum);
                }

                if (multiplySum > Max)
                {
                    Max = multiplySum;
                }

            }

            return Max;
        }
    }

还有另外一种使用Linq方法来简化:

public static long GetMaxFormLinq()
        {
            string number = "73167176531330624919225119674426574742355349194934" +
                            "96983520312774506326239578318016984801869478851843" +
                            "85861560789112949495459501737958331952853208805511" +
                            "12540698747158523863050715693290963295227443043557" +
                            "66896648950445244523161731856403098711121722383113" +
                            "62229893423380308135336276614282806444486645238749" +
                            "30358907296290491560440772390713810515859307960866" +
                            "70172427121883998797908792274921901699720888093776" +
                            "65727333001053367881220235421809751254540594752243" +
                            "52584907711670556013604839586446706324415722155397" +
                            "53697817977846174064955149290862569321978468622482" +
                            "83972241375657056057490261407972968652414535100474" +
                            "82166370484403199890008895243450658541227588666881" +
                            "16427171479924442928230863465674813919123162824586" +
                            "17866458359124566529476545682848912883142607690042" +
                            "24219022671055626321111109370544217506941658960408" +
                            "07198403850962455444362981230987879927244284909188" +
                            "84580156166097919133875499200524063689912560717606" +
                            "05886116467109405077541002256983155200055935729725" +
                            "71636269561882670428252483600823257530420752963450";

            int adjacentDigits = 13;

            long greatestProduct = number.Select((c, i) => number.Substring(i, Math.Min(adjacentDigits, number.Length - i))
                    .Select(d => long.Parse(d.ToString())).Aggregate((a, b) => a * b)).Max();

            return greatestProduct;
        }

登录/注册后可看大图

tommyyu · 发表于 2023-5-28 13:23:43

本帖最后由 tommyyu 于 2023-5-28 13:45 编辑

以下代码可以生成 “生成答案的代码”，只不过这个“生成答案的代码”有一点点长

ans = ''
ans += ('a = []\n')
ans += ('num = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450')
ans += ('\ns_num = str(num)\n')
i = 0
for i in range(-12+len('7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450')):
    ans += (f'a.append( int(s_num[{i}]) * int(s_num[{i+1}]) * int(s_num[{i+2}]) * int(s_num[{i+3}]) * int(s_num[{i+4}]) * int(s_num[{i+5}]) * int(s_num[{i+6}]) * int(s_num[{i+7}]) * int(s_num[{i+8}]) * int(s_num[{i+9}]) * int(s_num[{i+10}]) * int(s_num[{i+11}]) * int(s_num[{i+12}]) )\n')
ans += ('print(max(a))')
print(ans)

欧拉计划 · 发表于 2023-5-29 02:54:29

学习编程中的Ben 发表于 2023-5-28 06:43
对了，为啥我活跃的这几年都没看到你啊？
前面你加我好友我还是满脸愣
再一看你是版主——我更 ...

感谢支持！！！

欧拉计划 · 发表于 2023-5-29 02:54:53

wuliangtdi 发表于 2023-5-28 12:39
C# Code:

Nice~

欧拉计划 · 发表于 2023-5-29 02:55:10

tommyyu 发表于 2023-5-28 13:23
以下代码可以生成 “生成答案的代码”，只不过这个“生成答案的代码”有一点点长

确实长……

欧拉计划 · 发表于 2023-5-29 02:55:31

傻眼貓咪发表于 2023-5-28 10:49
numbers.txtmain.py（四行代码）

厉害哦~

欧拉计划 · 发表于 2023-5-29 02:56:26

zhangjinxuan 发表于 2023-5-28 07:49
滑动窗口我也想到了，但是 0 就不好处理

如果是 0 的话……指针就直接后移 13 位，遇到零就继 ...

是，0 的处理是比较麻烦一丢丢~

auend · 发表于 2023-6-2 14:10:17

这个比较难，学习

Kazimierz · 发表于 2023-6-24 16:30:00

想不出用户名 · 发表于 2023-6-29 21:29:06

xyLi · 发表于 2023-7-3 16:27:37

6666

1412342464 · 发表于 2023-7-3 17:01:15

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

评分