初学者のためのプログラミング学習サイト[Pythonプログラミング]数学オリンピックの問題を解いてみるよ2021年10月02日カテゴリ:プログラミングPython暇なので暇つぶしに数学オリンピックの問題をプログラムで解いてみることにしました。解説動画はこちらさて今回はこんな問題です。「各桁の数字が相異なるような37の倍数のうち最大のものを求めよ。雑なコードで解いてみることにします。各桁が異なる整数で最大になるのは・・・9876543210でしょうね。各桁が異なる整数になれば良いですね。コードはこんな感じになりました。break答えは・・・9876435012各桁が異なる整数で37で割り切れますね。コードでは判定する部分として37で割りきれるかどうかは37で割った余りが0になるということになります。%で余を求められるので計算できますね。10桁の各桁が異なるはいったん数字に直して10個の数字をセットに入れ込みます。すると各桁が違い場合は長さが10各桁で同じ数字が来た場合は長さが10未満になるので弾けます。この2つの判定を用いてその最大値を求めました。倍数であるとき,その整数を面白い整数と呼ぶことにする。面白い整数は全部でいくつあるか。これもさっきと同じ各桁が違うがそのまま使えますね。result.append(i)・・・うーーーん全然プログラムが終わりません。10桁なので90億回近く計算する羽目になります。これだと普通のPCではなかなか終わりません。そこでもっと効率の良いコードを考えてみることにします。result.append(num)print(len(result))itertoolsを使うと順列を求めることができます。この場合全ての桁の数が違う数値10個を使った順列を求めてあげれば10桁全ての整数で判定しなくても良くなります。答えはresultの個数を数えて3456個になりました。通りに表せる最小の数なのです。桁の正の整数を表している。このとき次の問題に答えなさい。この数式を少し変えてみるとこれならプログラムに組み込めますね。mとnを求める感じにしてみましょう。この二通りの組み合わせから求められる4桁の整数は1729になります。通りに表される最小の正の整数をラマヌジャンさんのタクシー数と言っているそうです。タクシー数は他にもありますが手計算するのはしんどいですねーーーでもプログラムならすぐに求めることができるのがプログラムのいいところです。数学オリンピックの問題でさえも整数問題なら、PCを持ち込めれば解ける!!!!!(多分ダメだーー)なので、答えだけは出せます。手でやる解き方は知りません。今回はここまでですそれでは。1時間で学べるPythonプログラミング[Pythonプログラミング]馬鹿でかい円周率を求めるアルゴリズム[Pythonプログラミング]モンティ・ホール問題のシミュレーション[Pythonプログラミング]人工衛星がどんだけ時間ズレるかプログラミングの力で求めてみようコーディングに迷った際に役に立ちWEB検索する時間を無くして作業時間を効率化できます。