Project Euler で紹介されている問題38を解いてみました。パンデジタル数について解くため、ライブラリで順列を使える C++ を利用して解きました。
Project Euler 問題38(パンデジタル倍数)
192 という数字に 1、2、3 をそれぞれ掛ける。
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
それぞれの積を連結すると、1 から 9 のパンデジタル数 192384576 を得る。192384576 を 192 と (1,2,3) の連結積と呼ぶ。
9 から始めて 1、2、3、4、5 を掛けると、9 と (1,2,3,4,5) の連結積であるパンデジタル数 918273645 を得る。
整数と (1,2, … , n) との連結積として表される最大の 9 桁パンデジタル数を求めよ。ただし、n > 1 とする。
パンデジタル数の定義
問題32の問題文でパンデジタルを以下と定義しています。
n桁の数で、1からnまでのすべての数字をちょうど1回ずつ使うものをパンディジタル(pandigital)と呼ぶことにする。たとえば、5桁の数 15234 は1から5のパンディジタルである。
パンデジタルな数をパンデジタル数と呼びます。パンデジタル数は、0 を含む場合もあるようです。Wikipedeia の「パンデジタル数」の定義では、0 を含めています。この問題では、Project Euler の流儀に従います。
考察
問題文で、n > 1 としています。n = 1 の場合を認めると、9桁の数と (1) の連結積となり、明らかに 987654321 が最大となります。
問題文にもある 9 と (1,2,3,4,5) の連結積であるパンデジタル数 918273645 は、最大値の候補になります。このため、連結積であるパンデジタル数の一番左の桁は 9 とします。
最初の整数を2桁とします。連結積であるパンデジタル数の一番左の桁を 9 とすると、以下となり、パンデジタル数が9桁となりません。? は、数字1桁を表します。
9? → 18? → 27? → 残り1桁
最初の整数を3桁とします。こちらも2桁の場合と同じく、パンデジタル数の一番左の桁を 9 とすると、以下となり、パンデジタル数が9桁となりません。
9?? → 18?? → 残り2桁
最初の整数を4桁とします。この場合は、あり得ます。
9???? → 18??? (ちょうど9桁になる)
9から始まる4桁の数とそれに2を掛けた5桁を連結した9桁のパンデジタル数で最大のものを探します。もし見つからなければ、918273645 が最大となります。
解答例
順列を使うと楽に解くことができます。C では標準ライブラリで順列のサポートがありません。標準ライブラリで順列のサポートがあるC++を使って解きます。問題32では、順列を生成する next_permutataion を do-while と組みにして、1から9までのすべての順列を生成して解きました。
今回は、最大値を求めるため、ひとつ前の順列を生成する prev_permutataion を使います(28行目)。もし、この条件を満たすパンデジタル数が見つからなければ、918273645 を出力します(11行目)。
以下は、C++ のプログラムです。
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main(void)
{
int n[8] = {8, 7, 6, 5, 4, 3, 2, 1};
int answer = 918273645;
do {
int num1 = 9;
for (int i = 0; i < 3; ++i) {
num1 = num1 * 10 + n[i];
}
int num2 = 0;
for (int i = 3; i < 8; ++i) {
num2 = num2 * 10 + n[i];
}
if (num1 * 2 == num2) {
if (num1 * 100000 + num2 > answer) {
answer = num1 * 100000 + num2;
break;
}
}
} while (prev_permutation(n, n + 8));
printf("Problem038: %d\n", answer);
return 0;
}
このプログラムでは、条件を満たす数が見つかれば、ループを break します。break しなければ、解答以外に 927318546 と 926718534 が条件を満たすことが分かります。
最後に
連結積の定義から最大値となるのは、4桁+5桁の場合に絞り込めました。このため、プログラムはすっきりと書けました。
引き続き、Project Euler の問題を紹介していきます。