マージソートを理解できるようにわかりやすくまとめる

マージソートの考え方や実際のプログラムまで、理解しやすく、忘れないようにまとめたいと思います。

マージソートの擬似言語で書かれたアルゴリズム

マージソートで擬似言語で書くと以下のようなコードになります。
ALDS1_5_Bを参照しています。

/**
  A:ソート対象の配列
  left:配列の左端のindex,
  mid:配列の中間index
  right:配列の右端index
*/
merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  // 2つの配列を作成する
  create array L[0...n1], R[0...n2]
  // 左側
  for i = 0 to n1-1
    L[i] = A[left + i]
  // 右側
  for i = 0 to n2-1
    R[i] = A[mid + i]

  // 番兵を入れる
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  // 2つの部分配列をマージする①
  for k = left to right-1
    if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

Merge-Sort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right)

マージソートのアルゴリズム

この擬似言語のアルゴリズムからマージソートは以下の手順で実行されます。

1.指定されたn個の要素を含む部分配列を
それぞれn / 2の要素を含む2つの部分配列に分割する(divide)

2.分割した2つの部分配列をマージソートでソートする(solve)

3.ソートした2つの部分配列をマージする

マージソートはソート済みの2つの部分配列を結合するときのアルゴリズムが鍵になっています。

擬似言語のアルゴリズムでは、①の箇所が該当します。
2つの配列LとRは昇順にソートされていることを前提とし、
LとRのすべての要素が昇順となるようにソート済みの数列を格納するAにコピーしています。

2つの部分配列は、昇順にソートされていることが前提と書きましたが、
マージソートでは、要素数1からスタートし、部分配列を昇順に結合していくので、
2つの部分配列はソートされていることになります。

部分配列LとRはソート済みであることから、擬似言語でのアルゴリズムのコードからわかるように、
計算量は、O(n1 + n2)となります。

マージソートの結合する箇所を図解する

マージソートの要となる結合部分のアルゴリズムを図示してみます。
マージのアルゴリズムは、以下のコードでした。

  // 番兵を入れる
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  // 2つの部分配列をマージする①
  for k = left to right-1
    if L[i] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

まず、以下の2つの部分配列L・Rと、結合する整列した配列Aがあるとします。
L:1,6
R:2,3,9
A:***

部分配列のL・Rは要素が2つ以上入っているので、
Aには、すでに整列途中の結果が入っていることになります。

擬似言語のアルゴにあるように、それぞれに番兵(最大の数値今回はSとする)を代入します。

L:1,6,S
R:2,3,9,S

1回目の比較

Lのindex0とRのindex0を比較して、小さい方をA[left]に代入します。

L:1,6,S
R:2,3,9,S

A:1

Lのindex0の値1が挿入されたので、Lのindex対象の変数iを1つ増やします。

2回目の比較

L:1,6,S
R:2,3,9,S

A:1,2

Rの2代入されます。
Rのindex対象の変数jを1つ増やします。

3回目の比較

L:1,6,S
R:2,3,9,S

A:1,2,3

Rの3が代入されます。

4回目の比較

L:1,6,S
R:2,3,9,S

A:1,2,3,6

Lの6が代入されます。
次からLは番兵を指すようになります。

最後の比較

L:1,6,S
R:2,3,9,S

A:1,2,3,6,9

最後の比較になります。
Lは番兵をさすので、Rの9がAに挿入されます。

forループの比較回数は、left to right - 1とleftとrightの合計の要素数になっているため、
ここで比較が終了します。

番兵と比較する要素数で判断することによって、O(n1 + n2)の処理数を実現しています。

mergeSort関数の解説

結合のアルゴリズムがわかったところで、mergeSort関数部分を図解していきます。
mergeSortの擬似言語での関数は以下です。

Merge-Sort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right)

引数Aには、対象となるソートしたい配列を、
leftには、部分配列の先頭を、rightには、末尾+1のindexを指定します。

left + 1 < right
により、要素が1以下の場合は処理しないようにしています。

mid = (left + right)/2; Merge-Sort(A, left, mid)
Merge-Sort(A, mid, right)

探索する範囲を狭めて、再帰処理を行なっています。
最終的には、Merge-Sortに渡す対象のindexが2つの部分配列の要素数がそれぞれ
1になるようにすることで、昇順に整列する箇所が機能するようにしています。

mergeSortの工程を図解する

では最後にmergeSortの工程を図解します。

数列859263714をマージソートにかけています。
黒矢印が分割する工程を、赤矢印がマージする工程を示しています。

mergeSortの計算量を考える

merge関数の処理の計算量は前述したように0(n1 + n2)になります。

上図にあるように、9個の数を1個になるまで、分割しようとすると、
9 → 5 → 3 → 2 → 1
の4回の分割が必要になり、階層は5になります。

このことから、階層は一般に
$log_{2}n$個になります。

階層階ごとに行われる全てのマージの総計算量はO(n)になるので、
マージソートの計算量はO(nlogn)になります。

参考
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
マージソートのwikipedia

再帰関数を理解できるように詳しくまとめる

再帰関数についてまとめたいと思います。

再帰関数とは

関数の中で、その関数自身を呼ぶような関数のことを再帰関数といいます。

再帰関数の例としてよくあげられるのは、階乗するようなケースです。
$3!$などの計算のことです。

$3!$のケースを考えると、
$3! = 3 × 2 × 1$
という計算になりますが、この乗算する処理を自身で実行してしまおう
というのが、再帰関数になります。

階乗処理を例とした再帰関数の実装

階乗処理をベースに再帰関数を書いてみたいと思います。

引数に階乗したい数値を入れ、
その階乗した値を返す関数を再帰関数で考えてみます。

factorial(int n ){
  if(n == 1) return 1;
  return n * factorial(n - 1)
}

再帰関数の処理を図式化する

関数だけだと、処理を想像することが難しいので、
図式化したいと思います。

階乗したい数値を4として、factorial関数に代入する様子をみてみます。

再帰関数1回目の処理

factorialに4を代入します。

return 4 × factorial(4 - 1)

ここで、factorial(4 - 1)として自身を呼び出しています。
return処理は行われず、factorial(4 - 1)関数が先に呼ばれます。

再帰関数2回目の処理

factorial(4 - 1)を呼びます。

return 3 × factorial(3 - 1)

factorial(3 - 1)を呼びします。
まだreturnはしていません。

再帰関数3回目の処理

factorial(3 - 1)を呼びます。

return 2 × factorial(2 - 1)

factorial(2 - 1)を呼び出します。
次から展開が変わります。。。

再帰関数4回目の処理

factorial(2 - 1)を呼び出します。

if(n == 1) return 1;

nが1なので、ようやくここで、1をreturnします。
factorial(2 - 1)を呼び出した、3回目の処理にもどります。

factorial(3 - 1)の処理

factorial(2 - 1)の処理結果として1が返ってきたので、 factorial(2 - 1)の処理を呼び出していた、
factorial(3 - 1)のreturnが以下のように返るようになります。

return 2 × 1

次に、factorial(3 - 1)を呼び出していた、
factorial(4 - 1)のreturn処理が行われることになります。

factorial(4 - 1)の処理

factorial(3 - 1)が2 × 1と返ってきたため、 factorial(4 - 1)のreturn部分の処理が行われます。

return 3 × factorial(3 - 1)

つまり

return 3 × 2 × 1

がfactorial(4 - 1)のreturn値になります。
factorial(4 - 1)を呼んだfactorial(4)のreturn値が返ることになります。

factorial(4)の処理

いよいよ、factorial(4)の処理が終わります。

return 4 × factorial(4 - 1)

つまり

return 4 × 3 × 2 × 1

が、最終的な値として、返ってくることになります。

双方向連結リストc++で動的に実装する

双方向連結リストをc++で実装してみたいと思います。
まず、双方向連結リストとは何かに関してまとめます。

双方向連結リストとは

あるデータを持ったノードがあり、そのノードの前方と後方に別のノードが連結しているリストのことです。
数値をデータとして持つノードの双方向連結リストを図で表すとこんな感じです。

□→ ←□2□→ ←□4□→ ←□

□は、繋いでいるデータのメモリアドレスです。

一番最初のデータと一番最後のデータは、空のデータを表すnilを入れます。
参照しても空ということです。

双方向連結リストをc++で実装する

では、c++で双方向リストを実装してみたいと思います。

まず、ノードとなるデータを構造体で定義します。

struct Node{
    int key;
    Node *next,*prev;
};

データとして、int型を定義し、
自身を二つ定義します。
これに、連結リストとなる次のノードと前のノードを代入して、連結リストが作られていきます。

双方向リストの位置を管理する番兵を導入する

定義したノードを生成して、新しく連結リストを作っていくのに、現在の連結リストの位置を管理する必要があります。 そのために、グローバル変数として、番兵を用意します。

// 番兵をグローバル変数として定義する
Node* nil;

// 番兵を生成する
void init(){
    nil = (Node*)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}

新しくメモリを割り当てる関数mallocを使って、連結リストのノードを作成しています。 mallocで作成したメモリ領域は必ず、free関数で解放する必要があるので、ノードを削除する関数で、
free関数を必ず呼びましょう。

nil->next = nil
nil->prev = nil
によって、番兵の前と次の要素を自身に設定して、巡回するようにしています。

双方向連結リストに新しいノードを挿入する

位置を管理する番兵を定義したところで、新しいノードのを追加する関数を定義します。
insert関数は、連結リストの先頭にキーを持つノードを挿入する関数です。

void insert(int key){
    // 新しくnode用のメモリを作成
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    // 番兵の次に要素を追加
    node->next = nil->next;
    nil->next->prev = node;
    nil->next = node;
    node->prev = nil;
}

ここがわかりにくいと思うので、挿入していく様子を図解してみます。

ノードが挿入される要素を図解する

1.まず新しくkey3を持つノードを作成します。

□空の先頭□ □3□

2.続いて番兵の設定をして、連結リストが管理できるようにします。

番兵はinit関数により、自身を巡回させているので、下図のようになります。

       prev       next
番兵 ← □番兵□ → 番兵

続いて、挿入していく様子を図にします。

まず、新しく作成したnodeのnextに番兵を指定します。
nil->nextはnilを指していますね。

node->next = nil->next;

□3□ → □番兵□

続いて、nil->next->prev = node
ですが、最初に要素を挿入するときには、nil->next->prevはnilを指しています。
なので、nilのprevにnodeを挿入していることになります。

nil->next->prev = node

□3□ → □番兵□
　   ←

続いて、番兵のnextに作成したノードを設定します。 図では、番兵が2つになっていますが、実際はもちろん一つで、表現するためにそうしています。

nil->next = node

□番兵□ → □3□ → □番兵□
　　　　　　    ← 

最後に、ノードのprevに番兵を設定します。

node->prev = nil;

□番兵□ → □3□ → □番兵□
　　　   ←　　 ←

これで、一回目の挿入が終わりました。

2回目の双方向連結リストへの挿入

