線形探索とはなにか？そのアルゴリズムをc++で学ぶ

線形探索とは、配列にような一列に並んだデータを先頭から一つづつ検索していくアルゴリズムのことです。

ランダムに並べられた数列から対象となる数字を検索したい場合は以下のように、
配列の先頭から最後尾まで、目的の数字を探索するプログラムを書きます。

// keyを探すプログラム
int key = 3;
int numbers[] = {2,4,6,8,1,3,5,9,7,10};
for(int i = 0;i < 10;++i){
  if(numbers[i] == key){
    return true;
  }
}

上記のプログラムでは、number[i] == keyにて、
一回のみ条件判定を行なっているように見えますが、
for文でi < 10の条件分岐を判定をしていることから、2回行なっています。
この条件判定を番兵と呼ばれる概念を使用することにより1回に減らすことができます。

番兵とは

データの終了を示すために配置される特殊なデータを指す
wikipediaより

では、データ終了を示すために配置される番兵を使って
線形探索を行なってみます。

データの終了を示すために、Keyとなる数字を配列の末尾に挿入します。 Keyを挿入しているということは、絶対にKeyは見つかります。
配列のindexが末尾まで到達していた場合Keyが見つからなかったことになるので、
この条件を使用することで、2回行われていた判定条件を一つにします。

int key = 3;
// 番兵として配列の末尾にKeyを挿入する
int numbers[] = {2,4,6,8,1,3,5,9,7,10,3};
int i = 0;
while(numbers[i] != key)i++;
// 末尾までいっていたら見つからなかったことになる
return i != 10;

上記のように番兵を使うことで条件分岐の回数を減らすことができました。
ほかの優秀なアルゴリズムがあるので、線形探索自体あまり使われませんが、
有効な考え方だと思いました。

幅優先探索のアルゴリズムをc++で学ぶ

幅優先探索のアルゴリズムを学びます。

幅優先探索はグラフで用いられるアルゴリズムで、深さ優先探索と対等してあげられることが多いようです。

深さ優先探索では、隣接するノードが見つかった場合、そのノードを探索しにいきますが、幅優先探索では、隣接ノードが見つかった場合でもそのノードを探索しにいこうとせず、他に隣接するノードがないかをチェックしにいきます。

幅優先探索のアルゴリズム図で学ぶ

幅優先探索のアルゴリズムを学んでいきましょう。
このグラフを幅優先探索にかけてみます。

 

1.ノード1をキューにいれる

1

2.ノード1を取り出して、ノード1に隣接している未訪問のノードをキューに入れます。

1 2

3.次にノード2を取り出して隣接しているノード3,4をキューにいれます。

1 2 3 4

4.つぎにノード3に隣接しているノードをチェックします。
ノード3はノード7に隣接しているので、7をキューに入れます。

1 2 3 4 7

5.次はノード4の隣接ノードを探索します、ノート2とノード5が隣接していますが、
ノード2は探索済みなので、キューには入れません。

1 2 3 4 7 5

6.以後、これを繰り返し、キューに入れた数(end)と、探索を開始する始点(head)が
一致した時点で探索終了です。

幅優先探索のアルゴリズムをc++で学ぶ

最後に、c++で書かれたプログラムを載せます。
ソースは上記のグラフを元にしたものです。

#include <queue>
using namespace std;

#define MAX 8
bool visited[MAX];

int GRAPH[MAX][MAX] = {
    {0,1,0,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,1,0},
    {0,1,0,0,0,0,0,0},
    {0,0,0,1,0,1,0,0},
    {0,0,0,0,1,0,1,1},
    {0,0,1,0,0,1,0,1},
    {0,0,0,0,0,1,1,0}
};

queue<int>q;

int main() {
    // queueに入れる
    q.push(0);
    visited[0] = true;
    
    do{
        int i = q.front();
        q.pop();
        for(int j = 0;j < MAX;++j){
            // 経路発見
            if(GRAPH[i][j] == 1 && !visited[j]){        
                printf("%d->%d ",i + 1,j + 1);
                q.push(j);
                visited[j] = true;
            }
        }
    }while(!q.empty());
}

非連結グラフのプログラムで表現する

非連結グラフをプログラムで表現します。

基本は、連結グラフの時と変わりませんが、 グラフが分かれていることを
示すために変数を持っています。

図は以下の非連結グラフを使っています。
1から4が一つのグラフとなっており
5から8が一つのグラフとなっています。

