二分木の関係性の覚え方
超適当自分流覚え方。(必ずしも正しくはない)
高さ n -> 節の数 2^(n+1)-1
高さに対して倍々に増えて行くので指数関数のグラフを意識すると良い。最後のマイナス１は根の数が１つだけだからとなんとなく覚えておけばなんとかなる。
指数関数 - Wikipedia
節の数 n -> 高さ log(2) n
高さの逆。高さが増えて行くためには節の数は倍々に増えている必要があります。なので、増えていくnを抑えて高さを数えて行く必要があります。対数関数のグラフを思い浮かべましょう。
対数 - Wikipedia
節の数 n -> 枝の数 n-1
節ごとがそれぞれ親に繋がる枝を持っているので、節の数と基本的には同じになるが、根のみ親を持たないためマイナス１をしてます。
クイックソート
クイックソートは対象となる配列を分割していきながら整列を行います。
ポイントとしては、
- 基準をもとに分割をしてくこと
- それが再帰的であること
手順
1. 基準値を決定
2. 基準値より小さな要素と大きな要素をそれぞれ分割する
3. 分割してできた２つの配列に対し1.の操作を配列の長さが１になるまで繰り返す
基本はこの順番な気がしますが、基準値の選び方は様々で、配列の一番右側を基準としたり真ん中を基準としたりするなどがあった気がします。
また、小さな要素と大きな要素の選別も両サイドから探し始めて要素を入れ替えていくパターンと、新たな配列を用意してそこに移していくパターンもあります。前者の方法をする場合、再帰処理の前に基準値を配列の真ん中に持ってくること、再帰の際に配列を参照渡ししその小さい要素の開始点と終了点を引数に渡してあげることで実現します。
正直なところ、ソートをコーディングする際の条件式の書き方によって多少やり方も変わりますが、基本的にやっていることは変わらないと思います。以下、疑似コード。両サイドから入れ替えていくパターンです。
function qsort(Data, left, right) //Dataは参照渡しでleftとrightは整列する配列の両端 int pivot, lp, rp pivot = Data[right] //基準を右端にとる lp = left rp = right while(lpがrpに等しくない) //このwhileで基準より小を左側に基準以上を右に写す while(Data[lp]がpivotより小さい) lp++ endwhile while(lpがrpより小さい & Data[rp-1]がpivot以上) rp-- endwhile if(lpがrpより小さい) Dataのlpとrp-1要素を入れ替え endif endwhile //ここまでで大小が左右に別れる Dataのlpとright要素を入れ替え //基準を真ん中に持ってくる if(lp-1がleftより小さい) //次に整列させる配列の要素が1個なら終了 qsort(Data, left, lp-1) endif if(rp+1がrightより小さい) //次に整列させる配列の要素が1個なら終了 qsort(Data, rp+1, right) endif endfunction
【応用情報】Unicode -> UTF-8 -> 16進数表現の問題
問題
Unicode文字列をUTF-8でエンコードすると、各文字の先頭バイトは２進数表示が0又は11で始まり、それ以降のバイトは10で始まる。16進数表示された次のデータは何文字のUnicode文字列をエンコードしたものか。
E3 83 9F E3 82 B9 E3 83 81 E3 83 AB 32 35 74 68
解き方
変換ツールを使えば一発ですが、それはダメです。まず、文字コードの仕様から見ます。
- Unicode 世界各国の文字を統一して扱うための16bitコード。後に21bitに拡張された。
- UTF-8 Unicodeを8bit単位で符号化するための文字符号化形式。ASCII文字と互換性をもち、ASCIIは0から始まる1byte文字で、それ以外の多バイト文字は、先頭バイト→11から始まる1byte、先頭以外のバイト→10から始まる1byteで符号化する。
ここで重要なのは、UTF-8が8bit文字ではないこと！！！僕は知りませんでした。笑 つまり1byteごとに区切ってちょうどいい大きさにするやつって感じですか。
ASCIIは7bit文字なので、必然的に1byte内に収まるんですね。一方Unicodeは2byte以上必要になるので、先頭バイトとそれ以外のバイトの始まりが分けられているんですかね？（多分）
文字だとわかりにくいので、図を用意。
改めて問題を確認。
問題文の最初の部分はエンコード後の先頭バイトについて。わざわざ書いてくれていました。優しい！
次に問題の文字列を確認。16進数が並んでいますね。これは、UTF-8を２進数→16進数に直した結果でしょうか。直し方の手順としては、
- UTF-8から1byte分持ってくる(これで一文字とは限らない) 11100011
- 4bitごとに分ける 1110 0011
- 16進数に変換する E3
こんな感じです。
手順がわかったところで、次は文字の切れ目の目安である、先頭byteが0又は11の探し方です。
2桁で表されている16進数の左側に先頭byteの情報が反映されるため、ここを確認すれば見つけ出すことができます。
- 先頭が0から始まる4bitは 0000~0111 これを16進数に直すと0~7
- 先頭が11から始まる4bitは 1100~1111 これを16進数に直すとC~F
つまり、2桁の左側が上の数字から始まっていれば、そこは先頭byteであり、文字の始まりであると言えそうです。
(余談ですが、先頭バイト以外は10で始まると言いましたが、これは16進数でいう8~Bにあたり、見事被らないですね)
あとは、問題から上の条件で始まる16進数を見つけ、数えればそれが答えです。
(E3 83 9F) (E3 82 B9) (E3 83 81) (E3 83 AB) (32) (35) (74) (68)
A.8文字
ところでなんて書いてあるのでしょうね。
以上。
