Project Euler で紹介されている問題32を解いてみました。ライブラリで順列を使える C++ を利用して解きました。
Project Euler 問題32（パンデジタル積）
n桁の数で、1からnまでのすべての数字をちょうど1回ずつ使うものをパンディジタル（pandigital）と呼ぶことにする。たとえば、5桁の数 15234 は1から5のパンディジタルである。
掛けられる数、掛ける数、積の式、39×186＝7254 が1から9のパンデジタルとなっている。7254はその積である。
掛けられる数/掛ける数/積が、1から9のパンデジタルとなる式の積の和を求めよ。
ヒント：いくつかの積は、いくつかの方法で得ることができるが、積の和としては、一度だけ含まれるようにしてください。
解答例
Project Euler 問題24（辞書式順列）で順列について紹介しました。Project Euler では、C を使って解くことが多かったですが、C では標準ライブラリで順列のサポートがありません。標準ライブラリで順列のサポートがあるC++を使って解きます。
順列を生成する next_permutataion を do-while と組みにして、1から9までのすべての順列を生成します。
この順列を、sep1、sep2 という切れ目で、3つの数字に分割します。配列のインデックスを使って表現すると3つの数字は以下となります。以下、[n, m) は、「n以上、m未満」を表します。
- 掛けられる数 num1 = [0, sep1)
- 掛ける数 num2 = [sep1, sep2)
- 積 num3 = 「sep2, 9)
また、複数の方法で同じ積を得ることができるため、set を使って重複を取り除いています。具体的な C++ プログラムは、以下となります。
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int main(void)
{
int n[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
set<int> p;
do {
int sep1, sep2;
for (sep1 = 1; sep1 <= 7; ++sep1) {
for (sep2 = sep1 + 1; sep2 <= 8; ++sep2) {
int num1 = 0;
int num2 = 0;
int num3 = 0;
for (int i = 0; i < sep1; ++i) {
num1 = num1 * 10 + n[i];
}
for (int i = sep1; i < sep2; ++i) {
num2 = num2 * 10 + n[i];
}
for (int i = sep2; i < 9; ++i) {
num3 = num3 * 10 + n[i];
}
if (num1 * num2 == num3) {
// printf("%d * %d = %d\n", num1, num2, num3);
p.insert(num3);
}
}
}
} while (next_permutation(n, n + 9));
int sum = 0;
for (auto it = p.begin(); it != p.end(); ++it) {
sum += *it;
}
printf("Problem032: %d\n", sum);
return 0;
}コメントアウトしている printf を有効にすると、見つけた式を表示します。以下の積は複数の式で見つかりました。
- 12 × 483 = 138 × 42 = 5796
- 18 × 297 = 198 × 27 ＝ 5346
最後に
順列のライブラリサポートがあれば、それほど難しくない問題でした。試してみると、上で紹介したように、積が同じになる複数の式が見つかりました。このような計算でも数の不思議を感じました。
引き続き、Project Euler の問題を紹介していきます。
