外点の個数(データ構造)

外点

2分探索木に導入される架空の頂点. 元からある頂点を内点,架空の頂点を外点という. 要素は内点にのみ割り当てられる.

外点の個数

内点の個数をn個とすると,外点の個数はn+1個である.

これを数学的帰納法により証明する.

[i]n=1の場合,

外点の個数はn+1より

1+1=2

である. 内点が1個のみであるから,1個のみに対する架空の点は2個である.

従って,n=1の場合成立する.

[ii]n=kの場合成立すると仮定する.

外点の1個を内点に置き換えた時 内点の個数は1個減り, 外点の個数は置き換わった1つ分減り,新たな内点に対する外点が2つ増えるから外点の個数は

(k+1)-1+2=(k+1)+1

この式はn=k+1の場合に成立することを示す.

[i],[ii]より外点の個数がn+1であることが数学的帰納法により示された.

一言

講義でやった内容の復習も兼ねて記事にしていきたいと思います. 間違いがあったら是非教えてください.

Rubyのインストール

経緯

MacBookPro touch bar付きを買った. (大学のプロキシには悩まされたが簡単に設定できるスクリプトを先輩からもらったのでかなり快適になった.) 学祭実行委員会のtwitterアカウトで学祭のことをツイートをリツイートするようにBot化するのが目標.

install

Homebrewはinstall済みの想定.

%brew install rbenv 
%brew install ruby-build

.zshrc に

export PATH="$HOME/.rbenv/bin:$PATH" 
eval "$(rbenv init - zsh)"

を追加

%source ~/dotfiles/.zshrc

設定ファイル読み直し。(dotfiles/ の中に.zshrcを置いてgitで管理している.)

%rbenv install -l

インストール可能なrubyのバージョンを確認する。

%rbenv install 2.3.3

Ruby 2.3.3をインストール

% rbenv versions
* system (set by /Users/kicchii/.rbenv/version)
  2.3.3
% rbenv global 2.3.3
% rbenv rehash

rehash → 選択したrubyやgemのPATHを設定しなおす。

参照 http://blog.tokoyax.com/entry/zsh/command-not-found

一言

もっと勉強しないとですね. 更新頻度が低いしそれだけ勉強してないってことだ.

Sierraでもkarabiner使いたい

はじめに

はじめまして。 きっちーといいます。 某国立大学で情報系の勉強しています。 サークルでRuby on Rails、研究室ではPythonを使います。

勉強したことを残しておこうと思いこのブログを始めました。 特にサークルでのRailsの方を中心にやっていきたいと思っています。 これからサークルに入ってきてRailsを勉強することになる人たちのためにまだRailsの詳しくない状態の気持ちを残しておきたいと思っています。 Pythonの方はまだ触ったこともないので無知を晒すと思いますが温かい目で見守って下さい笑。 Pythonはやり始めたら何か書きます笑。 稀に全然関係無いことも投稿するかもしれません。

短いですがこんな感じです。 よろしくお願いします