Project Euler Problem 8

 Tìm 13 số liên tiếp trong số có 1000 chữ số mà có tích 13 số này lớn nhất. Giá trị số đó là gì ?

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Tìm 13 số liên tiếp trong số có 1000 chữ số mà có tích 13 số này lớn nhất. Giá trị số đó là gì

Bắt đầu ở từng vị trí mà tối thiểu 13 con số (biến span) có thể tìm thấy, vòng lăp sẽ qua 13 con số và:

convert từng con số từ mã ASCII thành số: Numeric = ascii -'0'

nhân tất cả các con số đã convert

Nếu tích lớn hơn các số trước đó thì lưu lại

Ngoài ra thay vì nhân tất cả con số lặp đi lặp lại, có thể sử dụng một phần lớn tích của lần lặp trước

ví dụ P0=x0*x1*x2*x3

thì P1 = x1*x2*x3*x4=P0*x4/x0

Nó sẽ giảm độ phức tạp xuống

#include <iostream>

#include <string>

int main()

{

  unsigned int tests;

  std::cin >> tests;

  while (tests--)

  {

    // length of string

    unsigned int length;

    // number of relevant consecutive digits

    unsigned int span;

    // read number as a string

    std::string number;

    std::cin >> length >> span >> number; //(1000 13 number)

    // results can be much bigger than 32 bits ... but 64 bits are enough, though

    unsigned long long best = 0;

    // loop ends when there are less than "span" digits left

    for (int start = 0; start + span < length; start++)

    {

      unsigned long long current = 1;

      // convert digits from ASCII to numbers and multiply

      for (unsigned int i = 0; i < span; i++)

        current *= number[start + i] - '0';

      // better than before ?

      if (best < current)

        best = current;

    }

    std::cout << best << std::endl;

  }

  return 0;

}

Convert mã ASCII từ string thành number, ví dụ mã ascii của char 1 là 49 dec, mã ascii của char 0 là 48 dec thì trừ đi sẽ ra 1 decimal

number[start + i] - '0'; : Khi ta access từng phần tử của mảng string, thì nó sẽ convert về int của ký tự đó, trừ đi int của ký tự 0 sẽ được chính số đó ở dạng int.

for (int start = 0; start + span < length; start++)

start là vị trí của ký tự trong mảng char 1000 số.

Chạy từng mảng này, nhưng mà chạy tới điều kiện là start + 13 số liên tiếp phải nhỏ hơn chiều dài 1000 số.

      for (unsigned int i = 0; i < span; i++)

        current *= number[start + i] - '0';

      // better than before ?

      if (best < current)

        best = current;

    }

Đoạn này đơn thuần chỉ là nhân để lấy tích 13 số bằng cách access array bằng start offset + 13 con số chạy của span. Ngoài ra là phép trừ đi int của char 0 để chuyển đổi number char thành number int.