黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

入試問題をプログラムで解いてみる(1):虫食い算と不定方程式(開成高校2013 大問1-1)

math 数学 python

問題(こちらより拝借)

f:id:program_study:20140214200556p:plain

解説

  • (100a + 10b +3) - (200 + 10a + b) = 100b + 10c +a
  • ∴89a -91b -10c = 197-[i]
  • 10*(8a -9b -c ) + (9a - b) = 197

ここで9a-bの1の位が7となる(a,b)は(a,b) = (1,2),(2,1),(4,9),(5,8),(6,7),(7,6),(8,5),(9,4)。さらに、(a,b) = (1,2),(2,1)のとき(i)の左辺<197になるので不適となり、b>=4 が必要

(ii):まず89a - 91b > 0 <=> a >91/89 b ∴a > bが必要。故に(a,b) = (7,6),(8,7),(9,4)に絞って考える。

  • 89a - 91b = 90(a-b)-(a+b)
  • (a,b)=(7,6)のとき, 89a - 91b = 90 -13 = 77<197より不適
  • (a,b)=(8,5)のとき, 89a - 91b = 270 - 13 = 257 より(a,b,c) = (8,5,6)
  • (a,b)=(9,4)のとき, 89a - 91b = 450 - 13 = 437。c =9 のとき(i)の左辺>0となるので不適。

以上より(a,b,c) = (8,5,6) (答)

[i]のa,b,cを総当たりで調べるpythonプログラムを書いてみた

今度は[i]「不定方程式:89a -91b -10c = 197」にa,b,cに1〜9全ての整数を代入し検証してみよう。まず試験中9*9*9 = 729通り全てを試すことは不可能だ。この為人力で解く場合は、理由をつけて出来る限り調べる回数を減らす事が要求される。出題者や採点者はこの過程を見たい事に注意だ(解答を省略するなということ)。

もちろん数学の力を付けたいならば、こういった事を考え続ける事が肝心だ。これが数学なりプログラムのアルゴリズムなりに活きていくだろう。あと、一般に総当たりに用いるa,b,cの個数が各々n個の時、その総当たり全て調べるプログラムの計算量はO(n^3)となる。この為nが大きいと計算が終わらなくなるので注意したい。

下記プログラムを走らせた結果、(a,b,c)=(8,5,6)が得られたので問題なし。計算量も少ないので、すぐ実行された。最後に本記事が数学好き、プログラム好きの目に留まる事を期待したい。