では、次にkey5を持つノードを新しく挿入するケースを確認したいと思います。

node->next = nil->next
現在nilのnextには、先ほど作成した3を持つノードが指定されているので、node->nextは
3のノードを指すことになります。

node->next = nil->next


□5□ → □3□ → □番兵□
　　　　 　←

nil->next->prev = node
nil->nextには、3が入っています。 ということは、nil->next->prevは3のprevを指しますね。
3のprevに5のノードを代入します。

nil->next->prev = node;
□5□ → □3□ → □番兵□
　　←　 　←

nil->next = node
nil->nextに5のノードを設定します。

nil->next = node
□番兵□ → □5□ → □3□ → □番兵□
　　　              ←　 　←

node->prev = nil 現在のノードのprevに番兵を指すようにして、巡回させるようにします。

node->prev = nil;
□番兵□ → □5□ → □3□ → □番兵□
　　　   ←       ←　 　←

こんな感じで先頭に挿入することができます。
要素の先頭と最後方には番兵が入ることになり、双方向連結リストの挿入を容易にしてくれます。

双方向連結リストをキーで探索する

リストをキーで検索してみます。

insert関数で図解したように、番兵のnextに先頭の要素が、
最後方のnextに番兵が入っているので、
キーを探すには、番兵のnextから探索し、番兵が見つかれば、
キーをもつ要素が見つからなかったという判断ができそうです。

双方向連結リストをキーで探索するプログラム

それでは、双方向連結リストを探索するプログラムを見ていきます。

Node* searchList(int key){
    // 番兵の先頭から探していく
    Node* cur = nil->next;
    // 番兵でなく、キーが同じでなければ、次の要素を探索する
    while(cur != nil && cur->key != key){
        cur = cur->next;
    }
    // 見つからければ、番兵が返ることになる。
    return cur;
}

双方向連結リストのノードを削除する

続いて、ノードを削除する方法を見ていきましょう。
引数として与えられたノードを削除するプログラムを書きます。

双方向連結リストのノードを削除するプログラム

void deleteNode(Node* n){
    // 番兵のケースは何もしない
    if(n == nil) return;
    n->prev->next = n->next;
    n->next->prev = n->prev;
    free(n);
}

プログラムの様子がイメージしにくい部分があると思うので、
先ほどinsertした図を使用し、プログラムの遷移を表現してみます。

□番兵□ → □5□ → □3□ → □番兵□
　　　   ←       ←　 　←

この連結リストから5のノードを削除するケースを考えてみます。

n->prev->next = n->next
自身のprevの要素のnextが指す位置を自身の次の要素に入れ替えます。
つまり、番兵のnextが3を指すようになります。

n->prev->next = n->next

□番兵□    □5□ → □3□ → □番兵□
　　　   ←       ←　 　←
　　　　　 □番兵□ →　

n->next->prev = n->prev
自身の次の要素のprevが指す位置を自身の前の要素に入れ替えます。 つまり、3ノードのprevが番兵を指すようになります。

n->prev->next = n->next

□番兵□ → □3□ → □番兵□ □5□ 
　　　   ←       ←　 　　

free(n); 最後にどこにも連結しなくなった、ノード5をfree関数によって、削除します。

これで、5を削除しても連結リストが保持されていることが確認できました。

双方向連結リストの先頭のノードを削除する

番兵のnextが先頭のノードを指しているので、deleteNode関数に
nil->nextを渡せばokです。

void deleteFirst(){
    deleteNode(nil->next);
}

双方向連結リストの最後方のノードを削除する

番兵のprevは後方のノードを指しているので、deleteNode関数に
nil->prevを渡せばokです。

void deleteLast(){
    deleteNode(nil->prev);
}

双方向連結リストの特定のキーをもつノードを削除する

先ほど特定キーをもつノードを探し、返す関数を書いたので、その関数を使います。

void deleteKey(int key){
    deleteNode(searchList(key));
}

これで、双方向リストのプログラムが完成しました。

双方向連結リストの計算量を考える

双方向連結リストの計算量を考えてみます。

双方向連結リストの挿入する計算量

プログラムで示した通り、番兵のnextのpointerを繋ぎ変えるだけなので、
O(1)になります。

双方向連結リストから特定の要素を探索する計算量

双方向位連結リストは直列で結ばれているので、
先頭から末端のNまで、探索する必要があります。
なので、O(N)になります。

双方向連結リストから特定の要素を削除する計算量

先頭・最高峰の要素を削除するには、番兵があるので、O(1)の計算量で、
それ以外は、O(N)になります。

シェルソートをわかりやすくまとめる

シェルソートについて、わかりやすくまとめたいと思います。

シェルソートとは

一定間隔(g)ごとに挿入ソートを行うことをシェルソートといいます。 最後に必ず、通常の挿入ソートを行いますが、
この時に、あらかた整列されていることが期待されます。

この一定間隔gの決め方ですが

g = 1,4,13,40,121・・・

つまりは、
$g_{n+1} = 3g_{n} + 1$の数列を用いると、
計算量が$O(N^{1.25})$になるようです。

また、上記のgを適応すると、2のべき乗の値($2^p = 1,2,4,...$)の場合は、ソート対象となる要素が少なくなるため、
効率化は見込めないようです。

シェルソートの工程を図解する

実際にシェルソートが行われる工程を図解してみます。

数列{4,8,9,1,10,6,2,5,3,7}に対して、 g{4,3,1}として、シェルソートをかけてみます。

ここで、選択対象数字を赤で、整列済みの数字を緑で表現したいと思います。

1.間隔を4に空けて挿入ソートをかけます。

4,8,9,1,10,6,2,5,3,7
3,8,9,1,4,6,2,5,10,7

3,8,9,1,4,6,2,5,10,7
3,6,9,1,4,7,2,5,10,8

3,6,9,1,4,7,2,5,10,8
3,6,2,1,4,7,9,5,10,8

3,6,2,1,4,7,9,5,10,8
3,6,2,1,4,7,9,5,10,8

2.間隔を3に空けて挿入ソートをかけます。

3,6,2,1,4,7,9,5,10,8
1,6,2,3,4,7,8,5,10,9

1,6,2,3,4,7,8,5,10,9
1,4,2,3,5,7,8,6,10,9

1,4,2,3,5,7,8,6,10,9
1,4,2,3,5,7,8,6,10,9

3.最後に間隔1(通常)に空けて挿入ソートをかけます。

1,4,2,3,5,7,8,6,10,9
1,2,3,4,5,6,7,8,9,10

安定ソートとはどういう概念なのか

安定ソートに関して、まとめます。

安定ソートとそうでないソートの例

wikipediaの例を参考にして、まとめます。
学生番号とテストの合計点が書かれたデータがあるとします。

学生番号	テスト合計点
1	419
2	366
3	402
4	453
5	419
6	402

このデータは、学生番号順に並んでいます。
これをテスト合計点順にバブルソートと選択ソートを使って並び替えてみたいと思います。

テスト合計点順にバブルソートで並び替えた場合

バブルソートで並び替えた場合以下のようになります。 計算過程は省略します。

学生番号	テスト合計点
2	366
3	402
6	402
1	419
5	419
4	453

同じ合計点の例に着目すると、学生番号順にならんでいることがわかります。
この性質のことを安定ソートといいます。
バブルソートは同じ点数の際は入れ替えないため、学生番号の順序も変わらないんですね。

テスト合計点順に選択ソートで並び替えた場合

テスト合計順に選択ソートを使って、並び替えてみたいと思います。

1.まずデータの中から最小得点のデータを探し出します。

学生番号2、点数366が最小なので、左端のデータと交換します。

　　　　

学生番号	テスト合計点
2	366
1	419
3	402
4	453
5	419
6	402

2.
一番目が決まったので、2番目から最小値を探索していきます。
最小値は402学生番号は3のデータになります。

　　　　

学生番号	テスト合計点
2	366
3	402
1	419
4	453
5	419
6	402

3.
3番目から最小値を探します。
最小値は402学生番号は6のデータになります。

　　　　

学生番号	テスト合計点
2	366
3	402
6	402
4	453
5	419
1	419

この時点で、419点において、学生番号が入れ替わってしまいました。

計算過程は省略しますが、学生番号が入れ替わったまま、得点順に並び替えられるのは、
選択ソートの性質上明らかですね。

このように元の順序が変わってしまうソートを不安定ソートといいます。

選択ソートについて、わかりやすくまとめる

選択ソートアルゴリズムについて、わかりやすくまとめたいと思います。

選択ソートは、数列の中から最大または最小の数値を探しだして、その数値と左端の数値を交換することで、 ソートしていくアルゴリズムです。

では、例題で確認してみます。

選択ソートの例題

以下の数列を選択ソートを使ってを昇順に並べて変えてみたいと思います。
昇順に並び替えるので、最小値を選択して数列の左端から並び替えることにします。

5,4,8,7,9

また、対象となっている文字を赤で、ソート済みの数値を緑で表示して、わかりやすくしてみます。

一回目の選択

数列の左端から右端まで最小の値を探していきます。

5,4,8,7,9

左端の値5を最小の値として保存します。
次に右を探索していき、5よりも最小の値があれば、最小の値を更新します。

5,4,8,7,9

5 > 4なので、最小の値が4に変わりました。
次に、8,7,9をチェックしていきますが、最小値は4のままなので、
4と5を交換します。

4,5,8,7,9

これで、最小値がきまり、左端の値が決定しました。
次に、2番目の値つまり5からまた、最小値を探して交換を繰り返していきます。

これが選択ソートになります。

選択ソートの計算量

データの総数をNとすると、
未ソート部分の最小値を探し出すのに、N - 1回、N - 2回, N - 3回、...、1の比較演算を行います。

よって、合計の比較演算回数は、常に(N^2 - N) / 2になるので、 N^2に比例するため、O(N^2)のアルゴリズムになります。

c++でのプログミング問題の数値入力受付方法まとめ

プログラムの問題を解くときに最初に条件の出力を受け取りますが、
すぐ忘れるので、その受付方法をまとめたいと思います。

文字列の間に空白があり、それを連続して変数に受け取る方法

例として、

0 4
1 0
1 1

のように文字列・空白・文字列のケースでは、cinを使って次のように受け取ることができます。

int num1;
int num2;
cin >> num1 >> num2

上記のように入力ケースが決まっている場合はいいですが、

0 4
1 0
2
0 2

のようなケースだと、num2に改行後の数値である0が入ってしまうので、
別途対応が必要です。

cin・coutは遅い

cin・coutはprintfやscanfなどに比べて処理が遅いです。
その場合は、ios::sync_with_stdio(false) をcin・courの前に入れると多少早くなります。

コイン問題を動的計画法とC++で解く

AIZU_ONLINE_JUDGEのDPL_1_Aの問題を使用して、コイン問題を解きます。
コイン問題を以下に引用します。

問題

額面がc1, c2,..., cm　円の　m　種類のコインを使って、
n 円を支払うときの、コインの最小の枚数を求めて下さい。
各額面のコインは何度でも使用することができます。

