2012年11月2日金曜日

プロジェクトオイラー 問63

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。

問63 「n 乗して得られる n 桁の正整数は何個あるか?」
5桁の数 16807 = 75は自然数を5乗した数である.
同様に9桁の数 134217728 = 89も自然数を9乗した数である.

自然数をn乗して得られるn桁の正整数は何個あるか?

-----

注意!!!
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の解答例は以下です。畳んでいます。
def f():
	import math
	return [(a,b,a**b) for a in xrange(1,10) for b in xrange(1, int(1/(1-math.log(a, 10)))+1)]

L = f()
print len(L),L


自然数aをb乗してb桁の正整数ということは、桁数の区切りは10の累乗値なので以下の式が成り立ちます。
0 ≦ 10(b-1) ≦ ab < 10b ・・・(A)
a>1、b>1 ・・・(B)

まず、aの変域を求めます。(A)の右部分の2式より、
1 ≦ a < 10 ・・・(C)

次にbの変域を求めます。
(A)の左部分をbについて解きます。
まず、左部分の2式の対数をとって、
(b-1)*log10 ≦ b*(log a)

次にbを左辺に寄せて、
(b-1)/b ≦ (log a)/log10

対数の底を10にして、
1-(1/b) ≦ log10a

1-log10a ≦ 1/b

b ≦ 1/(1-log10a)

(B)よりb>0なので、bの変域は
1 ≦ b ≦ 1/(1-log10a) ・・・(D)

上記(C)(D)の範囲で二重ループさせます。

2つの関数を使っています。

1.関数f()
・import math
 数学用関数モジュールmathをインポートして使えるようにしておきます。

・return [(a,b,a**b) for a in xrange(1,10) for b in xrange(1, int(1/(1-math.log(a, 10)))+1)]
 内包表記内に二重ループを入れています。
 まず前の「for a in xrange(1,10)」で、aが1以上10未満の整数でループします。
 そしてループ変数aを後ろのfor文へ渡します。
 後ろの「for b in xrange(1, int(1/(1-math.log(a, 10)))+1)」で、
 bが1以上1/(1-math.log10a)未満の整数でループします。
 math.log()関数は対数関数です。第2引数は対数の底です。
 int関数で切り捨てて整数にします。
 このa,bの値を先頭の式、(a,b,a**b)に渡します。
 これは問題に合うa, b, aのb乗の値のタプルです。
 このタプルを内包表記でリストにため、そのまま呼び出し元に返します。

2.関数の外
・L = f()
 print len(L),L
 関数f()で問題に合うa, b, aのb乗のタプルを格納したリストを取得しLとします。
 求める個数、とそのリストを表示します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
49

(追記)
・20130127 ネタバレ注意の追記など

0 件のコメント:

コメントを投稿