2015年7月5日日曜日

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

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問112「はずみ数」
左から右までどの桁もその左の桁を下回らない数を増加数と呼ぶ. 例えば, 134468.
同様に, どの桁もその右の桁を下回らない数を減少数と呼ぶ. 例えば, 66420.
増加数でも減少数でもない正の整数をはずみ数と呼ぶことにする. 例えば, 155349.

100以下にはずみ数が無いのは明らかだが, 1000未満では半数を少し上回る525個がはずみ数である.
実際, はずみ数の割合が50%に達する最少の数は538である.
驚くべきことに, はずみ数はますます一般的になり, 21780でははずみ数の割合は90%に達する.
はずみ数の割合がちょうど99%になる最小の数を求めよ.






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






私の回答例は以下の通りです。
def f(n):
	i, b, c, r = 0, 0.0, 0.0, n/100.0
	while True:
		i += 1
		s = str(i)
		t = "".join([j for j in sorted(s)])
		u = "".join([j for j in sorted(s, reverse=True)])
		if t<s<u: b += 1
		else: c += 1
		if r<=b/(b+c): break

	return i

n=99
s = f(n)
print s



小さい数から順に各桁を昇順降順にソートした値と比較することではずみ数か判定し、件数カウントしその割合を計算しました。

1.関数f(n)
・はずみ数の割合がちょうどn%になる最小の数を返します。
・変数iは候補値、変数bははずみ数の個数、変数cははずみ数以外の個数、変数rは割合です。
・変数sで候補値を文字列にします。
  ループ変数jでひと桁ずつ取り出し、sorted関数で昇順にして再度連結した値を変数tとし、sorted関数のreverse引数をTrueにすることで降順にして再度連結した値を変数uとします。
・変数tとuはそれぞれ増加数と減少数なので、変数sがこれらの間の値であれば、はずみ数と判定します。





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