入力

n m
C1C2・・・Cm

１行目に整数 n と整数 m が１つの空白区切りで１行に与えられます。
２行目に各コインの額面が１つの空白区切りで１行に与えられます。

出力

コインの最小枚数を1行に出力してください

制約

1 ≤ n ≤ 50,000
1 ≤ m ≤ 20
1 ≤ 額面 ≤ 10,000
額面はすべて異なり、必ず1を含む。

入力・出力例

15 6
1 2 7 8 12

2

解法

使用できるコインの額面が決まって入れば、額面が大きいものから引いていけば、
最小枚数を求めることができますが、今回の出力例でその方法を使用すると...

12 2 1
3

3となってしまい7,8を選んだ場合の最小値2となりません。
なので、貪欲法は使えません。

ここでは、以下のような配列の入れ物を定義し、
最小枚数を求めます

coin[m] : coin[i]をi番目のコインの額面とする配列
T[m][n + 1] : T[i][j]をi番目までのコインを使ってj円支払う時のコインの最小枚数とする2次元配列

コインの枚数をi,各iにおける支払う金額jを増やしていき、T[i][j]を更新していきます。
T[i][j]は、i番目のコインを使う場合と使わない場合の枚数を比べ、小さい方を選べばよいので、
次のような漸化式で求めることができます。

T[i][j] = min(T[i - 1][j],T[i][j - C[i]] + 1)

i枚目のコインを使わない場合は、ここまで計算したj円を払う最適解T[i - 1][j]となり、
使った場合は、現在の金額jからC[i]を引いた金額を払う最適解に1枚足した値になります。

配列の具体例

例題のように、支払う金額を15とし、コインの額面を1 2 7 8 12として
coin[m]とT[m][n + 1]の中身を見てみましょう

coin

1
2
7
8
12

T

0	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8
0	1	1	2	2	3	3	1	2	2	3	3	4	4	2	3
0	1	1	2	2	3	3	1	1	2	2	3	3	4	2	2
0	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2

例として、3枚目のコイン(額面8indexは０から)までのコインを使って15円を払う最適解は、
min(T[2][15],T[3][15-8] + 1)より2枚になります。
これは、先に述べたように3枚目のコインまでを使って7円払う最適解に1足したものです。

先の表からわかるように、コインの額面ごとに最適枚数を記録しておく必要はないので、
j円を支払うときのコインの最小枚数は1次元配列の要素T[j]として、次のように求めることができます。

T[j] = min[T[j],T[j - C[i]] + 1)

以上を踏まえて、c++を言語としてプログラムをみていきましょう

#include <iostream>
#include <algorithm>

using namespace std;

#define M_MAX 20
#define N_MAX 50000
#define INFTY 1 << 29

int main(){
    int n,m;
    int coin[21];
    int T[N_MAX + 1];
    
    cin >> n >> m;
    // コインに額面を代入する
    for(int i = 1;i <= m;++i){
        cin >> coin[i];
    }
    
    // 最大値で初期化
    for(int i = 0;i < N_MAX;++i){
        T[i] = INFTY;
    }
    T[0] = 0;
    for(int i = 1;i <= m;++i){
        for(int j = 0;j + coin[i] <= n;++j){
            T[j + coin[i]] = min(T[j + coin[i]],T[j] + 1);
        }
    }
    cout << T[n] << endl;
    return 0;
}

参考

べき乗の計算回数を少なくする繰り返し自乗法

べき乗の計算回数を少なくする方法をAIZU_ONLINE_JUDGEのNTL_1_B:Powerを用いて求めたいと思います。

問題

2つの整数m,nについて、m^nを1000000007で割った余りを求めてください。

単純に計算すると、時間がオーバーしてしまうので、計算方法を工夫する必要があります。
計算方法は

$x^n = (x^2)^\frac{n}{2}$

であることを利用します。

べき乗を計算する関数をpowとして、以下のように再帰関数として定義することで
計算回数を減らします。

pow(x,n) = 1(nが0の時)
pow(x,n) = $pow(x^2,n ÷ 2)$(nが偶数の時)
pow(x,n) = $pow(x^2,n ÷ 2) × x$(nが奇数の時)

例として、この関数を$2^{11}$でトレースしてみます。

$2^{11} = (2 × 2)^5 × 2$(nが奇数のケース)

$4^5 = (4 × 4)^2 × 4$(nが奇数のケース)

$16^2 = (16 * 16)^1$(nが偶数のケース)

このように計算回数を3回に減らすことができました。

Order記法

繰り返し自乗法は、再帰関数の引数が半分になっていくので、
O(logn)のアルゴリズムになります。

以上を踏まえての全体のプログラムです。

#include <iostream>
#include <cmath>

using namespace std;

long pow(long x,long n,long M){
    long res = 1;
    if(n > 0){
        res = pow(x,n / 2,M);
        if(n % 2 == 0){
            res = (res * res) % M;
        }else{
            res = (((res * res) % M) * x) % M;
        }
    }
    return res;
}

int main(){
    int m,n;
    cin >> m >> n;
    
    cout << pow(m,n,1000000007) << endl;
    return 0;
}

単一始点最短経路をダイクストラ法の隣接行列で求める

単一始点最短経路の問題をダイクストラ法と隣接行列を使って解きたいと思います。
問題はALDS1_12_Bを使います。

ダイクストラ法とは

ダイクストラ法は以下のように表される。

前提として、グラフG = (V,E)の頂点全体の集合をV、始点をs、
最短経路木に含まれる頂点の集合をSとします。

各計算のステップで、最短経路木の辺と頂点を選びSへ追加していきます。

また、各頂点iについて、S内の頂点のみを経由したsからiへの最短経路のコストをd[i]とします。

ダイクストラ法のロジック

1.初期化処理

最短経路木に含まれる頂点の集合をSを以下のように初期化します。

始点sに対して最短経路のコストを示すd[s] = 0を代入し、
始点s以外の頂点の全体集合Vに属する全ての頂点iに対してd[i] = 最大値
を代入します。

2.以下の処理をS = Vになるまで(始点sから各々の頂点の最短経路がもとまるまで)続けます。

2.1
V - Sの中から、d[u]が最小である頂点uを選択(最短経路と決定している頂点を除く)します。

2.2
頂点uをSに追加すると同時に、uに隣接しかつV - Sに属する全ての頂点vに対する
値を以下のように更新します。

if d[u] + w(u,v)(実際にかかる移動コスト) < d[v]
　　 d[v] = d[u] + w(u,v)

2.の各計算ステップ直後に,
u[v]には、sからSの頂点のみを経由したvまでの最短コストが記録されていることになります。
つまり1,2の処理が全て終了すると、u[v]に,sからvまでの最短コストが記録されます。

ダイクストラ法の図解

プロセスがわかりやすいように、ダイクストラ法を図解してみます。

下図のようなグラフがあり、始点をAをとします。 Aから各々の頂点への最短経路をダイクストラで求めてみます。

まず、始点Aを0で初期化し、各々への頂点に探索が完了していないことを示すために最大値を代入(変数d[]が対象となる)します。

出典:MIT open course ware

ここから、2.のプロセスに入ります。
最短経路木を示す頂点の集合をSとして、Sを以下のように表します。

S = {} {A B C D E }(Sから各頂点の最短経路の重さを示します。)

step1

まず、始点(s)である頂点AをSに追加します。

S = {A} {0 ∞ ∞ ∞ ∞ }

続いて、頂点Aに辺があり、最短経路未決定の頂点の最短経路を更新します。

最短経路か判定する式は、

if d[u] + w(u,v) < d[v]
　　 d[v] = d[u] + w(u,v)

なので、Aに隣接する頂点B,Cは頂点uが始点で重みが0なので、 辺への重みのみが加算され、以下のようになります。

S = {A} {0 10 3 ∞ ∞ }

step2

また、2.1のプロセスに戻ります。
2.1:V - Sの中から、d[u]が最小である頂点uを選択します。

つまり、最短距離未決定の最小頂点C(重み3)を選ぶことになりますが、
なぜ、最小コストの頂点を選んだ時点で、その地点が最短経路になるのかを、
図で考えてみます。

なぜ、最小コストの頂点が最短経路になるのか

下図のように始点から辺が3つ伸びているグラフがあるとします。
グラフより、各々の3つの頂点からその3つの頂点への辺があるとしても、
sから各々の頂点への3つの辺の中に必ず最短となる経路があることがわかります。

これは、辺が2つでも4つでも同じことです。

step2に戻ります。
Sに最短経路である頂点Cを追加します。

S = {A C} {0 10 3 ∞ ∞ }

続いて、Cにつながる頂点への最短経路更新プロセスに入り、
図を参考に以下のように更新します。

S = {A C} {0 7 3 11 5 }

step3

プロセス1に戻って、探索を開始する頂点を決定します。
最短点であるE(5)が選ばれるので、EをSに追加します。

S = {A C E} {0 7 3 11 5 }

プロセス2に移り、頂点Eにつながる頂点の最短点の更新を行います。

更新する頂点はないので、結果は前と変わりません。

S = {A C E} {0 7 3 11 5 }

step4

プロセス1に戻って、探索を開始する頂点を決定します。
最短点であるB(7)が選ばれるので、BをSに追加します。

S = {A C E B} {0 7 3 11 5 }

プロセス2に移り、頂点Bにつながる頂点の最短点の更新を行います。 頂点Dへの最短経路が9に変わります。

S = {A C E B} {0 7 3 9 5 }

step5

プロセス1に戻って、探索を開始する頂点を決定します。
ここで、全ての最短経路がもとまったので、処理を終了します。

始点sから頂点uへの最短経路はd[u]に入っていることになります。

隣接行列を用いたダイクストラ法

上記をふまえて以下のように実装します。
上記の対象の処理には番号を振っています。

#define MAX 100
#define INFTY 1<<22
// 未訪問の頂点を示す
#define WHITE 0
// 訪問済の頂点を示す
#define GRAY 1
// 未探索の頂点d[u]にはINFTYが入っている
#define BLACK 2
// 隣接行列頂点から頂点への辺の重みが入っている
// 例:gMatrix[0][1] 頂点0から1への重み INFTYの場合辺がないことを示す
int gMatrix[MAX][MAX];

