記事の内容
今回は、pythonに慣れるために簡単な数学パズルのようなものに挑戦します。
そのテーマは、「平方根を求める」です。どのようにコードを欠けば、効率よくある数の平方根を求めることができるのか、いろいろと工夫してみましょう。
python初心者の方にも、アルゴリズム初心者の方にもおすすめな記事です。「平方根」というテーマのもと、プログラミングの考え方に慣れていきましょう！
問題解決のPythonプログラミング
こちらの本にのっている題材を引用させてもらいます。そのほかにも、いろいろと面白い問題がのっているので、ぜひ読んでみてください。
反復法
まずは、素直に平方数を順に作っていく方法です。順に作っていき、もとめたいある数に一致するまで続けます。1,2,3,4,,,,の平方数を順に作成していきます。例えば、「64の平方根をもとめよ」という問題なら、1の2乗から8の2乗まで順に作ると、（8の2乗）=64となり、64の平方根は8だと求めることができます。
コンピュータが得意なしらみつぶしの方法と言えるでしょう。
ただし、注意点があります。それは、平方根がぴったりと整数になることはまれであるということです。よって、小数まで考えます。小数点以下のどの桁まで計算するか考えるべきです。
そのため、次の2点を工夫します。
・どれだけ平方根に近いのか基準値をもうける →epsilon
・whileループでどれくらい増やすか注意 →increment
この2点に注意したコードは次のようになります。
実装1
#探索空間を幅がincrementのスロットに分割している。平方根がどのスロットにあるのか次々に調べていく。 def findSquareRootWithinError(x, epsilon, increment): if x < 0: print("Sorry, no imaginary numbers") return numGuesses = 0 #whileループの繰り返し回数を計算 ans = 0.0 while x - ans**2 > epsilon: ans += increment numGuesses += 1 print("numGuesses =", numGuesses) if abs(x - ans**2) > epsilon: print("Failed on square root of", x) else: print(ans, "is close to square root of", x)
結果1
findSquareRootWithinError(64, .01, .001)
>>>numGuesses = 8000
8.000000000001005 is close to square root of 64
findSquareRootWithinError(65535, .01, .001)
>>>numGuesses = 255999
Failed on square root of 65535
findSquareRootWithinError(65535, .01, .00001)
>>>numGuesses = 25599803
255.99803007005775 is close to square root of 65535
スロットを細かくすればするほど、探索回数も増えていくのがわかります。すなわち、実行時間が増えていきます。もっと効率よく探索する方法はないでしょうか？
二分探索
もっと効率よく探索する方法があります。それは、探索する区間をしぼるというものです。各区間の中点の値とまずは比較することで、区間を右と左にわけることができます。右の区間に求める値があるだろうな、と絞ることができるので、左の区間の分はばっさりと捨てていいわけです。こうして、どんどん調べなくていい区間を捨てていくことができます。こうして、探索の効率をあげます。
それでは、2分探索を利用したコードを見てみましょう。
#2分法で探索 def bisetionSearchForSquareRoot(x, epsilon): if x < 0: print("Sorry, no imaginary numbers") return numGuesses = 0 low = 0.0 high = x ans = (high + low) / 2.0 while abs(ans**2 - x ) >= epsilon: if ans**2 < x: low = ans else: high = ans ans = (high + low) / 2.0 numGuesses += 1 print("numGuesses = ", numGuesses) print(ans, "is close to square root of", x)
実行結果もみてみましょう。探索回数が飛躍的に減少しています。
bisetionSearchForSquareRoot(65535, .01)
>>>numGuesses = 24
255.99804684519768 is close to square root of 65535
ただし、2分探索を使うことができる条件に注意です。それは、探索するデータがあらかじめソートされていることです。たとえば、整数のデータなら、その大きさ順に並んでいる必要があります。ですので、ソートアルゴリズムと一緒に学習するのがいいかもしれません。
