【アルゴリズム】栄光学園中の入試問題を python で解いてみる

はじめに

こんな問題をツイッタで見かけて、特に問3の答えが気になったので python で解いてみました。

完成物

import itertools
from fractions import Fraction

def f(es):
    v = sum([ Fraction(es[i*2], es[i*2+1]) for i in range(len(es)//2) ])
    if v.denominator==1 and v <= 7:
        expr = "+".join([ f"{es[i*2]}/{es[i*2+1]}" for i in range(len(es)//2) ])
        print(f"Found {expr}=={v}")

for es in itertools.permutations(range(1, 11)):
    f(es)

実行結果

Found 1/2+3/6+4/8+7/10+9/5==4
Found 1/2+3/6+4/8+9/5+7/10==4
Found 1/2+3/6+7/10+4/8+9/5==4
...

最初の答えが出るまでは一瞬、全部計算し終わるまで M1 mac で 24 秒くらいかかりました。

解説

10! は 363 万くらいなので総当りでも何とかなるやろということで、1〜10 の順列を生成して先頭から□に埋めていって計算して分母が 1 かつ 7 以下になったら式を印字するようにしました。

感想

7 の取り扱いがめんどくさそうだな、7/1 みたいに各項が整数になるようにすればいいかなと思ったら 7/1 だけで 7 になってしまい、めんどくさいやつだと思って手で解くのはあきらめてスクリプトを書きました。

2023/01/06
テーマ: アルゴリズム / 2023 / すべて