cでのプログラムになります。

#include 
using namespace std;

#define MAX 8
bool visited[MAX];

void visit(int i);

int GRAPH[MAX][MAX] = {
    {0,1,0,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,0,0},
    {0,1,0,0,0,0,0,0},
    {0,0,0,0,0,1,0,0},
    {0,0,0,0,1,0,1,1},
    {0,0,0,0,0,1,0,1},
    {0,0,0,0,0,1,1,0}
};

int main() {
    // 非連結用
    int count = 1;  
    
    for(int i = 0;i < MAX;++i){
        if(!visited[i]){
            printf("graph%d:",count++);
            visit(i);
        }
    }
    return 0;
}

void visit(int i){
    visited[i] = true;
    for(int j = 0;j < MAX;++j){
        if(GRAPH[i][j] == 1 && !visited[j]){
            printf("%d->%d ",i + 1,j + 1);
            visit(j);
        }
    }
}

実行結果

graph1:1->2 2->3 2->4 graph2:5->6 6->7 7->8

非連結グラフ(disconnected graph)とは

非連結グラフ(disconnected graph)はグラフが分かれているもののことをいいます。

図にすると、こんな感じです。

グラフの説明で載せたグラフの図を分解しました。
数字1,2,3,4は一つのグラフですが、5,6,7,8は別のグラフになっています。
こういう概念です。

グラフの深さ優先探索をc言語で学ぶ

グラフを探索する方法の一つに深さ優先探索(DFS:Depth-First-Search)があります。

探索方法をグラフの解説で使用したグラフを例に解説すると、

 

まず、ノード1に隣接するノードを走査します。

ノード1にノード2が隣接するのでノード2を走査しに行きますが、
この時にノード1に隣接する他のノードの探索を行う前に、
ノード2に隣接するすべてのノードの探索を行います。

ノード2でもノード1と同様に探索を行いノード3を見つけます。

ノード3を見つけたら、ノード4は探索せずに、ノード3の探索を行います。

これを続けていき、隣接ノードが見つからない場合前のノードに戻り、
これを繰り返し、すべての探索が終わったら探索を終了します。

この時にループ処理に陥らないように、一度訪れたノードに対してフラグをもたせます。

では、cで書かれた深さ優先探索を行うコードを見て見ます。
このコードは、上記のグラフを例にしています。

#include 
using namespace std;

#define MAX 8
bool visited[MAX];

void visit(int i);

int GRAPH[MAX][MAX] = {
    {0,1,0,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,1,0},
    {0,1,0,0,0,0,0,0},
    {0,0,0,1,0,1,0,0},
    {0,0,0,0,1,0,1,1},
    {0,0,1,0,0,1,0,1},
    {0,0,0,0,0,1,1,0}
};

int main() {
    visit(0);
    return 0;
}

void visit(int i){
    visited[i] = true;
    for(int j = 0;j < MAX;++j){
        if(GRAPH[i][j] == 1 && !visited[j]){
            printf("%d->%d ",i + 1,j + 1);
            visit(j);
        }
    }
}

実行結果

1->2 2->3 3->7 7->6 6->5 5->4 6->8

ポイントは、一度訪れたノードに対してフラグを持つことです。

グラフとは有効グラフ無効グラフとは

グラフ(graph)は節点(node)を辺(edge)で結んだものです。

グラフの図を例に挙げます。

このグラフでは、節点を辺で結んでいますが、
辺で結ばれた間は行き来する道があることを示しています。

隣接行列

先のようなグラフをデータとして表現するたの手法として、
隣接行列(adjacency matrix)があります。

先のグラフを隣接行列で表してみます。

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

節点から節点へ辺がある場合には1でない場合は0で
表現しています。

無効グラフ

辺に向きのないものを無効グラフと言います。
先で示したグラフは無効グラフになります。

有効グラフ

辺に向きをもたせたものを有効グラフと言います。
有効グラフの辺には矢印をもたせます。

有向グラフでは、矢印が向いている方向に対してのみ道があります。

例をあげると、
先のグラフ図で、1 → 2と向いている場合
隣接行列で表現すると、

1 → 2は1になるが
2 → 1は0になります。

木構造の解説

枝分かれしながら、データが増えていくデータ構造を木構造といいます。

木構造を図で示すと以下のようになります。

