Project Euler で紹介されている問題8を解いてみました。1000桁の入力をどのように取り込むかを話題にします。数学的な考察よりも、プログラムとしてどう書くかの要素が強い問題です。
問題8（積の最大値）
以下の1000桁（50桁×20行）の数字のうち、積が最大となる隣接する4つの数字は、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同じ1000桁の数字のうち、積が最大となる隣接する13個の数字を見つけて、この積の値を求めよ。
解答例
数学的な考察より、プログラミング言語の使い方を問う側面が強い問題です。まず問題として与えられている1000桁の数字をどのようにプログラムに与えるかですが、方法は大きく分けると2つあります。
- プログラムに変数として定義する。
- 内容をファイルに書いて、それを読み込む。
大きなデータを取り扱う場合、2のやり方を採用することになりますが、この問題は1000桁であるため、1のやり方としました。ファイルの入力は、それだけで敷居が高くなると考えたためです。
C 言語での実装例です。問題の数字を文字列で与えました。C は空白（改行含む）で区切られた文字列をコンパイル時に連結して解釈します。このため50桁の数字を含む20個の文字列は、連結されて1000桁の文字列（を表す char の配列）となります。プログラムの冒頭で、文字列で与えられた数字の列を int の配列に変換しておきます。
ループ文では、1個違いミスに気を付ける必要があります。また、求める積は C の long int の範囲より大きくなるため、unsinged long long int を使いました。
#include <stdio.h>
typedef unsigned long long int ull;
char problem_string[] =
"73167176531330624919225119674426574742355349194934"
"96983520312774506326239578318016984801869478851843"
"85861560789112949495459501737958331952853208805511"
"12540698747158523863050715693290963295227443043557"
"66896648950445244523161731856403098711121722383113"
"62229893423380308135336276614282806444486645238749"
"30358907296290491560440772390713810515859307960866"
"70172427121883998797908792274921901699720888093776"
"65727333001053367881220235421809751254540594752243"
"52584907711670556013604839586446706324415722155397"
"53697817977846174064955149290862569321978468622482"
"83972241375657056057490261407972968652414535100474"
"82166370484403199890008895243450658541227588666881"
"16427171479924442928230863465674813919123162824586"
"17866458359124566529476545682848912883142607690042"
"24219022671055626321111109370544217506941658960408"
"07198403850962455444362981230987879927244284909188"
"84580156166097919133875499200524063689912560717606"
"05886116467109405077541002256983155200055935729725"
"71636269561882670428252483600823257530420752963450";
int problem[1000];
int main(void)
{
int i, j;
ull product, max;
for (i = 0; i < 1000; ++i) {
problem[i] = problem_string[i] - '0';
}
max = 0;
for (i = 0; i <= 1000 - 13; ++i) {
product = 1;
for (j = 0; j < 13; ++j) {
product *= (ull)problem[i + j];
}
if (product > max) {
max = product;
}
}
printf("Problem008: %lld\n", max);
return 0;
}考察
正の解がある前提では、途中で 0 を検出した場合、その積は 0 になるため、解の候補にはなりません。0 を検出した場合は次の桁から調べればよいことも分かります。
実装としては、0 を検出した場合は、上位のループ変数 i の値を書き換えて、continue します。continue は最も内側のループのループ変数 j の再初期化と次の判定に移ります。すぐにこのループを抜けるため、j の値に 13 を代入しておきます（実際には、continue のあと、j はインクリメントされるため 14 で判定されます）。
このコードは、ループ変数をループ本体中で変更するなど、将来のトラブルになりやすい書き方をしており、プログラムとしては推薦できません。考察のひとつとして参考にしていただければと思います（main だけ示します）。
int main(void)
{
int i, j;
ull product, max;
for (i = 0; i < 1000; ++i) {
problem[i] = problem_string[i] - '0';
}
max = 0;
for (i = 0; i <= 1000 - 13; ++i) {
product = 1;
for (j = 0; j < 13; ++j) {
if (problem[i + j] == 0) {
i = i + j;
j = 13;
continue;
}
product *= (ull)problem[i + j];
}
if (product > max) {
max = product;
}
}
printf("Problem008: %lld\n", max);
return 0;
}最後に（問題の補足）
この問題は、当初5個の隣接する数字の積の最大値を求める問題でした。5個であれば、数字を追いかけていけば解を見つけることができる可能性があるため、プログラムが必要となる13個に変更したようです。問題の変更は、2014年5月18日に行われたため、この問題の過去の解説にはご注意ください（わたしも過去作ったプログラムを調べたら、5個バージョンで解いていたものが見つかりました）。
引き続き、Project Euler の問題を紹介していきます。
