Величайший продукт из пяти последовательных цифр в 1000-значном числе

Question

Я работаю над проблемами в проекте Эйлера и не уверен, правильно ли я понимаю вопрос.

Проблема 8 заключается в следующем:

Найдите наибольшее произведение из пяти последовательных цифр в 1000-значном числе.

Я взял это, чтобы означать следующее:

Мне нужно найти любые пять чисел, которые идут подряд в 1000-значном числе, а затем сложить их, чтобы получить сумму. Я предполагаю, что размер чисел может быть любым, то есть 1,2,3 или 12,13,14 или 123,124,124 или 1234,1235,1236 и т.д.

Верно ли мое понимание этого или я неправильно понял вопрос?

Примечание: Пожалуйста, не предоставляйте код или решение, которое мне нужно решить самостоятельно.

Answer 1

Номер:

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

• Первые пять последовательных цифр: 73167. Их произведение 7 * 3 * 1 * 6 * 7 = 882
• Следующие пять последовательных цифр: 31671. Их произведение 3 * 1 * 6 * 7 * 1 = 126
• Следующие пять последовательных цифр: 16717. Их произведение равно 1 * 6 * 7 * 1 * 7 = 294

И так далее. Обратите внимание на совпадение. Теперь найдите пять последовательных цифр, произведение которых максимально на все 1000-значное число.

Answer 2

Цифра представляет собой один 0-9 в строке, представляющей число. Таким образом, число 12345 имеет 5 цифр. 1234554321 состоит из 10 цифр.

Продукт представляет собой итоговую сумму, а не общую сумму. Таким образом, произведение 3, 5 и 7 составляет 105.

(несколько неуклюжий) способ перефразировать вопрос:

Учитывая число из 1000 цифр, выберите из него 5 последовательных цифр, которые, взятые как отдельные числа и умноженные вместе, дают самый большой результат.

Answer 3

Пять однозначных цифр. 1, 5, 8 ... все, что появляется в большом числе, все подряд. Так что, если кусок прочитал «... 47946285 ...», то вы могли бы использовать «47946», «79462», «94628», «46285» и т. Д.

Answer 4

Это мое личное решение, использующее немного брутальной силы:

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

и результат ...; -)

Answer 5

Вы получите: Номера: 99879 Товар: 40824

$no = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
$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;

Answer 6

Единственная импровизация в моем решении - избежать ненужных вычислений, заглядывая в будущее.

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] + ")");
    }
}

Answer 7

В C я скопировал его в текстовый файл и прочитал из него, или вы можете просто инициализировать строку в начале.

#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);
}

Answer 8

public class ProjectEuler8
{
    public static void main(String[] args)
    {
        int list[] = new int[1000];
        int max = 0;
        String str = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
        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);
    }
}

Просто лучше, не правда ли?

Answer 9

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 = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
        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");
        }
    }
}