木は節点(node)とそれらを結んでいる枝(branch)によって構成されます。
節点はデータを表し、枝はその節点との関係にあたります。

分岐元の節点を親といい、枝をたどった先の節点を子といいます。

また、一番先頭の接点を根(root)と呼び、子を持たない接点のことを葉(reef)といいます。

深さと高さ

根からある節点に至るまでに通る枝の数をその頂点の深さ(depth)といい、
根から最も深い節点までの深さを木の高さ(height)>といいます。

図でいうと、木の高さは2になります。

2分木と2分探索木

木のうちで、各々の節点から出る枝の数が2本以下であるものを2分木といいます。

また、各々の節点のデータが比較可能で、
親と子の関係に規則がある(親と子に大小の関係あるなど)木のことを2分探索木(binary search tree)といいます。

この規則を元にし、アルゴリズムでは木が利用されます。

全二分木(Full Binary Tree)とは

全二分木は、すべてのノードが2つか子を持たない二分木をいいます。

親が一つしか子を持たないので、全二分木ではない。

     10
   1
3    5

全てのノードが2つ子を持っている・または子をもっていないので、
全二分木である。

     10
   1      20
3    5

complete binary treeとは

complete binary treeとは、一番深いノード以外すべてのノードが満たされている2分木のこと。

また、一番深いノードは、
左から右の順に埋まっているという条件も満たしている必要があります。
図解すると、、、

一番下のノードが右しかないので、complete binary treeではない。
           10
    5           20
3     6              40

           10
    5           20
3     6    16

一番下のノードが左から始まっているので、complete binary treeである。

スタック内の最小値を返すスタッククラスを作成する

問題：スタック内の最小値を返すスタッククラスを作成する

カスタムしたクラス内に最小値を保存スタックを持つことで、
簡潔にコードを書くことができます。

pushするときにカスタムスタッククラス内のスタックメンバーの最小値を
チェックし、最小ならばpushする。

popも同様の処理を行うことで、最小値を保持するスタックが完成します。

kotlinでのサンプルを載せます。

import java.util.Stack

class StackWithMin : Stack(){
    var stack : Stack = Stack()

    override fun push(value : Int): Int? {
        if(value < getMin()){
            stack.push(value)
        }
        return super.push(value)
    }

    fun getMin() : Int {
        if(stack.isEmpty()){
            return Integer.MAX_VALUE
        }
        else{
            return stack.peek()
        }
    }

    override fun pop() : Int{
        val value = super.pop()
        if(value == getMin()){
            stack.pop()
        }
        return value
    }
}

続いてmain関数での実行例です。

fun main(args : Array){
    var stack : StackWithMin = StackWithMin()
    stack.push(100)
    stack.push(50)
    stack.push(1)
    // 1
    println(stack.getMin())
    stack.pop()
    // 50
    println(stack.getMin())
    stack.pop()
    // 100
    println(stack.getMin())

}

キューとは

キューは、FIFO(First In First Out)と呼ばれるデータ構造になります。
スタックは、後から挿入されたものから取り出されていましたが、
キューは最初に挿入したものが、最初に取り出されます。

イメージでいうと、レジの会計でしょうか。

例を見ていきましょう

数字を1,3,5の順でキューに挿入します。

1

3 1

5 3 1

次にこれらを取り出します。
最初に挿入した1から取り出されます。

5 3

5

以上です。

スタックとは

ブロックを上から積み重ねていくようなデータ構造のことを言います。

スタックのデータ構造はLIFO(last in first out)(後入れ先出し)です。

後入れ先出しというように、後から挿入したデータが最初に取り出されるデータ構造のこといいます。

例を見てきましょう

スタックの構造

スタックに以下の数字1,3,5を挿入していきます。挿入することをpushといいます。

push 1
1

push 3
3 1

push 5
5 3 1

スタックは順に積み重なる構造になるので、最初に挿入した1がデータ構造の最後に来ます。

次は、スタックに挿入されたデータを取り出して見ましょう。
スタックからデータを取り出すことをpopと言います。

pop
3 1

pop
1

再度データを挿入してみます。

push 7
7 1

push 9
9 7 1

挿入する場合は、先頭から挿入されるため、最初に挿入した1は
最後まで残ることになります。

文字列が回文かどうかを判定する

問題：与えられた文字列が回文かどうかを調べる関数を作成せよ

回文とは

上から読んでも下から読んでも同じである文字列のことをいいます。
例えば

