1000位数字中连续五位数字的最大产品
我正在解决欧拉项目的问题，如果我对这个问题的理解是正确的，我也不太确定。
问题8如下：
查找1000位数字中连续五位数字的最大产品。
我认为这意味着以下几点：
我需要find在1000位数字中连续运行的五个数字，然后将这些数字加起来得到总数。 我假设数字的大小可以是任何东西，即1,2,3或12,13,14或123,124,124或1234,1235,1236等。
我的这个理解是否正确，还是我误解了这个问题？
注意：请不要提供代码或解决scheme，我需要解决自己。
号码是：
73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 7163626956188267042825248360082 3257530420752963450
- 前五个连续的数字是：73167.他们的产品是7 * 3 * 1 * 6 * 7 = 882
- 接下来的五个连续数字是：31671.他们的产品是3 * 1 * 6 * 7 * 1 = 126
- 接下来的五个连续数字是：16717.他们的产品是1 * 6 * 7 * 1 * 7 = 294
等等。 注意重叠。 现在，找出产品在整个1000位数字上最大的连续五位数字。
代表数字的string中的数字是单个0-9。 所以12345号码有5位数字。 1234554321有10位数字。
乘积是总乘数，而不是总乘数。 所以3,5和7的乘积是105。
重述这个问题的方式（有点笨重）是：
给定一个1000位的数字，从中select5个连续的数字，当作为单独的数字并相乘时，给出最大的结果。
五个单数字。 1，5，8 …无论什么都出现在大数字中，都是连续的。 因此，如果一个块读取“… 47946285 …”，那么你可以使用“47946”，“79462”，“94628”，“46285”等
我的解决scheme只是即兴而已，通过outlook避免不必要的计算。
package com.euler; public class Euler8 { public static void main(String[] ar) throws Exception { String s = "73167176531330624919225119674426574742355349194934" + "96983520312774506326239578318016984801869478851843" + "85861560789112949495459501737958331952853208805511" + "12540698747158523863050715693290963295227443043557" + "66896648950445244523161731856403098711121722383113" + "62229893423380308135336276614282806444486645238749" + "30358907296290491560440772390713810515859307960866" + "70172427121883998797908792274921901699720888093776" + "65727333001053367881220235421809751254540594752243" + "52584907711670556013604839586446706324415722155397" + "53697817977846174064955149290862569321978468622482" + "83972241375657056057490261407972968652414535100474" + "82166370484403199890008895243450658541227588666881" + "16427171479924442928230863465674813919123162824586" + "17866458359124566529476545682848912883142607690042" + "24219022671055626321111109370544217506941658960408" + "07198403850962455444362981230987879927244284909188" + "84580156166097919133875499200524063689912560717606" + "05886116467109405077541002256983155200055935729725" + "71636269561882670428252483600823257530420752963450" ; Integer[] tokens = new Integer[s.length()]; for (int i = 0; i < s.length(); i++) { tokens[i] = (int) s.charAt(i)-48; } int prod = 1; int[] numberSet = new int[5]; int prodCounter = 1; for (int i=0; i<tokens.length-4; i++) { // Look ahead: if they are zeros in next 5 numbers, just jump. if ( tokens[i] == 0) { i = i+1; continue; } else if ( tokens[i+1] == 0) { i = i+2; continue; } else if ( tokens[i+2] == 0) { i = i+3; continue; } else if ( tokens[i+3] == 0) { i = i+4; continue; } else if ( tokens[i+4] == 0) { i = i+5; continue; } int localProd = tokens[i] * tokens[i+1] * tokens[i+2] * tokens[i+3] * tokens[i+4]; System.out.println("" + (prodCounter++) + ")" + tokens[i] + "*" + tokens[i+1] + "*" + tokens[i+2] + "*" + tokens[i+3] + "*" + tokens[i+4] + " = " + localProd); if (localProd > prod) { prod = localProd; numberSet[0] = tokens[i]; numberSet[1] = tokens[i+1]; numberSet[2] = tokens[i+2]; numberSet[3] = tokens[i+3]; numberSet[4] = tokens[i+4]; } } System.out.println("Largest Prod = " + prod + " By: (" + numberSet[0] + " , " + numberSet[1] + " , " + numberSet[2] + " , " + numberSet[3] + " , " + numberSet[4] + ")"); } }
您将得到：编号：99879产品：40824
$no = ""; $x = 0; $a = 0; $max = 0; while($a != 63450){ $a = substr($no, $x, 5); $prod = substr($a, 0, 1) * substr($a, 1, 1) * substr($a, 2, 1)* substr($a, 3, 1) * substr($a, 4, 1); if($prod >= $max){ $max = $prod; $theno = $a; } $x++; } echo 'Numbers: '.$theno.'<br>'; echo 'Product: '.$max;
这是我个人的解决scheme，使用一点残酷的力量：
Module Module1 Sub Main() Dim v() As Integer = {7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4, 9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3, 8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1, 1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7, 6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3, 6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9, 3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6, 7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6, 6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3, 5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7, 5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2, 8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4, 8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1, 1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6, 1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2, 2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8, 0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8, 8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6, 0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5, 7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0} Dim n = v.Length - 1 Console.WriteLine(ElementoMax(v)) Console.ReadKey() End Sub Function ElementMax(vett() As Integer) Dim MAX, temp1, temp2, temp MAX = vett(0) * vett(1) * vett(2) * vett(3) * vett(4) * vett(5) * vett(6) * vett(7) * vett(8) * vett(9) * vett(10) * vett(11) * vett(12) For i = 1 To (vett.Length - 13) temp1 = vett(i) * vett(i + 1) * vett(i + 2) * vett(i + 3) * vett(i + 4) * vett(i + 5) * vett(i + 6) * vett(i + 7) * vett(i + 8) * vett(i + 9) * vett(i + 10)* vett(i + 11) * vett(i + 12) temp2 = vett(i + 5) * vett(i + 6) * vett(i + 7) * vett(i + 8) * vett(i + 9) * vett(i + 10) * vett(i + 11) * vett(i + 12) temp = temp1 * temp2 If temp > MAX Then MAX = temp End If Next Return MAX End Function End Module
结果是… 😉
public class Problem008 { public static int checkInt(String s) { int product = 1; for (int i = 0; i < 5; i++) { Character c = new Character(s.charAt(i)); String tmp = c.toString(); int temp = Integer.parseInt(tmp); product *= temp; } return product; } public static void main(String[] args) { long begin = System.currentTimeMillis(); String BigNum = ""; String snip; int largest = 0; for (int i = 0; i <= (BigNum.length()-5); i++) { snip = null; for (int j = 0; j < 5; j++) { char c = BigNum.charAt(i+j); snip += c; } if (checkInt(snip) > largest) largest = checkInt(snip); } long end = System.currentTimeMillis(); System.out.println(largest); System.out.println(end-begin + "ms"); } } }
public class ProjectEuler8 { public static void main(String[] args) { int list[] = new int[1000]; int max = 0; String str = ""; for (int index = 0; index < 1000; index++) list[index] = str.charAt(index) - 48; for (int count = 0; count < 996; count++) { int product = list[count] * list[count + 1] * list[count + 2] * list[count + 3] * list[count + 4]; if (product > max) max = product; } System.out.println(max); } }
简单是更好，不是吗？
在C中，我把它复制到一个txt文件中并从中读取，或者你可以在开头初始化string。
#include <stdio.h> #include <stdlib.h> int main() { FILE *a; a=fopen("Long.txt","r"); char s[1001]; fscanf(a,"%s",s); char p[6]; int i=0,x,prdmax=1,m,n; while(s[i]!='\0') { p[0]=s[i]; p[1]=s[i+1]; p[2]=s[i+2]; p[3]=s[i+3]; p[4]=s[i+4]; p[5]='\0'; x=atoi(p); n=x; int prd=1; while(x!=0) { int q=x%10; prd*=q; x/=10; } if(prd>prdmax) { prdmax=prd; m=n; } i++; } printf("Numbers are: %d\n Largest product is: %d",m,prdmax); fclose(a); }
