3月31日(火)
予定:
英語リーディング(1時間)→完
単語→完了
アルゴリズム:&3、&4 →&3まで完成
pythonサイト:<面向对象高级编程> →未
論理回路:P68ページまで →40ページ(予定)
学校とコンタクトを取る → 進行中。向こうに質問送ったところ
今日一日の感想
仕事に邪魔されず、外出等もなく、時間的に集中できた一日でした。
単語、リーディング、アルゴリズム やりましたが、
全体的に、頭に一杯詰め込まれた感があり、復習、振り返りが必要。
以下、簡単に振り返り(アルゴリズムは文章の最後にする):
1、英語: 間違った問題を振り返りする必要がる。
適宜英語の記事を読んでみてよいかも。
2、朝の時間を有効活用。英語は夜にしても良い。
3、アルゴリズムの計算量の出し方が分からない。(統計の知識がいるっぽい)
明日の予定:
アルゴリズム &4
pythonサイト:<面向对象高级编程>
英語:リスニング、単語
論理回路:P80
学校とコンタクトを取る
2文探索木: 左の子>親、親<右の子
挿入時の動作: 根から辿っていき、適切な場所に見つけたらそこへノードを追加する。
削除時の動作: 根から対象ノードを見つけて、削除する。削除された後、空いた穴には、元々子がなければNULLとする/子が1個のみならその子のNODEを持ってくる/左右両方に子がいれば、右側の最小の子を持ってくる。
プログラム実装時の注意点: 削除関数はNodeとobjectを受取、objectを削除した後の(形整理し直した後の)nodeを返す。また、内部で再帰的に呼び出しはこの性質を利用しする。node.left = delete(node.left,object)のように書く。
平衡木: 要素はすべて葉に格納され、途中ノードは必ず2,3個の子を持つ。
途中ノードには、2個目と3個目の子の子孫の内の最小値を格納する。
追加時: 根から辿って行って、挿入する。挿入後、4つ要素になったら、隣の子と二人で独立して、親の兄弟を新しくできる。
削除時:根から辿って削除する。一人子になったら、隣に3人子いればそこから一人借りて終わる。両隣に二人子しかいなかったら、そこへ移す。ネノードが一人子になったら、根ノードを削除し、その一人子を新しい根にする。
ハッシュ: 衝突が起こりうる。
→チェイン法: 同じハッシュ値を持つ要素をリストにつなげる。バケットに、リストへのポイントを格納する
→開番地法:バケットに要素をそのまま格納する。衝突したら、再ハッシュする。削除したら、Deletedマークを残す。探索でDeletedにあったら、再ハッシュする。追加でDeletedにあったら、そのまま入れる。
集合群: あまり理解できなかった
クイックソート:最初2個の値の内、大きい方の値を境界にして、それ以上とそれより小さい の2グループに分ける。←再帰的呼び出しをする。←くっつける。
配列に適用する方法もある:
・partitionを導入する。partition([],i,j,p)で、対象リスト内で、p値より小さい、大きいに分けて、swapする。
マージソート: 対象列を前半、後半に機械的に分割し、それぞれを再帰呼び出しに渡してソートする。ファイルに対するマージソートはよくわからなかった。