abcba,abba

などです。

回文と判定するには

回文の文字列を見るとなんとなく想像できるかと思いますが、
奇数個の文字列が2個以上存在すると回文ではなくなってしまいます。
文字数に着目して、この条件が正しいかどうかチェックしましょう

奇数個の文字列

abcba abcdabd

これらの文字列は回文です。
法則に着目すると、奇数の数の文字が一つしかないことに気づきます。
では今度は偶数個の文字列です。

abcbca,abcdcbda

偶数個の回文には、偶数個の文字しか置けないことに気が付きます
よって奇数個の文字が2つ以上あるとき回文でないことが判定できます。

これらを踏んでのkotlinのサンプルコードです

kotlin

fun main(args : Array) {
    if(isPalindrome("eeffkabcabcdd")){
        println("回文です")
    }
    else{
        println("回文ではありません")
    }
}

// 回文かどうかチェックする
fun isPalindrome(str : String) : Boolean{
    var tables = getCharFrequencyTable("ababc")
    return !isOddNumOne(tables)
}

/**
 * 文字に対応する数値を返す
 * アルファベット以外なら-1を返す
 */
fun getCharNumber(c : Char) : Int{
    val a = Character.getNumericValue('a')
    val z = Character.getNumericValue('z')
    val charInt = Character.getNumericValue(c)
    // アルファベット範囲内
    if(charInt >= a && charInt <= z){
        return charInt - a
    }
    return -1
}

// 各文字が何個含まれるのかを保持する配列を返す
fun getCharFrequencyTable(str : String) : IntArray{
    var tables = IntArray(Character.getNumericValue('z') - Character.getNumericValue('a') + 1)
    for(c in str) {
        val charInt = getCharNumber(c)
        if(charInt != -1){
            tables[charInt]++
        }
    }
    return tables
}

// 奇数の文字数が複数ないか
fun isOddNumOne(tables : IntArray) : Boolean{
    var isOdd : Boolean = false
    for(num in tables){
        if(num % 2 != 0){
            if(isOdd){
                return false;
            }
            isOdd = true
        }
    }
    return false
}

同じ文字列かどうかを判定する

問題:2つの文字列があり、片方の文字列がもう片方を並べ替えたものになっているかどうかを判定するプログラムを書け

2つの文字列が同じ文字と文字数が使われていること(順列の性質)を利用します。

文字コード分の配列を整数型で確保して、片方の文字数を加算、
もう片方の文字列を減産し、各々の文字数が不一致ならば、違う文字列だと判断することができますね。

コードを見ていきましょう

kotlin

fun isPermutation(str1 : String,str2 : String) : Boolean {
    // 長さが違えば異なる文字列
    if(str1.length != str2.length){
        return false
    }
    // ascii仮定
    var letters = IntArray(128)
    for(char in str1){
        // 対応する文字コード数のindexを加算する
        letters[char.toInt()]++
    }

    // 一致チェック
    for(char in str2){
        letters[char.toInt()]--
        // ある文字数が多い場合一致しないことになる
        if(letters[char.toInt()] < 0){
            return false

        }
    }
    return true
}

文字コードをasciiと解釈しています

重複しない文字列

問題

入力されたUNICODE文字列が、重複する文字がないかどうか判定するプログラムを書く

ASCIIコードは128種類らしいので、文字列の長さが128を超えたとすると、重複していることになります。
128個と要素数が決まっているので、boolean型で配列を確保して判定するのが
すぐ思いつくやり方だろうか

kotlin

fun isUniqueChars(str: String): Boolean {
    if (str.length > 128) return false
    var charSet = BooleanArray(128);

    for (char in str) {
        var value: Int = char.toInt();
        if (charSet[value]) {
            return false
        }
        charSet[value] = true
        return true
    }
    return true
}

O-記法

O-記法は実行にかかる時間の目安として扱われます。

例えば、O(n)とすると、一時探索で見つかるような場合を指します。
プログラムにすると、

int answer[10];

for(int i = 0;answer < 10; n;++i){
    // 探索する
}

といった具合です

では、O(n^2)の場合では、どうなるかというと

int answer[10][100]

int anser[]
for(int i = 0;i < 10;++i){
    for(int j = 0;j < 100;j++){
    // 探索する
    }
}

といった具合にforの2重ループに相当します。

以下、O(n^3)の場合は、3重のfor... を意識していただければと、 以上です。