题目8：找出这个1000位数字中连续13个数字乘积的最大值
题目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
视频讲解：
https://www.bilibili.com/video/BV1jW4y1Q7h4/
思路解析及源码参考（C & Python）：
**** Hidden Message *****
嘿嘿嘿，我直接上暴力。
k = """7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"""
s = 0
for i in range(len(k) - 12):
w = int(k) * int(k) * int(k) * int(k) * int(k) * int(k) * int(k) * int(k) * int(k) * int(k) * int(k) * int(k) * int(k)
# print(w)
if w > s:
s = w
print(s)
对了，为啥我活跃的这几年都没看到你啊？
前面你加我好友我还是满脸愣{:10_277:}
再一看你是版主——我更加懵了{:10_282:}
不过好歹我知道了欧拉计划嘿嘿{:10_265:}
所以你现在开始又要坚持发题了喽？
以后周末拿到电脑有空就来做你的题{:10_279:} 还好不是高精度，是高精度我人就崩溃了{:10_256:}
#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;
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 - '0');
}
if (tmp > res) {
int tot = 0;
for (int j = i - p + 1; j <= i; ++j) {
ans[++tot] = (s - '0');
}
res = max(res, tmp);
}
}
for (int i = 1; i <= p; ++i) {
printf("%d", ans);
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:52 编辑
滑动窗口我也想到了，但是 0 就不好处理{:10_277:}
如果是 0 的话……指针就直接后移 13 位，遇到零就继续，在移动的过程中给顺便计算答案，嗯，好主意，O(N) 没错{:10_256:} Python Code
def main():
x = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
ans = 0
for i in range(len(x) - 12):
ji = x
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 - '0';
if (tmp > ans) ans = tmp;
}
}
printf("%lld\n", ans);
return 0;
}
n = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
p, max_p = 0, 0
for i in range(len(n)-12):
p = eval('*'.join(n))
if p > max_p:
max_p = p
print(max_p) 本帖最后由 傻眼貓咪 于 2023-5-28 10:51 编辑
numbers.txt73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450main.py（四行代码）FILE = open("numbers.txt")
numbers = "".join()
print(max(])) for n in range(len(numbers) - 13)]))
FILE.close() 本帖最后由 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 - 48,其中chars是字符，转化为整数再减去48就是阿拉伯数字
int currentNum = ((int)chars - 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;
}
https://i.imgloc.com/2023/05/28/VnFxaN.png 本帖最后由 tommyyu 于 2023-5-28 13:45 编辑
以下代码可以生成 “生成答案的代码”，只不过这个“生成答案的代码”有一点点长{:10_256:}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) 学习编程中的Ben 发表于 2023-5-28 06:43
对了，为啥我活跃的这几年都没看到你啊？
前面你加我好友我还是满脸愣
再一看你是版主——我更 ...
感谢支持！！！ wuliangtdi 发表于 2023-5-28 12:39
C# Code:
Nice~ tommyyu 发表于 2023-5-28 13:23
以下代码可以生成 “生成答案的代码”，只不过这个“生成答案的代码”有一点点长
确实长…… 傻眼貓咪 发表于 2023-5-28 10:49
numbers.txtmain.py（四行代码）
厉害哦~ zhangjinxuan 发表于 2023-5-28 07:49
滑动窗口我也想到了，但是 0 就不好处理
如果是 0 的话……指针就直接后移 13 位，遇到零就继 ...
是，0 的处理是比较麻烦一丢丢~ 这个比较难，学习 666 1 6666 111
页:
[1]
2