void dijkstra(int n){
    // 最小の重みを記録する
    int minV;
    // u[v]に始点sからvまでの最短コストを保存する
    int u[MAX];
    // 訪問状態を記録
    int color[MAX];
    // 1.初期化
    for(int i = 0;i < n;++i){
        u[i] = INFTY;
        color[i] = WHITE;
    }
    // 0を始点とする
    u[0] = 0;
    color[0] = GRAY;
    
    while(1){
        minV = INFTY;
        // uは探索対象となる頂点を示す
        int u = -1;
        // 2.1 d[u]が最小である頂点を決定する
        for(int i = 0;i < n;++i){
            // 最短経路決定ずみの頂点は含めない
            if(minV > weight[i] && color[i] != BLACK){
                u = i;
                minV = weight[i];
            }
        }
        if(u == -1)break;
        // 選んだ頂点は最短経路決定利用はダイクストラロジック解説にて
        color[u] = BLACK;
        
        for(int v = 0;v < n;++v){
            // 辺が存在し、最短経路決定済頂点以外の経路が対象になる。
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                // 2.2最短コストを更新する
                // この処理の終了後weight[v]sからS内の頂点のみを経由したvまでの最短コストが記録される
                if(weight[v] > weight[u] + gMatrix[u][v]){
                    weight[v] = weight[u] + gMatrix[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
    // 出力
    for(int i = 0;i < n;++i){
        cout << i << " " << ( weight[i] == INFTY ? -1 : weight[i] ) << endl;
    }
}

プリム法と同様wikiに図解されているかなと思ったんですが、
残念ながらのっていませんでいした。
その代わりにアニメーション図がありました、全体の整理でないんでわかりにくい気がしますが。

それでは、ALDS1_12_Bの問題をふまえての全体のプログラムです。

#include <iostream>
using namespace std;
#define MAX 100
#define INFTY 1<<22
#define WHITE 0
#define GRAY 1
#define BLACK 2

int gMatrix[MAX][MAX];

void dijkstra(int n){
    // 最小の重みを記録する
    int minV;
    // weight[v]に始点sからvまでの最短コストを保存する
    int weight[MAX];
    // 訪問状態を記録
    int color[MAX];
    // 1.初期化
    for(int i = 0;i < n;++i){
        weight[i] = INFTY;
        color[i] = WHITE;
    }
    // 始点
    weight[0] = 0;
    color[0] = GRAY;
    
    while(1){
        minV = INFTY;
        // 頂点を示す
        int u = -1;
        // 2.1weight[u]が最小である頂点を決定する
        for(int i = 0;i < n;++i){
            if(minV > weight[i] && color[i] != BLACK){
                u = i;
                minV = weight[i];
            }
        }
        if(u == -1)break;
        color[u] = BLACK;
        
        for(int v = 0;v < n;++v){
            // 辺が存在する
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                // 2.2最短コストを更新する
                // この処理の終了後weight[v]sからS内の頂点のみを経由したvまでの最短コストが記録される
                if(weight[v] > weight[u] + gMatrix[u][v]){
                    weight[v] = weight[u] + gMatrix[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
    // 出力
    for(int i = 0;i < n;++i){
        cout << i << " " << ( weight[i] == INFTY ? -1 : weight[i] ) << endl;
    }
}

int main(){
    int n;
    cin >> n;
    
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            gMatrix[i][j] = INFTY;
        }
    }
    
    int k,c,u,v;
    for(int i = 0;i < n;++i){
        cin >> u >> k;
        for(int j = 0;j < k;++j){
            cin >> v >> c;
            gMatrix[u][v] = c;
        }
    }
    dijkstra(n);
    return 0;
}

最終更新:2020/1/29

最小全域木問題をプリムのアルゴリズムと隣接行列で解く

最小全域木問題をプリムのアルゴリズムと隣接行列を使って解きたいとおもいます。 問題はALDS_1_12_A:Minimum Spanning Treeを参照してください。

プリム法

プリムのアルゴリズムを使って、最小全域木(MST)を求めるには、以下の通りに行います。

グラフG = (V,E)の頂点全体の集合をV,MSTに属する頂点の集合をTとする
1.Gから任意の頂点rを選らんで、それをMSTのルートとしてTに追加する。
2.以下の処理をT=Vになるまで繰り返す

Tに属する頂点とV-Tに属する頂点をつなぐ辺の中で、重みが最小のものである辺(p(u),u)を選び、
それをMSTの辺とし、uをTに追加する

上を実行する過程がプリム法のwikipediaの図に詳しくまとめられていたので、そちらを見るとわかりやすいと思います。

ここで、最小の重みの辺を保持するために、以下の変数を用います。
ここで、頂点の数n = |V|とします。

gColor[n] : color[v]にvへの訪問状態を色で記録します。
WHITE:未訪問,GRAY:訪問(未確定),BLACK(最小値決定済み)

gMatrix[n][n] : gMatrix[u][v]にuからvへの辺の重みを記録した隣接行列

weight[n] : weight[v]にTに属する頂点とV-Tに属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する

parent[n] : parent[v]にMSTにおける頂点vの親を記録する

プリムのアルゴリズムのコード

では、コードを見ていきます。
実施していく過程はwikiの図を見るとわかりやすいと思います。

#define MAX 100
#define INFTY 1 << 21
// 未訪問状態
#define WHITE 0
#define GRAY 1
#define BLACK 2

// 隣接行列
int gMatrix[MAX][MAX];

int prim(int n){
    // 頂点
    int u;
    // 最小の重み
    int minV;
    // Tに属する頂点と(V - T)に属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する
    int weight[MAX];
    // MSTにおける頂点vの親を記録する
    int parent[MAX];
    // 訪問状態を記録する
    int color[MAX];
    // 初期化
    for(int i = 0;i < n;++i){
        weight[i] = INFTY;
        parent[i] = -1;
        color[i] = WHITE;
    }
    // 初回探索地点をindex0にする
    weight[0] = 0;
    
    while(1){
        minV = INFTY;
        u = -1;
        // 隣接する地点で
        for(int i = 0;i < n;++i){
            if(minV > weight[i] && color[i] != BLACK){
                // 最小の重みを記録する
                u = i;
                minV = weight[i];
            }
        }
        // 全て訪問した
        if(u == -1)break;
        // 訪問済み
        color[u] = BLACK;
        for(int v = 0;v < n;++v){
            // uとvの間に辺が存在する
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                if(weight[v] > gMatrix[u][v]){
                    // 隣接する辺に重みを割り当てる
                    weight[v] = gMatrix[u][v];
                    parent[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for(int i = 0;i < n;++i){
        if(parent[i] != -1) sum += gMatrix[i][parent[i]];
    }
    
    return sum;
}

O記法を考える

隣接行列を使ったプリムのアルゴリズムは
重みが最小である頂点を探すために、グラフの頂点数調べる必要があるので、
O(|V|^2)のアルゴリズムになります。

では、ALDS_1_12_A:Minimum Spanning Tree
を例題とした全体のコードです。

#include 
using namespace std;

#define MAX 100
#define INFTY 1 << 21
// 未訪問状態
#define WHITE 0
#define GRAY 1
#define BLACK 2

// 隣接行列
int gMatrix[MAX][MAX];

int prim(int n){
    // 頂点
    int u;
    // 最小の重み
    int minV;
    // Tに属する頂点と(V - T)に属する頂点をつなぐ辺の中で、重みが最小の辺の重みを記録する
    int weight[MAX];
    // MSTにおける頂点vの親を記録する
    int parent[MAX];
    // 訪問状態を記録する
    int color[MAX];
    // 初期化
    for(int i = 0;i < n;++i){
        weight[i] = INFTY;
        parent[i] = -1;
        color[i] = WHITE;
    }
    // 初回探索地点をindex0にする
    weight[0] = 0;
    
    while(1){
        minV = INFTY;
        u = -1;
        // 隣接する地点で
        for(int i = 0;i < n;++i){
            if(minV > weight[i] && color[i] != BLACK){
                // 最小の重みを記録する
                u = i;
                minV = weight[i];
            }
        }
        // 全て訪問した
        if(u == -1)break;
        // 訪問済み
        color[u] = BLACK;
        for(int v = 0;v < n;++v){
            // uとvの間に辺が存在する
            if(color[v] != BLACK && gMatrix[u][v] != INFTY){
                if(weight[v] > gMatrix[u][v]){
                    // 隣接する辺に重みを割り当てる
                    weight[v] = gMatrix[u][v];
                    parent[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    int sum = 0;
    for(int i = 0;i < n;++i){
        if(parent[i] != -1) sum += gMatrix[i][parent[i]];
    }
    
    return sum;
}

int main(){
    int n;
    cin >> n;
    
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            int edge;
            cin >> edge;
            gMatrix[i][j] = (edge == -1) ? INFTY : edge;
        }
    }
    
    cout << prim(n) << endl;
    return 0;
}

参考

全域木・最小全域木とは

全域木(Spanning tree)とは

グラフG = (V,E)の全域木G = (V',E')とは、
グラフの全ての頂点Vを含む部分グラフであり(V = V')、木である限りできるだけ多くの辺を持つものをいう。 グラフの全域木は、深さ優先探索や幅優先探索で求めることができますが、求める全域木は一つになるとは 限らず、探索方法により変化します。

最小全域木(Minimum Spanning Tree)とは

グラフの全域木の中で辺の重みの総和が最小のもののこと

参考

グラフの連結成分をALDS1_11_D:Connected Componentsを利用してc++で学ぶ

グラフの連結成分に関してALDS1_11_D:Connected Componentsを参考にして学びます。

問題文

連結成分分解
SNS の友達関係を入力し、
双方向の友達リンクを経由してある人からある人へたどりつけるかどうかを判定するプログラムを作成してください。

入力

１行目にSNS のユーザ数を表す整数 nn と友達関係の数 mm が空白区切りで与えられます。
SNS の各ユーザには 0 から n－1 までのID が割り当てられています。

続く mm 行に１つの友達関係が各行に与えられます。
１つの友達関係は空白で区切られた２つの整数 ss、tt で与えられ、ss と tt が友達であることを示します。

続く１行に、質問の数 qq が与えられます。続くqq 行に質問が与えられます。
各質問は空白で区切られた２つの整数 ss、tt で与えられ、「ss から tt へたどり着けますか？」という質問を意味します。

出力

各質問に対して ss から tt にたどり着ける場合は yes と、たどり着けない場合は no と１行に出力してください。

入力例

10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

出力例

yes
yes
no

同じグループに属するか判定する処理

色を振り分けることにより同じグループに属するかどうかを判定します。

void assignColor(int number){
    int id = 1;
    for(int i = 0;i < number;++i){
        color[i] = NIL;
    }
    for(int i = 0;i < number;++i){
        if(color[i] == NIL)dfs(i,id++);
    }
}

続いて深さ優先探索にて、自身の友達に対し色を割り当てます。
これを元にして、探索を行います。

void dfs(int r,int c){
    stack<int>s;
    // 自身を入れる
    s.push(r);
    // colorに自信のidを入れる
    color[r] = c;
    while(!s.empty()){
        // 自身
        int u = s.top();
        s.pop();
        // 自分の友達に色を割り当てる
        for(int i = 0;i < gGraph[u].size();++i){
            int v = gGraph[u][i];
            if(color[v] == NIL){
                color[v] = c;
                s.push(v);
            }
        }
    }
}

では、 c++の解答例です。

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

#define MAX 1000000
#define NIL -1

vector<int>gGraph[MAX];
int color[MAX];

void dfs(int r,int c){
    stack<int>s;
    // 自身を入れる
    s.push(r);
    // colorに自信のidを入れる
    color[r] = c;
    while(!s.empty()){
        // 自身
        int u = s.top();
        s.pop();
        // 自分の友達に色を割り当てる
        for(int i = 0;i < gGraph[u].size();++i){
            int v = gGraph[u][i];
            if(color[v] == NIL){
                color[v] = c;
                s.push(v);
            }
        }
    }
}

void assignColor(int number){
    int id = 1;
    for(int i = 0;i < number;++i){
        color[i] = NIL;
    }
    // 同じグループに属するかの色を割り当てる
    for(int i = 0;i < number;++i){
        if(color[i] == NIL)dfs(i,id++);
    }
}

int main(){
    int s,t,m,q,n;
    
    cin >> n >> m;
    
    // 友達関係数
    for(int i = 0;i < m;++i){
        cin >> s >> t;
        // 各々のインデックスごとに友達を加算する
        gGraph[s].push_back(t);
        gGraph[t].push_back(s);
    }
    
    assignColor(n);
    
    cin >> q;
    
    for(int i = 0;i < q;++i){
        cin >> s >> t;
        if(color[s] == color[t]){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }
    return 0;
}

参考資料 https://book.mynavi.jp/ec/products/detail/id=35408

メモ化再帰方法によるフィボナッチ数列

メモ化再帰方法によるフィボナッチ数列をALDS_1_10_A:BibonacciNumberを例題に学びます

メモ化再帰方法とは

複雑な計算処理の結果を保存しておき、再度その計算が必要な際にその値を使うことで
処理の負担を減らすことです。

問題からフィボナッチ数列の計算方法を抜粋すると

             1 (n = 0)
fib(n)= 1 (n = 1)
              fib(n - 1) + fib(n- 2)

となりますが、この計算結果を配列などに保存しておき、
再帰的に計算する際に保存した計算結果を使うことで、
計算にかかる処理を短縮します。

では、ALDS_1_10_A:BibonacciNumberに合わせた全体のプログラムです。

#include <iostream>
using namespace std;

int result[45];

int fib(int n){
    if(n == 0 || n == 1)return result[n] = 1;
    if(result[n] != -1) return result[n];
    return result[n] = fib(n - 1) + fib(n - 2);
}

int main(){
    int n;
    for(int i = 0;i < 45;++i){
        result[i] = -1;
    }
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

最大値に関する優先度付きキューの実装をc++で学ぶ

最大値を返却する優先度付きキューをc++で実装して見たいと思います。
問題文はALDS1_9_C:Priority Queueを参照してください

実装方法としては、キーが大きいものを優先することから
単純にmaxヒープを使うことで実装できます。
maxヒープに関しては、こちらを参照してください。

まず、キーを挿入するinsert関数からみていきたいと思います。
ヒープのサイズを増やして、正しい位置にキーを挿入する流れになります。

void insert(int key){
    gSize++;
    gHeap[gSize] = -INFINITY;
    increaseKey(gSize, key);
}

increaseKey(int i,int key)関数は
2分ヒープの要素iのkeyを増加させる役割を担います。

void increaseKey(int i ,int key){
    if(key < gHeap[i])return;
    gHeap[i] = key;
    while(i > 1 && gHeap[i / 2] < gHeap[i]){
        swap(gHeap[i],gHeap[i / 2]);
        i = i / 2;
    }
}

キーを交換する箇所では、現在の要素のキーと親の要素のキーを比較して、
要素のキーが大きい間、親の要素との交換を繰り返すことで、正しい位置に挿入します。

例として、{20,9,10,7,6,8,5,1,2,4}に15を追加し、追加した位置にincreaseKye関数を実行して見たいと思います。

           20
      9         10
  7     6    8    5
1 2  4 

           20
      9         10
  7     6    8    5
1 2  4 15

           20
      9         10
  7    15    8    5
1 2  4 6

           20
      15         10
  7    9    8    5
1 2  4 6

優先度付きキュー最大値を取得する

つづいて、最大値を取得するプログラムを書きます。
最大ヒープになっているので、根の値を取得すればいいことになります。
取り出す関数を見ていきます

int extract(){
    int maxv;
    if(gSize < 1) return -INFINITY;
    maxv = gHeap[1];
    gHeap[1] = gHeap[gSize--];
    maxHeapify(1);
    return maxv;
}

一時変数に最大値を保持をさせ、
根にヒープの最後の値を移動し、ヒープのサイズを減らします。
最後に根からmaxHeapify関数を実施します。

例として2分ヒープ{20,9,10,7,6,8,5,1,2,4}から最大値を取り出す様子を図にしてみます。

           20
      9         10
  7     6    8    5
1 2  4 

           4
      9         10
  7     6    8    5
1 2  4 

            4
      9         10
  7     6    8    5
1 2   

           10
      9         8
  7     6    4    5
1 2   

最後にALDS1_9_C:Priority Queue
に対応した全体のソースになります。

#include <iostream>

using namespace std;
#define MAX 2000000
#define INFINITY (1<<30)

int gHeap[MAX + 1],gSize;

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

int extract(){
    int maxv;
    if(gSize < 1) return -INFINITY;
    maxv = gHeap[1];
    gHeap[1] = gHeap[gSize--];
    maxHeapify(1);
    return maxv;
}

void increaseKey(int i ,int key){
    if(key < gHeap[i])return;
    gHeap[i] = key;
    while(i > 1 && gHeap[i / 2] < gHeap[i]){
        swap(gHeap[i],gHeap[i / 2]);
        i = i / 2;
    }
}

void insert(int key){
    gSize++;
    gHeap[gSize] = -INFINITY;
    increaseKey(gSize, key);
}

int main(){
    int key;
    char com[10];
    
    while(1){
        cin >> com;
        if(com[0] == 'e' && com[1] == 'n') break;
        if(com[0] == 'i'){
            cin >> key;
            insert(key);
        }else{
            cout << extract() << endl;
        }
    }
    return 0;
}

最大ヒープを出力させるアルゴリズム

ALDS_1_9_B:MaximumHeapを例題にmaxヒープを構築するプログラムを学びます。

最大ヒープとは

以下引用

「節点のキーがその親のキー以下である」という max-ヒープ条件を満たすヒープを、
max-ヒープと呼びます。
max-ヒープでは、最大の要素が根に格納され、ある節点を根とする部分木の節点のキーは、
その部分木の根のキー以下となります。
親子間のみに大小関係があり、兄弟間に制約はないことに注意してください。

この問題でmaxヒープを構築する方法として、2つの関数を用いています。
ひとつは、maxHeapify(A,i)関数で、A[i]をmaxヒープ条件を満たすまで木の葉まで下降させます。

maxHeapify関数

maxHeapify(A,i)はiの左の子と右の子のうち、キーが大きい方を選び、
A[i]よりも大きければ交換する処理を再帰的に繰り返します。
問題に載っている疑似コードをc++に書き直すと以下のようになります。

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    // 値が大きければ交換する
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

buildMapHeap関数

もう一つの関数は、与えられた配列を最大ヒープにするbuildMapHeapです。

この関数では、
子を持つ節点の中で、添え字が最大の節点(2分ヒープの性質上HeapSize / 2となる)から逆順にmaxHeapify(A,i)を行います。

最大ヒープが構築される過程を図で確認する

例として2分ヒープA = {4,1,3,2,16,9,10}
を図にしてみてみましょう。

        4
  1         3
2  16  9  10

子を持つ中で添え字が最大の節点は7 / 2 = 3になりますので、
maxHeapify(A,3)からスタートします。

        4
  1         10
2  16  9    3

続いて、maxHeapify(A,2)関数を呼びます。

        4
  16         10
2  1  9    3

最後に、maxHeapify(A,1)関数を呼びます。

        16
    4        10
2     1   9     3

アルゴリズムに従いmaxヒープが完成しました!

最後に全体のソースコードになります。

#include <iostream>
using namespace std;
#define MAX 2000000

int gHeap[MAX + 1],gSize;

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

int main(){
    cin >> gSize;
    
    for(int i = 1;i <= gSize;++i) cin >> gHeap[i];
    // buildMaxHeap
    for(int i = gSize / 2;i >= 1;--i)maxHeapify(i);
    
    for(int i = 1;i <= gSize;++i){
        cout << " " << gHeap[i];
    }
    cout << endl;
    
    return 0;
}

完全2分木を2分ヒープを題材にしてc++で学ぶ

完全2分木を2分ヒープを題材として、解いてみたいとおもいます。
問題はAIDZU ONLINE JUDGEのALDS1_9_A問題を使いますので、
問題文などはリンクを参照してください。

完全2分木とは

以下問題文からの抜粋です。

すべての葉が同じ深さを持ち、すべての内部節点の次数が 2であるような二分木を完全二分木と呼びます。
また、二分木の最下位レベル以外のすべてのレベルは完全に埋まっており、
最下位レベルは最後の節点まで左から順に埋まっているような木も（おおよそ）完全二分木と呼びます。

完全2分木を配列に当てはめる方法としてはヒープについて書いた記事を参考にしてください。
この法則にしたがって、配列に代入し、出力していきます。
まずは、配列に代入されたキーを出力する箇所をみていきます。

int parent(int i){
    return i / 2;
}

int left(int i){
    return 2 * i;
}

int right(int i){
    return (2 * i) + 1;
}

ヒープを出力する際のルールに則って値を返しています。

あとは、入力されたキーを配列に挿入していき、
対象のキーを出力するのみです。
では、全体のプログラムになります。

#include <iostream>
using namespace std;

#define MAX 100000

int parent(int i){
    return i / 2;
}

int left(int i){
    return 2 * i;
}

int right(int i){
    return (2 * i) + 1;
}

int main(int argc, const char * argv[]) {
    int num,Heap[MAX + 1];
    
    cin >> num;
    for(int i = 1;i <= num;++i){
        cin >> Heap[i];
    }
    
    for(int i = 1;i <= num;++i){
        cout << "node " << i << ": key = " << Heap[i] << ", ";
        if(parent(i) >= 1) cout << "parent key = " << Heap[parent(i)] << ", ";
        if(left(i) <= num) cout << "left key = " << Heap[left(i)] << ", ";
        if(right(i) <= num) cout << "right key = " << Heap[right(i)] << ", ";
        cout << endl;
    }
    
    return 0;
}

二分ヒープとは図で学ぶ

二分ヒープの概念についてまとめます。

2分ヒープ(Binary Heap)は、図のように木の各接点に割り当てられたキーが
一つの配列の各要素に対応した完全二分木で表された構造のことです。
下記の図が2分ヒープを表したものです。

                   [1]
                   25

          [2]               [3]
          12                ９

    [4]        [5]    [6]          [7]
     6          8      5            4

 [8]   [9] [10]
  3     2    1

この図を配列で表すと以下のようになります。

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
25  12   9   6   8   5   4   3   2   1

2分ヒープを配列で表す

図では、2分ヒープを1次元配列で表しています。
2分ヒープを表す配列をA、2分ヒープのサイズをHとすると、
A[1,...,H]に2分ヒープの要素が格納されます。

木の添え字を1から、説点の添え字iが与えられた時の各々にアクセスするには

親[i] = floor(i / 2)(床関数)
左の子[i] = 2 * i
右の子[i] (2 * i ) + 1

で表すことができます。

maxヒープとminヒープ

2分ヒープの各説点のキーは、次に上げるヒープの条件を保つように格納されます。

maxヒープ条件
各節点のキーがその親のキー以下

minヒープ条件
節点のキーがその親のキー以上

図であげた2分ヒープはmaxヒープになります
親子関係のみに大小関係があり、兄弟間に制約はありません。

2分探索木の削除のやり方をc++で学ぶ

ALDS1_8_Cを参考にして2分探索木の削除方法を学んでいきます。
問題文の2分探索木の削除に関するアルゴリズムを抜粋します。

2分探索木から与えられたキーkを持つ節点zを削除するdelete kは、
以下の3つの場合を検討したアルゴリズムに従い、
2分探索木条件を保ちつつ親子のリンク(ポインタ)を更新します。

• 1.zが子を持たない場合、zの親pの子（つまりz）を削除する。
• 2.zが1つの子を持つ場合、zの親の子をzの子に変更、
  zの子の親をzの親に変更し、zを木から削除する
• 3.zが子を2つ持つ場合、zの次節点yのキーをzのキーへコピーし、yを削除する。
  yの削除では1.または2.を適用する。
  ここで、zの次節点とは、中間順巡回でzの次に得られる節点である。

問題では削除する節点としてzを引数として受け取ります。
削除する節点の候補をyとして
削除するyの子をxとして
図で各々のケースを確認してみます。

子を持たないケース(case1)

1をkeyにもつノードを削除したいとします。
ノード1は子を持たないので、繋ぎ直しをする必要がありません。
よって、そのまま消すことができます。

       0
  1(z = y)

子を1つ持つケース(case2)

12をキーにもつノードを削除したいとします。 12は左の子を持っています。

            30
  12(z = y)               88
1(x)  

12をキーにもつノードを削除したいとします。 12は右の子を持っています。

            30
  12(z = y)               88
        15(x)

子を2つ持つケース(case3)

0をキーにもつノードを削除したいとします。
0は下図のような子を持っています。

       0(z)
  1      4
2 3   5(y) 8        
           7(x)

削除する節点yを決める

case1,2の場合はyをzそのものにします。

case3の場合は、中間順巡回でzの次に訪問される節点にします。

削除する節点yの1つの子xを決める

case1の場合は右の子(NIL)
case2の場合はNILでない子
case3の場合はzの次節点の右の子(次節点は最小値なのでに左の子は存在しない)になります。

削除する節点yの親子のポインタを繋ぎ変えてyを削除する

xの親がyの親になるようにポインタを繋ぎ変えます。

yの親の子がxになるようにポインタを繋ぎ変える

yが根のケースなのか、(yの親の)左の子なのか右の子なのかを調べて
ポインタを繋ぎ変えます。

最後に、case3限定でzのキーにyのキーを設定します。

プログラムの部品

続いて、部品となるプログラムをみていきます。
まずは、次節点を返すgetSuccessor関数です。

Node* getTreeSuccessor(Node *x){
    // xに右の子が存在する場合右部分木でキーが最も小さい節点xの次節店にあんる
    if(x->right != NIL)return getMinimumTree(x->right);
    // 右の子が存在しない場合
    Node *y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }
    return y;
}

右の子が存在しない場合、親をたどっていき、
最初に左の子になっている節点の親が次節点になります。
節点に次節点が存在しない場合(木の中でxが最大のキーを持つ場合)はNILを返します。

2分探索木の節点xを根とする場合の最小のキーを持つ節点を返す
getMinimumTree関数です

Node* getMinimumTree(Node *x){
    while(x->left != NIL) x = x->left;
    return x;
}

では、ALDS1_8_Cの問題に合わせたプログラムです。
削除するdeleteTree関数では、上記の手順で書いています。

#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

Node* getMinimumTree(Node *x){
    while(x->left != NIL) x = x->left;
    return x;
}

Node* getTreeSuccessor(Node *x){
    if(x->right != NIL)return getMinimumTree(x->right);
    Node *y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }
    return y;
}

void deleteTree(Node *z){
    Node *y;    // 削除対象Node
    Node *x;    // yの子
    
    // 子がない場合はまたは一つしか子がない場合は対象の節点をそのまま消す
    if(z->left == NIL || z->right == NIL){
        y = z;
    }
    else{
        y = getTreeSuccessor(z);
    }
    
    // yの子xを求める
    if(y->left != NIL){
        x = y->left;
    }
    else{
        x = y->right;
    }
    
    if(x != NIL){
        x->parent = y->parent;
    }
    
    if(y->parent == NIL){
        gRoot = x;
    }else{
        if(y == y->parent->left){
            y->parent->left = x;
        }else{
            y->parent->right = x;
        }
    }
    
    if(y != z){
        z->key = y->key;
    }
    free(y);
}

Node *find(Node* u,int value){
    while(u != NIL && value != u->key){
        if(value < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
// 先行順巡回
void preOrder(Node *u){
    if(u == NIL)return;
    printf(" %d",u->key);
    preOrder(u->left);
    preOrder(u->right);
}

// 中間順巡回
void inOrder(Node *u){
    if(u == NIL)return;
    inOrder(u->left);
    printf(" %d",u->key);
    inOrder(u->right);
}

int main(){
    int n,x;
    string com;
    
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> com;
        if(com[0] == 'f'){
            cin >> x;
            Node *t = find(gRoot,x);
            if(t != NIL) cout << "yes\n";
            else cout << "no\n";
        }
        if(com == "insert"){
            cin >> x;
            insert(x);
        }
        else if(com == "print"){
            inOrder(gRoot);
            cout << "\n";
            preOrder(gRoot);
            cout << "\n";
        }
        else if(com == "delete"){
            cin >> x;
            deleteTree(find(gRoot,x));
        }
    }
    return 0;
}

参考ソース https://book.mynavi.jp/ec/products/detail/id=35408

2分探索木の探索の方法をc++で学ぶ

2分探索木の探索について学びます。
問題はALDS1_8_B:Binary Search Tree2を題材にします。

2分探索木については、こちらに説明を書いています。
また、2分探索木の挿入については、こちらに書いています。

2分探索木の探索のコード

先のリンク先で書いた2分探索木のルールとして右の木の値が左の木よりも大きい
というルールで木を構築したので、キーが小さければ左の木をそうでなければ、右の木を探索していき。
木がNILになると見つからなかったというコードを書くことになります。

ここでは、探索したキーが見つかった場合、キーを持つ対象のノードを返し、
見つからなかった場合は空のノードを返す関数を書きます。
返り値のノードが空でなければ、2分探索技の中にキーが存在するということになります。

Node *find(Node* u,int value){
    while(u != NIL && value != u->key){
        if(value < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

while文でキーが見つからない&NILではないという条件文を書きました。
では、全体のソースコードを確認してみます。

c++による全体のソースコード

#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

Node *find(Node* u,int value){
    while(u != NIL && value != u->key){
        if(value < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
// 先行順巡回
void preOrder(Node *u){
    if(u == NIL)return;
    printf(" %d",u->key);
    preOrder(u->left);
    preOrder(u->right);
}

// 中間順巡回
void inOrder(Node *u){
    if(u == NIL)return;
    inOrder(u->left);
    printf(" %d",u->key);
    inOrder(u->right);
}

int main(){
    int n,x;
    string com;
    
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> com;
        if(com[0] == 'f'){
            cin >> x;
            Node *t = find(gRoot,x);
            if(t != NIL) cout << "yes\n";
            else cout << "no\n";
        }
        if(com == "insert"){
            cin >> x;
            insert(x);
        }
        else if(com == "print"){
            inOrder(gRoot);
            cout << "\n";
            preOrder(gRoot);
            cout << "\n";
        }
    }
    return 0;
}

2分探索木挿入とはなにかをALDS 1_8_Aを題材にc++で学ぶ

2分探索木の挿入に関して、ALDS 1_8_A:Binary Search Tree1を題材にして学びます。

2分探索木の挿入

今回の問題では、右の木よりも左の木の方が値が小さいという条件のもと、
2分探索木を構築していきます。
30,88,12,1,20,17,25の値を空の木に挿入し、木が構築される例を見ていきます。

2分木の根から挿入するキーが対象のノードに対し、大きいか小さいかを判定し、
対象の根が空になった時点で空となった対象の親に左または右に挿入します。

key30を挿入

            30

木が空なので、そのまま挿入します。

key88を挿入

            30

                     88

rootのキー30を対象にして、挿入位置をチェックします。
rootのキー30よりも挿入キーが大きいので、30の右側に挿入します。

key12を挿入

            30

  12               88

12はrootの30よりも小さいので、30の左に挿入します。

key1を挿入

            30

  12               88

1  

対象を30,12と移動して1を挿入します。

key20挿入

            30

  12               88

1  20

key17挿入

            30

  12               88

1  20
 
  17

key25を挿入

            30

  12               88

1  20
 
    7  25

挿入手順として、根のキーを始点として探索します。
自身のキーが根のキーよりも小さければ左の子、
大きければ右の子を次の探索の節点として変えていき、
節点が空になったら挿入します。
また、その時に挿入する位置となる親を節点を変更するごとに保持・変更しておき、挿入位置が空になった時に、
親として代入することができるようにしておきます。

2分探索木挿入のプログラム

2分探索木を動的に実装するために以下の構造体を定義します。

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

続いて、挿入するプログラムを見ていきます。

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}

上記の図で説明したことをそのままプログラムにしています。
では、全体のソースです。

#include <stdio.h>
#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int key;
    Node *left,*right,*parent;
};

Node *gRoot,*NIL;

void insert(int value){
    Node *y = NIL;
    // 親
    Node *x = gRoot;
    // 自身
    Node *z;
    z = (Node*)malloc(sizeof(Node));
    z->key = value;
    z->left = NIL;
    z->right = NIL;
    
    // rootから自身を挿入する場所を探す
    while(x != NIL){
        // rootから検索
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    
    z->parent = y;
    // 親に子を持たせる
    if(y == NIL){
        gRoot = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}
// 先行順巡回
void preOrder(Node *u){
    if(u == NIL)return;
    printf(" %d",u->key);
    preOrder(u->left);
    preOrder(u->right);
}

// 中間順巡回
void inOrder(Node *u){
    if(u == NIL)return;
    inOrder(u->left);
    printf(" %d",u->key);
    inOrder(u->right);
}

int main(){
    int n,x;
    string com;
    
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> com;
        if(com == "insert"){
            cin >> x;
            insert(x);
        }
        else if(com == "print"){
            inOrder(gRoot);
            cout << "\n";
            preOrder(gRoot);
            cout << "\n";
        }
    }
    return 0;
}

2分探索木とはなにか？図で理解する

2分探索木は、各々の節点ごとにキーを持ち、2分探索木条件を常に満たすように構築された木です。

2分探索木条件とは、ある節点の左の木が兄弟の右の木やその節点よりも必ず低い値をもつなどの
一定の条件を満たす木のことです。
では、例を見ていきましょう

            30

  12           88

1  20
 
    7  25

この木の条件を例に見ると
キーが30の根の左部分木に該当するキーは全て30以下になっています。
右部分木に属する節点のキーは左部分木よりも大きいという条件が成り立っていることがわかります。
これが2分探索木になります。

木の巡回とは

木の操作には木の巡回と呼ばれる探索方法があります。
その探索方法を学びます。

例として以下の2分木を定義します。

       0
  1      4
2 3   5 8        
       6 7

この2分木を例として、木の巡回の出力例を見ていきましょう。

木の先行順巡回(Preorder Tree Walk)

根節点、左部分木、右部分木の順で節点の番号を出力します。

出力例
0 1 2 3 4 5 6 7 8

木の中間順巡回(Inorder Tree Walk)

左部分木、根節点、右部分木の順で節点の番号を出力します。

出力例
2 1 3 0 6 5 7 4 8

木の後行順巡回(Postorder Tree Walk)

左部分木、右部分木、根節点の順で節点の番号を出力します。

出力例
2 3 1 6 7 5 8 4 0

では、AIDU ONLINE JUDGEのALDS1_7_Cの木巡回の問題例に、
プログラムをチェックしましょう。

// 先行順巡回
void preParse(int u){
    if(u == NIL)return;
    printf(" %d",u);
    preParse(gNode[u].left);
    preParse(gNode[u].right);
}

// 中間順巡回
void inParse(int u){
    if(u == NIL)return;
    inParse(gNode[u].left);
    printf(" %d",u);
    inParse(gNode[u].right);
}

// 後行順巡回
void postParse(int u){
    if(u == NIL) return;
    postParse(gNode[u].left);
    postParse(gNode[u].right);
    printf(" %d",u);
}

出力する位置を変えることによって、
各々の出力形式で出力しています。

では、全体のソースです。

#include <stdio.h>
#include <iostream>
using namespace std;
// node最大量
#define MAX 100000
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];

// 先行順巡回
void preParse(int u){
    if(u == NIL)return;
    printf(" %d",u);
    preParse(gNode[u].left);
    preParse(gNode[u].right);
}

// 中間順巡回
void inParse(int u){
    if(u == NIL)return;
    inParse(gNode[u].left);
    printf(" %d",u);
    inParse(gNode[u].right);
}

// 後行順巡回
void postParse(int u){
    if(u == NIL) return;
    postParse(gNode[u].left);
    postParse(gNode[u].right);
    printf(" %d",u);
}

int main(){
    int left,right,v,n,root = 0;
    cin >> n;
    // 初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    
    for(int i = 0;i < n;++i){
        cin >> v >> left >> right;
        gNode[v].left = left;
        gNode[v].right = right;
        // 親の設定
        if(left != NIL){
            gNode[left].parent = v;
        }
        if(right != NIL){
            gNode[right].parent = v;
        }
    }

    // rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    cout << "Preorder\n";
    preParse(root);
    cout << "\n";
    cout << "Inorder\n";
    inParse(root);
    cout << "\n";
    cout << "Postorder\n";
    postParse(root);
    cout << "\n";
    
    return 0;
}

ALDS1_7_B BinaryTree(2分木)を参考にしてと2分木表現を学ぶ

AIZU ONLINE JUDGEのALDS1_7_B BinaryTree
の問題を参考に、2分木の表現方法を学びます。

問題文

与えられた根付き二分木 T の各節点 u
について、以下の情報を出力するプログラムを作成してください。

• uの節点番号
• uの親
• uの兄弟
• uの子の数
• uの深さ
• uの高さ
• 節点の種類（根、内部節点または葉）

ここでは、与えられる二分木は n 個の節点を持ち、それぞれ 0 から n－1 の番号が割り当てられているものとします。

入力例などは以下を参考にしてください。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_B&lang=jp

2分木を表現する構造体の定義

2分木を表現するための構造体の定義をします。
木を表現するためには、節点が必要になりますが、
2分木では節点は左右の子のみとルートを示す親を持てば
木全体を表現することができることがわかると思います。

struct Node {
    int parent;
    int left;
    int right;
};

2分木の深さをセットする

2分木の深さを求めるために、木のrootから子を探索し
left、right共にNILになるまで、再起的にチェックします。

// 深さを設定する
void setDepth(int u,int d){
    // 親の節点が葉のケース
    if(u == NIL) return;
    gDepth[u] = d;
    // 左右の子にもセットする
    setDepth(gNode[u].left, d + 1);
    setDepth(gNode[u].right, d + 1);
}

兄弟のノードを求める

兄弟のノードを求めるには、
単純に親がいるかをチェックし、親の左の子・右の子を調べます
子が自身のノードである可能性があるので、そのケースを除きます。

int getSibling(int u){
    // rootの場合
    if(gNode[u].parent == NIL)return NIL;
    // 自身が右の子だった場合
    if(gNode[gNode[u].parent].left != u && gNode[gNode[u].parent].left != NIL){
        return gNode[gNode[u].parent].left;
    }
    // 自身が左の子だった場合
    if(gNode[gNode[u].parent].right != u && gNode[gNode[u].parent].right != NIL){
        return gNode[gNode[u].parent].right;
    }
    // 親が一つしか子を持たない状態
    return NIL;
}

2分木の高さを求める

この場合の高さは、あるノードの末尾の子から自分との差分になります。
自分から左右の子が存在するかどうか再帰的にチェックしていき、深い方の子と自分との差分を返します。

// 高さの設定をする
int setHeight(int u){
    int h1,h2;
    h1 = h2 = 0;
    if(gNode[u].left != NIL){
        h1 = setHeight(gNode[u].left) + 1;
    }
    if(gNode[u].right != NIL){
        h2 = setHeight(gNode[u].right) + 1;
    }
    return gHeight[u] = (h1 > h2) ? h1 : h2;
}

最後にc++で書かれた全体のソースを載せます。

#include <stdio.h>
#include <iostream>
using namespace std;
// node最大量
#define MAX 100005
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];
int gDepth[MAX],gHeight[MAX];

// 兄弟を返す
int getSibling(int u){
    // rootの場合
    if(gNode[u].parent == NIL)return NIL;
    // 自身が右の子だった場合
    if(gNode[gNode[u].parent].left != u && gNode[gNode[u].parent].left != NIL){
        return gNode[gNode[u].parent].left;
    }
    // 自身が左の子だった場合
    if(gNode[gNode[u].parent].right != u && gNode[gNode[u].parent].right != NIL){
        return gNode[gNode[u].parent].right;
    }
    // 親が一つしか子を持たない状態
    return NIL;
}

void print(int node){
    cout << "node " << node << ": ";
    cout << "parent = " << gNode[node].parent << ", ";
    cout << "sibling = " << getSibling(node) << ", ";
    
    int deg = 0;
    if(gNode[node].left != NIL) deg++;
    if(gNode[node].right != NIL) deg++;
    cout << "degree = " << deg << ", ";
    cout << "depth = " << gDepth[node] << ", ";
    cout << "height = " << gHeight[node] << ", ";
    
    if(gNode[node].parent == NIL){
        cout << "root\n";
    }else if(gNode[node].left == NIL && gNode[node].right == NIL){
        cout << "leaf\n";
    }else{
        cout << "internal node\n";
    }
}

// 深さを設定する
void setDepth(int u,int d){
    // 親の節点が葉のケース
    if(u == NIL) return;
    gDepth[u] = d;
    // 左右の子にもセットする
    setDepth(gNode[u].left, d + 1);
    setDepth(gNode[u].right, d + 1);
}

// 高さの設定をする
int setHeight(int u){
    int h1,h2;
    h1 = h2 = 0;
    if(gNode[u].left != NIL){
        h1 = setHeight(gNode[u].left) + 1;
    }
    if(gNode[u].right != NIL){
        h2 = setHeight(gNode[u].right) + 1;
    }
    return gHeight[u] = (h1 > h2) ? h1 : h2;
}

int main(){
    int left,right,v,n,root = 0;
    cin >> n;
    // 初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    
    for(int i = 0;i < n;++i){
        cin >> v >> left >> right;
        gNode[v].left = left;
        gNode[v].right = right;
        // 親の設定
        if(left != NIL){
            gNode[left].parent = v;
        }
        if(right != NIL){
            gNode[right].parent = v;
        }
    }

    // rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    // 根からはじめて深さを代入する
    setDepth(root, 0);
    setHeight(root);
    
    for(int i = 0;i < n;++i){
        print(i);
    }
    return 0;
}

参考ソース
https://book.mynavi.jp/ec/products/detail/id=35408

ALDS1_7根付き木の解法と根付き木についてc++で学ぶ

AIZU Online judgeの根付き木の解法メモです。
サンプルのコードがわかりにくかったので、読み解いてみました。

問題は以下になります。

与えられた根付き木 T の各節点 u
について、以下の情報を出力するプログラムを作成してください。

• uの節点番号
• uの親の節点番号
• uの深さ
• uの節点の種類（根、内部節点または葉）
• uの子のリスト

ここでは、与えられる木は n 個の節点を持ち、それぞれ 0 から n－1 の番号が割り当てられているものとします。

入力

入力の最初の行に、節点の個数 n が与えられます。続く n行目に、各節点の情報が次の形式で１行に与えられます。

id
k c1 c2 ... ck

idは節点の番号、k は次数を表します。
c1 c2 ...ck は 1 番目の子の節点番号、... k 番目の子の節点番号を示します。

出力方式

次の形式で節点の情報を出力してください。節点の情報はその番号が小さい順に出力してください。

node id: parent = p , depth = d, type, [c1...ck]

pは親の番号を示します。ただし、親を持たない場合は -1 とします。
dは節点の深さを示します。

typeは根、内部節点、葉をそれぞれあらわす root、internal node、leaf の文字列のいずれかです。
ただし、根が葉や内部節点の条件に該当する場合は root とします。

c1...ck は子のリストです。
順序木とみなし入力された順に出力してください。
カンマ空白区切りに注意してください。
出力例にて出力形式を確認してください。

入力例

13
0 3 1 4 10
1 2 2 3
2 0
3 0
4 3 5 6 7
5 0
6 0
7 2 8 9
8 0
9 0
10 2 11 12
11 0
12 0

出力

node 0: parent = -1, depth = 0, root, [1, 4, 10]
node 1: parent = 0, depth = 1, internal node, [2, 3]
node 2: parent = 1, depth = 2, leaf, []
node 3: parent = 1, depth = 2, leaf, []
node 4: parent = 0, depth = 1, internal node, [5, 6, 7]
node 5: parent = 4, depth = 2, leaf, []
node 6: parent = 4, depth = 2, leaf, []
node 7: parent = 4, depth = 2, internal node, [8, 9]
node 8: parent = 7, depth = 3, leaf, []
node 9: parent = 7, depth = 3, leaf, []
node 10: parent = 0, depth = 1, internal node, [11, 12]
node 11: parent = 10, depth = 2, leaf, []
node 12: parent = 10, depth = 2, leaf, []

問題は以上です。

根付き木とは

根(root)を持つ木構造のことを根付き木といいます。
根は親を持たない唯一の節点のことをいいます。

では、問題を解いていきます。
まず、木の接点となるnodeの定義をします。

// node最大量
#define MAX 100005
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];
int gDepth[MAX];

構造体としてNodeを定義して
子がないことなどを示すためNILを定義しました。
NILはobjective-cなどにも定義されています。

leftは子という意味合いでrightは同じ階層の兄弟のような意味合いです。

続いて出力関数を定義します。

void print(int node){
    cout << "node " << node << ": ";
    cout << "parent = " << gNode[node].parent << ", ";
    cout << "depth = " << gDepth[node] << ", ";
    
    if(gNode[node].parent == NIL) cout << "root, ";
    else if(gNode[node].left == NIL)cout << "leaf, ";
    else cout << "internal node, ";
    
    cout << "[";
    
    for(int i = 0,left = gNode[node].left;left != NIL;++i,left = gNode[left].right){
        if(i) cout << ", ";
        cout << left;
    }
    cout << "]" << endl;
}

わかりにくいところは、left(左の木)を出力する箇所だと思います。
順番としてまず、対象のnodeのleftを出力します。
続いて、出力したleft nodeに飛び、そのleft(nodeと表現できる)のrightをのleftを出力
これを繰り返します。

続いて深さを求めて、global変数gDepthに代入する関数です。

// 再帰的に深さを求める
void rec(int node ,int parent){
    gDepth[node] = parent;
    if(gNode[node].right != NIL){
        // 右の兄弟に同じ深さを設定
        rec(gNode[node].right,parent);
    }
    if(gNode[node].left != NIL){
        // 最も左の子に自分の深さ+1を設定
        rec(gNode[node].left,parent + 1);
    }
}

道具が揃ったので、main関数を書きます。

int main(){
    int nodeNum,nodeIndex,node,left,root,n;
    cin >> n;
    // 1.初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    // 2.nodeに代入していく
    for(int i = 0;i < n;++i){
        cin >> nodeIndex >> nodeNum;
        for(int j = 0;j < nodeNum;++j){
            cin >> node;
            // 初期値はleft
            if(j == 0){
                gNode[nodeIndex].left = node;
            }
            else{
                gNode[left].right = node;
            }
            left = node;
            gNode[node].parent = nodeIndex;
        }
    }
    
    // 3.rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    // 根からはじめて深さを代入する
    rec(root,0);
    
    // 4.nodeのindexごとに出力する
    for(int i = 0;i < n;++i){
        print(i);
    }
    return 0;
}

1.初期化
まずは、NILで初期化します。

2.gNodeに入力された情報を埋め込みます。
初期値は必ずleftに2つめ以降はrightに入れていきます。
nodeの親は変わりません。

3.で根をさがしてそのindexを代入しています。

4.最後にprint関数を使い、nodeのindex順に出力します。

以上です。

こちらを参考にしています。

計数ソートとはc++で学ぶ

計数とは単純に数を数えるという意味らしく、
その名の通り、計数ソートは数を数えるアルゴリズムです(全部そうな気がしますが)

計数ソートのアルゴリズム

まず、以下の数列があり、これらを昇順にソートしたいとします。

A 5 0 5 3 1 4 5 0

この数列を配列Aとします。
計数ソートでは配列Aの各々の要素がいくつあるかを別の配列(Bとする)に記録することから始めます。

A 5 0 5 3 1 4 5 0

   0 1 2 3 4 5 6
B 2 1 0 1 1 3 0
B 2 3 3 4 5 8 8

上図では、要素の数を配列のindexに見立てて代入した後
各要素の累積和を求めて更新しています。
つまり、B[x]には配列Aについてのx以下の要素数が記録されていることになります。
これを利用して、ソートされた数列を作り出していきます。

次に昇順にソートされた数列を作りだされる過程をみていきます

1.

A 5 0 5 3 1 4 5 0
B 2 3 3 4 5 8 8

   1 2 3 4 5 6 7 8
C    0 

配列Aの末尾から0を取り出します。
続いて配列Bからindex0の要素数2を取り出します。
そして出力先となる配列Cのindex2に0を挿入します。
また、配列Cは便宜上index1からスタートしていることします。

配列Bから配列Cに挿入したindex0の要素数を一つ減らして1とします
挿入した要素を減らすことで、次に挿入する位置を調整しています。

2.

A 5 0 5 3 1 4 5 0
B 1 3 3 4 5 8 8

   1 2 3 4 5 6 7 8
C    0                  5

Aから末尾の位置を一つずらして、1と同じ動作を繰り返します。
Aの要素は5、Bのindex5の要素は8なので、cのindex8に5を代入し、
Bのindex5の要素数を一つ減らして7とします。

以下これを繰り返すことにより、昇順にソートすることができます。

計数ソートのオーダー

計数ソートは各要素が0以上k以下である要素数nの数列に対しO(n + k)で動作します。 動作で見る通りですね。

全探索アルゴリズム(brute force)と再帰処理

全探索アルゴリズムについて調べていたら、AIZU Online judgeにいい問題があったので、それを元に理解を深めます(個人的に)

問題は以下の通りです。

長さnの数列Aと整数mに対して、
Aの要素の中のいくつかの要素を足しあわせて
mが作れるかどうかを判定するプログラムを作成してください。
Aの各要素は１度だけ使うことができます。
数列 Aが与えられたうえで、質問として q 個の mi が与えれるので、
それぞれについて "yes" または "no" と出力してください。

制約が重くないために、
与えられた数値の全ての組み合わせを試せば問題が解けることになります。

制約

• n≤20
• q≤200
• 1≤Aの要素≤2,000
• 1≤mi≤2,000

問題の組み合わせ総数

与えられた数値が

1,3,5,7

だった場合、各々の数値をを使うか使わないかの選択になるので、
2^nの組み合わせになります。

再帰関数を使って、全探索を考える

以下引用になります。

1  makeCombination()
2    for i = 0 to n-1
3      S[i] = 0 // i を選択しない
4    rec(0)
5
6  rec(i)
7    if i == n
8      print S
9      return
10
11   rec(i + 1)
12   S[i] = 1 // i を選択する
13   rec(i + 1)
14   S[i] = 0 // i を選択しない

S配列をS[i] = 1の時その要素を選択する0は選択しないことを表す配列とします。
選択するかしないかを再帰関数により分岐させ、2^n - 1までのビット列を生成します。

この考え方を利用して、再帰関数を考えます。
solve(i,m)を「i番目以降の要素を使ってmを作れる場合trueを返す」という関数にすると、
solve(i,m)はより小さい部分であるsolve(i + 1,m)とsolve(i + 1,m - A[i])に分割することができます。
m - A[i]というところが、「i番目以降の要素を使う」に対応しています。

solve関数をc++で実装

再帰処理を行うsolve関数をc++で実装してみます。

// 入力値のmから選んだ要素を引いていく再帰関数
// 0なら組み合わせで生成できる数値
int solve(int i,int m){
    if(m == 0) return 1;
    if(i >= n) return 0;
    return solve(i + 1,m) || solve(i + 1,m - A[i]);
}

solveを使うmain関数を見ます。
入力された数列の各々の数値において、 与えられた数列で作りだせるかどうかをsolve関数を使って
判定しています。

int n,A[50];

int main(){
    int q,m;
    
    scanf("%d",&n);
    
    for(int i = 0;i < n;++i){
        scanf("%d",&A[i]);
    }
    
    scanf("%d",&q);
    
    for(int i = 0;i < q;++i){
        scanf("%d",&m);
        if(solve(0,m))printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

2分探索アルゴリズムの考え方とc++のソース

2分探索アルゴリズムとは

2分探索(binary search)アルゴリズムは、まず昇順or降順にソートした後に、探索開始位置を2分しながら
数値の大小をチェックし探索していくアルゴリズムになります。

では、2分探索のアルゴリズムの使用例を見ていきます。

2分探索アリゴリズムの使用例

以下のような要素を10個持つ数列があるとします。

10 8 12 6 14 4 16 2 18 20

この数列を2分探索を行うために、昇順または降順にソートします。
今回は、昇順にソートします。

2 4 6 8 10 12 14 16 18 20

では、この数列から4が存在するかどうかを
2分探索アルゴリズムを使い、探索してみます。

2分探索では探索位置を記憶するための変数として、
左辺値(left)・中央値(center)・右辺値(right)
を使います。
役割をそれぞれ説明すると、

左辺値(left)=先頭要素の位置

中央値(center)=左辺値と右辺値を足して2で割った中間の要素の位置

右辺値(right)=末尾の要素の位置

をそれぞれ示しています。

では、2分探索を実行してみます。

2分探索を実行する

1.中央位置を決定する

数列を配列だとみなすと、
leftが0、rightが9なので、centerが(0 + 9) / 2 = 4(小数点を切り捨てた)になるので、
探索位置はのindexは4です。

数列の要素4に該当するのは、

10です。

2.中央値とkeyとなる数値の大小をチェックする

探索値10とkey4の大小を調べます。

4 < 10なので、rightの9をcenterの4にし、
centerの値を再度計算します。

center = (0 + 4) / 2 = 2

後は、このように
1.2の計算を繰り返すことにより、
半分づつ探索位置をずらしながら、
探索を実行していきます。

では、2分探索のルールに従い探索を続けていきます。

center2の数値は6
一致しないので、
再度計算します。

rightに中央の位置を代入して、

right = 2

中央の位置を計算して、

center = (0 + 2) / 2 = 1

centerのindex1の数値は4となり一致したので、
2分探索終了です。

探索回数は3回でした。

探索値が大きかった場合

探索値が大きかった場合はleftを変更しますが、

leftの位置をずらす場合は、
left = center + 1
とします。

これは、keyとなる数値が探索数列内の値を超えていた場合 ループしてしまうからです。

2分探索の実行回数

2分しながら探索していていくことから、
探索回数はO(logn)になります。

c++のソースコード

最後にc++のソースコードを載せます

#include <iostream>

bool binarySearch(int numbers[],int length,int key){
    int left = 0;
    int right = length;
    int center;
    
    while(left < right){
        center = (left + right) / 2;
        if(key == numbers[center]) return true;
        else if(key > numbers[center]) left = center + 1;
        else right = center;
    }
    return false;
}

int main(int argc, const char * argv[]) {
    int numbers[] = {2,4,6,8,10,12,14,16,18,20};
    printf("%d",binarySearch(numbers, 10, 4));
    printf("%d",binarySearch(numbers, 10, -2));
    return 0;
}