Project Euler

Project Euler 問題43(割り切れる部分文字列)を解いてみる

760x428_Euler_043

Project Euler で紹介されている問題43を解いてみました。ある条件を満たすパンデジタル数の総和を求めます。ライブラリで順列を使える C++ を利用して解きました。

Project Euler 問題43(割り切れる部分文字列)

数字 1406357289 は、0 から 9 までの各数字が1回ずつ現われるため、0 から 9 までのパンデジタル数です。その部分文字列は、以下の興味深い性質を持っています。

d1 を 1 桁目、d2 を 2 桁目、… とします。

  • d2d3d4 = 406 は 2 で割り切れます。
  • d3d4d5 = 063 は 3 で割り切れます。
  • d4d5d6 = 635 は 5 で割り切れます。
  • d5d6d7 = 357 は 7 で割り切れます。
  • d6d7d8 = 572 は 11 で割り切れます。
  • d7d8d9 = 728 は 13 で割り切れます。
  • d8d9d10 = 289 は 17 で割り切れます。

同じ性質を持つ、0 から 9 までのパンデジタル数の合計を求めよ。

解答例

パンデジタル数については、問題32問題38問題41でも取り扱いました。今回のパンデジタル数は、0 を含みます。

C では標準ライブラリで順列のサポートがありません。標準ライブラリで順列のサポートがある C++ を使って解きます。順列を生成して、問題の条件を満たすか確認していくだけです。

確認する関数 is_satisfied を分けてプログラムしました。is_satisfied では、条件を満足しない場合が多い 17 から確認しています。また 5、2 の倍数の判定は末尾の数字だけから判断しています(20行目と27行目)。

解答を格納する変数 answer は、32ビットに収まらないため、long long 型としました。最終的に、C++ のプログラムは以下となります。

#include <iostream>
#include <algorithm>

using namespace std;

bool is_satisfied(int n[10])
{
	if ((n[7] * 100 + n[8] * 10 + n[9])% 17 != 0) {
		return false;
	}
	if ((n[6] * 100 + n[7] * 10 + n[8])% 13 != 0) {
		return false;
	}
	if ((n[5] * 100 + n[6] * 10 + n[7])% 11 != 0) {
		return false;
	}
	if ((n[4] * 100 + n[5] * 10 + n[6])% 7 != 0) {
		return false;
	}
	if (n[5] % 5 != 0) {
		/* n[3] * 100 + n[4] * 10 + n[5])% 5 == 0 */
		return false;
	}
	if ((n[2] * 100 + n[3] * 10 + n[4])% 3 != 0) {
		return false;
	}
	if (n[3] % 2 != 0) {
		/* n[1] * 100 + n[2] * 10 + n[3])% 2 == 0 */
		return false;
	}

	return true;
}

int main(void)
{
	int n[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

	long long int answer = 0;
	do {
		if (is_satisfied(n)) {
			long long int num = 0;
			for (int i = 0; i < 10; ++i) {
				num = num * 10 + n[i];
			}
			printf("%lld\n", num);
			answer += num;
		}
	} while (next_permutation(n, n + 10));

	printf("Problem043: %lld\n", answer);

	return 0;
}

条件を満たす6個のパンデジタル数が見つかり、このプログラムの出力が正解と判定されました。

最後に

条件を満たすパンデジタル数を丁寧に求めていく問題でした。

引き続き、Project Euler の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA