エンジョイC013回目ホーナーの法則３、ソート（2020-06-21）

ほえほえ＠スプシマン @hoehoe1234

エンジョイC 13回目。新メンバも加わりましたがいきなりホーナーの最終問題に挑みます。x^n（n=100)をどう計算するか？xは実数ですのでそのまま100回演算を繰り返すと遅くなります。うまい方法はないでしょうか？図はまずは再帰でエレガントに解けること（８回の掛け算）を示しています。 pic.twitter.com/FncvrWf9KJ

拡大

ほえほえ＠スプシマン @hoehoe1234

再帰をループに直します。p(100)はp(50)^2と定義できます。nが奇数であればたとえばp(25)はp(24)^2*xと定義できます。ほしいnを列挙すると100,50,25,12,6,3,1となります。この数列を取得するうまい方法はないでしょうか？ pic.twitter.com/DpCSWg6qL2

拡大

ほえほえ＠スプシマン @hoehoe1234

再帰呼び出し時にはnを1/2（切り捨て）しています。すなわち最下位ビットを切り捨てて１ビット右にシフトします。n=100のビットパターン7ビットの左部分ビット列がまさに50を表しています。すなわち左部分文字列がほしい数値そのものということになります。（この辺はややこししです） pic.twitter.com/KUEkgKIIMS

拡大

ほえほえ＠スプシマン @hoehoe1234

直接選択法のトランプによるアルゴリズムの確認です。数少ないカードにi,jを表すブロックを置き、１手ずつ書籍のコードを実行していきます。これにより手順が明確に目に見える形で確認できます。わりと楽しいです。 pic.twitter.com/fYdBtEPq44

拡大

ほえほえ＠スプシマン @hoehoe1234

今度は同じくトランプでバブルソートをやってみます。ここでのポイントはiとi+1の位置が常にセットで動くことです。一度数列をスキャンすると一番大きな値が右端に移動します。直接選択法との違いを確認したりしました。 pic.twitter.com/qCwLjNYm9R

拡大

ほえほえ＠スプシマン @hoehoe1234

今度は配列の内容をいつものように板書してみました。どこまでチェックすればよいか？の境界値がこれによりわかります。要素数をnとすると、最後の要素はa[n-1]、ソートでiが移動するのは最後の要素の前まで、すなわちa[n-2]になることを確認したりしました。 pic.twitter.com/L02rGOQOh1

拡大

ほえほえ＠スプシマン @hoehoe1234

バブルソートの板書です。受講生に書いていただきました。図にあるように、常にi番目の要素とiの右側の要素i+1番めを比較、交換すればよいことがわかります。 pic.twitter.com/JcidB6NGQ5

拡大

ほえほえ＠スプシマン @hoehoe1234

少し戻ってホーナの法則をつかったxの累乗の最終案の確認です。100が2^2+2^5+2^6、すなわち2の累乗で表せることを利用します。100=4+32+64となり100が2の累乗の和で表せます。これを利用するとx^100=x^4 * x^32 * x^64という数式が得られます。あとはこれを利用して少ない回数でxの100乗を計算します。 pic.twitter.com/80vqHQyjl0

拡大

ほえほえ＠スプシマン @hoehoe1234

ここで時間切れとなったのでホーナの法則を使った最終的なソースコードの解説は次回となりました。 ソートのアルゴリズムについても、ソースコードを追うだけでなくアルゴリズムを自分のものにするには「自分の言葉」で表せるまで理解する必要があります。参考として

ほえほえ＠スプシマン @hoehoe1234

次のようにまとめてみました。これ以外にもよい表現はあると思います。コードを追った後にまとめ直すことにより理解がふかまります。 直接選択法　直接選択法は、iをベースとして固定し右部分文字列から一番小さい要素(k番目）を見つけ出してその要素をベースであるi番目の要素と交換する方法です。

ほえほえ＠スプシマン @hoehoe1234

これによりi番目までの左部分数列はソート済みとなりますので、iを一つ進めて同じことをn-2（nは要素数、n-1番めは最終要素、n-2は最終要素の一つ前）まで繰り返す手法です。 バブルソート バブルソートはiを固定しないで左から右までサーチしていきます。

ほえほえ＠スプシマン @hoehoe1234

その過程でiとi+1を比較し、i番目の要素がi+1番めのより大きければ交換します。これにより一度のサーチで全体数列中の一番大きな値が右端に追いやられます（泡が浮かぶように隣と比較交換しながら右端に移動します）。

ほえほえ＠スプシマン @hoehoe1234

これを繰り返すことにより右部分数列がソートされた状態になります。また、最後の変更が起こった場所をlcp(last change posishon)とすると、lcpより右の部分数列はすでにソート済みですので、次のサーチでは最後までサーチせずにlcpを右端とすることにより効率化ができます。

ほえほえ＠スプシマン @hoehoe1234

以上のようにまとめることができます。今回のエンジョイCコースの概要は以上です。 次回から新機軸（書籍）が追加されますのでこれまで以上にがんばりますのでよろしくお願いします。　おわり。