Project Euler で紹介されている問題33を解いてみました。問題に書いてある条件をみたす分数を全検索で求めます。
Project Euler 問題33（桁消し分数）
分数 49/98 は、面白い性質を持ちます。初心者が 9 で約分をして、49/98 = 4/8 とすると（正しくない約分ですが）偶然正しい結果となります。
30/50 = 3/5 は、同じように約分して正しい答えを得ていますが、この場合を自明な例と呼びます。
値が1未満で、分子と分母が2桁の数字で、同じ性質を持つ自明でない例が、4つあります。
この4つの分数の積を約分したときの、分母の値を求めよ。
解答例
分数を
$$\frac{n_2 \times 10 + n_1}{d_2 \times 10 + d_1}$$
と表現します。以下となる場合が候補となります。
- $n_1 = d_1$ ただし、$n_1 \neq 0$
- $n_1 = d_2$
- $n_2 = d_1$
- $n_2 = d_2$
それぞれの場合に、元の分数と一致しているか確認します。確認する関数を is_satisfied として別にしました。
また、回答を求めるためには、分数の約分が必要となります。分子と分母を、その最小公倍数で割ります。最小公倍数を求める関数 gcd は、整数の道具箱から引用しました。
全体の C プログラムは、以下となります。
#include <stdio.h>
int gcd(int a, int b)
{
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int is_satisfied(int numerator, int denominator)
{
int n1, n2, d1, d2;
int result = 0;
n2 = numerator / 10;
n1 = numerator % 10;
d2 = denominator / 10;
d1 = denominator % 10;
if ((n1 == d1)&&(n1 != 0)) {
if (n2 * denominator == d2 * numerator) {
result = 1;
}
}
if (n1 == d2) {
if (n2 * denominator == d1 * numerator) {
result = 1;
}
}
if (n2 == d1) {
if (n1 * denominator == d2 * numerator) {
result = 1;
}
}
if (n2 == d2) {
if (n1 * denominator == d1 * numerator) {
result = 1;
}
}
return result;
}
int main(void)
{
int i, j;
int i_product, j_product;
i_product = 1;
j_product = 1;
for (i = 10; i <= 99; ++i) {
for (j = i + 1; j <= 99; ++j) {
if (is_satisfied(i, j) == 1) {
// printf("%d / %d\n", i, j);
i_product *= i;
j_product *= j;
}
}
}
printf("Problem033: %d\n", j_product / gcd(i_product, j_product));
return 0;
}56行目を有効にすると条件を満たす分数を表示します。問題に記載してあるように4つの分数が見つかりました。
最後に
この問題は、2桁と2桁の数字を組み合わせて全通り調べました。組み合わせが少ない場合、式を使って解くより全検索をした方が早く解ける場合があります。
一方、各種考察を使って候補を間引かないと、全検索が難しい場合もあります。問題が持つ構造を見極める必要があるようです。
引き続き、Project Euler の問題を紹介していきます。
