12/12 データの検索(3)

12/12 データの検索(3)

前回の補足

前回の感想，質問より

Q.
今日は空調が暑かったので、授業中に学生の意見を聞くなどして調整してもらえると助かります。
A.
情報教育棟の空調は事務室の集中管理なので、電話をすれば調整できたかもしれません。ただ、冷房と暖房は使える期間が限られているケースもあるので、暖房を弱めることはできても，冷房には切り替えることはできないかもしれません．
Q.
mergesortのプログラム 
def mergesort(a): #配列aを整列
  n = len(a)
  if n <= 1: #短いときはそれでよし
    return a
  else: 
    l = mergesort(a[0 : n//2])
    r = mergesort(a[n//2 : n])
      #前半と後半をそれぞれ整列
    return merge(l,r)
      #整列した結果を併合
で，なぜ、else以下でmergesort()をそれぞれ行うだけで、整列できるのでしょうか。数列が2つあることが必要なはずですが、一つでも整列できるのですか。
A.
「mergesort()をそれぞれ行う」部分は「整列済の配列を2つ作る」部分であり，たしかにそれだけでは整列できません．「整列済の配列2つから整列済の配列を1つ作る」部分が「merge(l, r)」であり，その部分が併合整列法の主要部分になっています．mergeが別の関数で定義されているので，わかりにくかったかもしれません．
Q.
誤差のために、0.07*100が７にならないというのは不便だと感じた。
A.
そうですね．python でもdecimalというモジュール (ライブラリ) を使うと10進小数を決められた桁までは誤差なく表現できます． 
IN [1]: import decimal
        a = decimal.Decimal('0.07')
        b = decimal.Decimal('7')
        b - a * 100 == 0.0
OUT[1]: True
ただ，これで誤差なく表現，計算できる数は浮動小数点数と同様に限られていますし，実行速度も速くないので特別な必要がある場合以外は使われません．
Q.
併合整列法はmergesort関数の中にmergesort関数が現れていますから、一種の再帰関数と言えるのでしょうか？
A.
はい。講義で定義したmergesortの関数は再帰関数です。併合整列法は再帰関数で書くことで、自然に書くことができて、効率も良いアルゴリズムの代表的な例となっています。

前回の課題について

講義資料

講義フォルダの作成

投票システム

vote.pyをダウンロードして(「リンク先のファイルを別名で保存」で，ホームフォルダの下のalgo18を選択(なければ作る)．".txt"を「追加しない」を選ぶ)保存します．ドックからターミナルを起動して， 
cd ~/algo18
を済ませてから， 
python vote.py 選択肢番号
のように使います．

Jupyter Notebookを使いながら(一旦終了せずに)，投票システムも使うには，ターミナルのメニューバーの「シェル」->「新規タブ」を選ぶか，[Command]+[T]で別のタブを開いて(あるいは[Command]+[N]で別のウィンドウを開いて)，投票システムを使うことをお勧めします．このあたりのことは，「はいぱーワークブック」の15.4 ターミナルの便利な使い方に書いてあるので参考にしてください．

テキストの補足

Notebook教材

以下のNotebook教材は，~/algo18 以下に ダウンロードして，Jupyter Notebookからopenして使ったり， Google Colaboratoryを使って，クラウド実行環境でPythonプログラムを実行できます．ダウンロードする場合もGoogle Colaboratoryの使い方を参照してください．Googleアカウントへのログインを求められたときは，通常のGoogleアカウント「XXX@gmail.com」ではなく，ECCSクラウドメールのアカウント「XXX@g.ecc.u-tokyo.ac.jp」を使ってログインしてください．

今日の課題