人生、Python、三角数
【イントロ】 日々の生活に疲れてくると、どうでもいいこと考えてしまいますよね。 たとえば、 「もっと別の生き方があったのではないか？」、 とか 「この自然数は何個の三角数で表せるんだろうか？」 とか。 そこで本記事では、Pythonを使用して「任意の自然数が何個の三角数で表せるか」判定するプログラムを作成したので、公開します。 【方法】 プログラムはPythonで書きました。本当はRustを使って書きたかったんですがそもそも書き方で悩むとかいう別問題があったので、アルゴリズムを考えて書きやすいPythonを採用しました。 そもそも、問題意識のきっかけは” yukicoder ”さんのこちらの問題「 No.634 硬貨の枚数1 」です。要は「任意の自然数が何個の三角数で表せるのか判定しましょう」という問題です。大きな数だと一体何個必要なのか想像もつきません。そこで小さな数で試しに実験してみたのが図1です。 図1、１０までの自然数を三角数で分解した場合 ・・・どうも必要な個数が3個を超えない予感がしてきました。 検索してみると、 こういう定理 (または こちら ) 「すべての自然数はたかだかｍ個のｍ角数で表せる」 が存在することがわかりました。やっぱ数学ってすごい。。。 この定理のお陰で与えられた問題は「任意の自然数は三角数１，２，３個で分割できるか判定する」と読み替えることが出来ます。この問題をPythonで解くこととしました。 【結果】 作成したプログラムは下記のとおりです。 もっとスマートな書き方があると思いますが、素人なので許してください。 import math #三角数の計算 def triangle(n): p = n*(n+1)/2 return p #与えられたN以下の最大の三角数を満たすqを返す def kirisute(n): p=(-1+math.sqrt(1+8*n))/2 q=math.floor(p) return q #与えられたnまでの三角数のリストを返す def trilist(n): list=[] for i in range(1,n+1): x=triangle(i) li...