課題4(6/9出題, 6/28締切)

課題

教科書の4.5 Discussion and ExercisesのExercise 4.5, 4.11, 4.12 のうちの1題以上を解きなさい．　
C++言語で回答する時は，回答に利用した環境も書いてください．
Exercise 4.11, 4.12は一から実装するのではなく，配布プログラム ods-cpp.tgz に手を加えて回答することが前提になっています．
Google Colab環境では，report4でExercise 4.11, 4.12 を実行することができます．できたら，[ファイル]->[.ipynbをダウンロード] でNotebook形式のファイルをダウンロードした上で，ipynb の拡張子を持つファイルを提出してください．
関連するファイルをreport4.tgzにまとめておきました．

Exercise 4.5 の 'Illustrate' は図を書くということだが，描画ツールを使って描いても，手描きの図を電子化(カメラで撮る/スキャンする)しても良い．第4章では，skiplistのheight は0始まりになっている．heightが4だということは，L₄にも含まれるということなので，注意が必要になる．

report4.tgzの中に含まれるSkiplistList.hの中からincludeされているex4_11.hの空白部分を埋めてください．

SkiplistList truncate(int i) {
  SkiplistList ret;
  // fill here    
  return ret;

動作チェックをおこなうプログラム check_ex4_11.cppを

g++ --std=c++11 -Wall -O2 -o check_ex4_11 check_ex4_11.cpp

でコンパイルし．

./check_ex4_11

で実行してOKが出ることで，このex4_11.hが正しく動作することを確認できます．fill here を埋めないプログラムを実行すると，

NG
xs=[1, 2, 3, 4, 5]
tuncate(0)
return
expected = [1, 2, 3, 4, 5]
return   = []
after xs = 
expected = []
return   = [1, 2, 3, 4, 5]

のように，間違いを検出してくれます(このチェックプログラムで検出できない間違いもあります)．

void absorb(SkiplistList& l2) {
  // fill here    
}

動作チェックをおこなうプログラム check_ex4_12.cppを

g++ --std=c++11 -Wall -O2 -o check_ex4_12 check_ex4_12.cpp

でコンパイルし．

./check_ex4_12

で実行してOKが出ることで，このex4_12.hが正しく動作することを確認できます．fill here を埋めないプログラムを実行すると，

NG
xs=[1, 2, 3, 4, 5]
absorb([10])
return
expected = []
return   = [10]
after xs = 
expected = [1, 2, 3, 4, 5, 10]
return   = [1, 2, 3, 4, 5]

のように，間違いを検出してくれます(このチェックプログラムで検出できない間違いもあります)．

作成したすべてのプログラムと，各プログラムに関する簡単な説明をまとめたプレインテキスト形式(テキストエディタで編集可能な形式)またはPDF形式のファイルを1つ作成して，ITC-LMSの「課題4(6/9出題, 6/28締切)」(6/9の講義時間中に公開される予定)に提出してください．

締切は，6/28(日) 23:59です．締切を過ぎた場合，2020年7月末までに提出された課題は6割を上限に採点する．

課題だけで物足りない人は，以下のオプション課題にも取り組んでください．