Project Euler で紹介されている問題36を解いてみました。2つの基数に対して回文数となっている数を求めていく問題です。
Project Euler 問題36(ダブルベース回文数)
10 進数 585 = 10010010012 (2 進数)は、どちらの基数でも回文数となります。
10進数としても、2進数としても回文数となる100万未満の数の合計を求めよ。
(どちらの基数でも、数字の先頭がゼロではないことに注意してください。)
解答例
Project Euler 問題4で回文数についての問題を解きました。逆さから読んだ数を求める関数(reversed_no)と回文数か確認する関数(is_palindrome)を流用します。ただし、どちらの関数も基数が指定できるように引数 base を追加しました。
10進数でも2進数でも回文数になっている100万未満の自然数の合計を求めます。
全体の C プログラムは、以下となります。
#include <stdio.h>
int reversed_no(int number, int base)
{
int reverse = 0;
while (number > 0) {
reverse = reverse * base + (number % base);
number = number / base;
}
return reverse;
}
int is_palindrome(int number, int base)
{
return number == reversed_no(number, base);
}
int main(void)
{
int i, sum;
sum = 0;
for (i = 1; i < 1000000; i++) {
if ((is_palindrome(i, 2) == 1)&&(is_palindrome(i, 10) == 1)) {
// printf("%d\n", i);
sum += i;
}
}
printf("Problem036: %d\n", sum);
return 0;
}
コメントした行(27行目)を有効にすれば、条件を満たす数を出力します。該当する数は、19個ありました。
最後に
過去に解いた問題(問題4)の結果を流用して問題を解きました。過去に書いたプログラムを流用できると、うれしい気分になります。
引き続き、Project Euler の問題を紹介していきます。