#はじめに
2019年も1ヶ月が過ぎ受験シーズンに迫ってきた。
Atcoderを始めて2週間が過ぎ、毎日過去問をあさる日々。
せっかく受験シーズンに迫ってきたので競プロの基本問題っぽい受験数学の問題をpythonで解きたいと思った。
ぱっと思いついたのが僕が大学受験をした年のあの有名な2015年度東大理系数学の第5問。
mを2015以下の正の整数とする。{}_{2015}C_mが偶数となる最小のmを求めよ。
これをpythonで解いてみよう。
受験会場では合否を分けた1問だったらしい。
ちなみに答えはm = 32
#解
組み合わせ(combination)は
{}_nC_r = \frac{n!}{(n-r)!r!}
で表される事を用いてまず自分なりに書いてみる。
まあ上の式をそのままぶちこむだけ。
def f(n):
if n == 0:
return 1
else:
return n * f(n - 1)
for i in range(1, 2016):
if f(2015) / (f(2015 - i) * f(i)) % 2 == 0:
print(i)
break
else:
print("no answer")
###結果１
RecursionError: maximum recursion depth exceeded in comparison
のエラーが出た。
問題に対する解として間違ったコードは書いていないつもりだったが、どうやら再帰の回数の上限を超えてしまったらしい。
再帰の上限のデフォルトは1000とのこと。
このコードだと2000回以上再帰しているのでアウト。
これを解消するために
sys.setrecursionlimit(limit)
これで再帰の深さを設定する。
これらを考慮してもう一度書いてみた。
import sys
sys.setrecursionlimit(3000)
def f(n):
if n == 0:
return 1
else:
return n * f(n - 1)
for i in range(1, 2016):
if f(2015) / (f(2015 - i) * f(i)) % 2 == 0:
print(i)
break
else:
print("no answer")
最初の2行以外何も変えていない
###結果2
6
！？
間違ってる。（答えは32）
いろいろ調べた結果、型変換による精度落ちから誤差が生じているせいらしい。
11行目の
if f(2015) / (f(2015 - i) * f(i)) % 2 == 0:
の箇所でint型からfloat型へ型変換が行われ、floatの仮数部（23ビット）よりint（32ビット）の方が大きいため値によっては精度落ちが発生してしまうらしい。
参照：http://akademeia.info/index.php?%A5%B3%A5%F3%A5%D4%A5%E5%A1%BC%A5%BF%A4%CE%B8%ED%BA%B9
実際、このコードで2015_C_6を計算してみると
92274542271702512
という値になる。
正しくは、
92274542271702505
(https://keisan.casio.jp/exec/system/1161228812 による計算結果)
の為、+7だけ誤差が生じている。
他にもいろいろな種類の誤差があるらしいが、極端に大きいまたは小さい値や、それら同士の演算の際には誤差が生じるケースがあることを頭に入れておいて間違いなさそうだ。
とりあえず整数値だけを扱うために11行目を
if f(2015) // (f(2015 - i) * f(i)) % 2 == 0:
に変えてあげて実行してみると
###結果3
32
となり所望の結果が得られた。
いや待てよ、
誤差が怖いなら素直にやるより、もっと小さな値だけの演算だけを使うコードを書けばいいじゃないか。
#解2
def f(n):
li = []
while True:
for i in range(2, n+1):
if n % i == 0:
n = n // i
li.append(i)
break
else:
continue
else:
break
return li
for i in range(1, 2016):
a = 0
b = 0
for k in range(1, i+1):
a += f(2016 - k).count(2)
b += f(k).count(2)
if a > b:
print(i)
break
else:
print("no answer")
関数f(n)でnの素因数をひとつずつぶちこんだリストを返し、
分子の持つ素因数2の数が、分母の持つ素因数2の数を超えた時点で出力して終了。
結果はもちろん32。
最小に書いたコードが2015!という大きな値を扱うのに対し、このコードは扱う整数値の最大値が2016とかなり小さくなるので、なんか優しげである。
#結論
テスト期間中に考えることではない。（単位やばいです。）
#参考
https://atcoder.jp/
http://d.hatena.ne.jp/aldente39/20110713/1310559234
http://akademeia.info/index.php?%A5%B3%A5%F3%A5%D4%A5%E5%A1%BC%A5%BF%A4%CE%B8%ED%BA%B9
https://keisan.casio.jp/exec/system/1161228812
https://math.nakaken88.com/problem/tokyo-u-r-2015-5/