Project Eulerに挑戦: 問題4

Table of Contents

問題4

3桁の2数の積で,回文になる最大のものを求めよ.

Cで解く

回文になるかどうかは, sprintf で文字列に変換してから確かめる.

 1:  int palindrome(int n) {
 2:      int i, j;
 3:      char s[11];
 4:      sprintf(s, "%d", n);
 5:      for (i = 0, j = strlen(s) - 1; i <= j; i++, j--) {
 6:          if (s[i] != s[j])
 7:              return 0;
 8:      }
 9:      return 1;
10:  }
11:  
12:  int e004() {
13:      int i, j, p;
14:      int m = 0;
15:      for (i = 100; i < 1000; i++) {
16:          for (j = i; j < 1000; j++) {
17:              p = i * j;
18:              if (palindrome(p))
19:                  m = p > m ? p : m;
20:          }
21:      }
22:      return m;
23:  }

Scalaで解く

回文をチェックする関数を作成する.

1:  def palindrome(n: Int) = {
2:    val s = n.toString
3:    s == s.reverse
4:  }

palindromeの実行結果は以下のようになる.

scala> palindrome(12321)
res: Boolean = true

したがって回答は以下で求められる.

scala> val ps = for (i <- 100 to 999; j <- i to 999) yield i * j
ps: ... = Vector(10000, 10100, ..., 998001)

scala> ps.filter(palindrome(_)).max

手で解く

6桁の回文は 105 a+104 b+103 c+102 c+10 b+a = 11(9091a+910b+100c) であり, 11の倍数になることはわかるが, それ以上の分析を進めて手で解くのは難しそうだ.

改善版

最大の回文を求めれば良いので,ループの回数を減らすことを目指す.

改善版 C

j のループを降順に変更し, 最初に回文が発見された時点でループを抜けるように変更する.

 1:  int e004() {
 2:      int i, j, p;
 3:      int m = 0;
 4:      for (i = 100; i < 1000; i++) {
 5:          for (j = 999; j >= i; j--) {
 6:              p = i * j;
 7:              if (palindrome(p)) {
 8:                  m = p > m ? p : m;
 9:                  break;
10:              }
11:          }
12:      }
13:      return m;
14:  }

この変更で,ループの回数は 405450回から 293035回に減少する.

これまでの回文の最大値 m が求まっている場合, j のループの最小値は m/i 以上になる.

そこでプログラムを以下のように変更する. m の初期値も 1 に変更している.

 1:  int e004() {
 2:      int i, j, p;
 3:      int m = 1;
 4:      for (i = 100; i < 1000; i++) {
 5:          int j0 = m / i;
 6:          for (j = 999; j >= i && j >= j0; j--) {
 7:              p = i * j;
 8:              if (palindrome(p)) {
 9:                  m = p > m ? p : m;
10:                  break;
11:              }
12:          }
13:      }
14:      return m;
15:  }

この変更で,ループの回数は 293035回から 49188回に減少する. かなり効果があったようだ.

早目に大きな m を発見したほうが,上の効果がさらに大きくなることが期待される. そこで i のループも降順に変更する.

 1:  int e004() {
 2:      int i, j, p;
 3:      int m = 1;
 4:      for (i = 999; i >= 100; i--) {
 5:          int j0 = m / i;
 6:          for (j = 999; j >= i && j >= j0; j--) {
 7:              p = i * j;
 8:              if (palindrome(p)) {
 9:                  m = p > m ? p : m;
10:                  break;
11:              }
12:          }
13:      }
14:      return m;
15:  }

この変更で,ループの回数は 3241回に減少する.

さらに,i または j が 11の倍数である条件を追加する.

 1:  int e004() {
 2:      int i, j, p;
 3:      int m = 1;
 4:      for (i = 999; i >= 100; i--) {
 5:          int j0 = m / i;
 6:          for (j = 999; j >= i && j >= j0; j--) {
 7:              if (i % 11 != 0 && j % 11 != 0)
 8:                  continue;
 9:              p = i * j;
10:              if (palindrome(p)) {
11:                  m = p > m ? p : m;
12:                  break;
13:              }
14:          }
15:      }
16:      return m;
17:  }
18:  

この変更で,ループの回数は 506回に減少する. 最初の 405450回に比較すると約800分の1である.

Date: 2017-09-29 21:44:18 JST

Author: 田村直之

Validate XHTML 1.0