ラベル algorithm の投稿を表示しています。 すべての投稿を表示
ラベル algorithm の投稿を表示しています。 すべての投稿を表示

2014年11月12日水曜日

DPについての講義を受けた記録(前編)

恥ずかしながら未だにDP(動的計画法)に慣れてないのでどうしたものかなと思っていたら「DPなら俺に任せろ。俺はDPの気持ちが分かる」という方が居られたのでそれならと知人と共に簡単な講義をお願いした。「ちょっと張り切って作ってみた」と聞いていたので少しビビりながらも当日に臨んだのでその記録。この内容は入門レベルなので読む必要ない人の方が多いはず。


導入


DPとはなんぞや


Wikipediaには以下の2つの条件を満たすものと書いてある。
  • 分割統治法
  • メモ化
しかし、講義内ではもう少し厳密さを入れたかったのか、ボトムアップに解いていく点も説明に含められていた。まとめると講義では、「部分問題をボトムアップに解いていく」、「同じ計算を二度実行しない」の二点が何度も繰り返された。

その後、フィボナッチ数列を例に説明が為された。


フィボナッチをDPで解く例

演習1(ロッド切り出し問題)


ロッド切り出し問題を使った演習。漸化式を見つけると言う分かりきった分かりにくいものだけではなく、部分最適構造性を見つけるということで含まれていたSchemeの例がわかりやすかった。

長さが5の時は、5, (4, 1), (3, 2)の3パターンだが、1から順に入力値までの最適解を求めながらループさせることになる。

コード例

演習2(LCS)


定番のLCSを使った演習。この漸化式見つけられるならそもそも困らないだろと皆がツッコみたいところである。仮定が大事という言葉にうまく丸め込まれた感は否めない。

仮定→漸化式→プログラム、という風に落としこんでいく感じは掴めた(気がする)。

コード例

所感


こういう機会を設けることに意味はあるが、仕事ではあまり使わない現実が悲しい。
久しぶりに書いたけど、Blogger使いづらい。

→DP講義(後編)は11/30開催予定

2013年12月15日日曜日

メタプログラミング本からプロコン本へ

メタプログラミングRubyを終えたので、この本を勉強会で進めている。

 

以前は第一版をRubyやPythonでやっていたのでC++で書いてる。以下は、今日やったところ。

2-1


DFS

  • 部分和問題
  • 水たまりカウント

BFS

  • 迷路問題


相変わらず面白いので今後も進める。

2013年9月23日月曜日

ビット演算の復習

月1ページでやってるプログラミングを楽しむ会で、ビット演算をもくもくしてた。というのもこの会ではここに在る通り普段やらないことを推奨されている。普段はRailsとかAWSなのでこういう時にちょうど良いネタ。

元ネタはこの本(↓)

 

2進→10進変換はBoostを使ってややさぼった。


こんな感じで。引き続き、ビット演算サンプル。


見たらわかると思うけど一応書く。
  • get_bit: 引数numの第iビットが0か1かを取得
  • set_bit: 引数numの第iビットに1をセット
  • clear_bit: 引数numの第iビットに0をセット


続いて、ある問題に対し考えた回答。
勝手に書いたらダメだと思うので問題は省略。
答え合わせもしてないから間違ってるかもしれないけどコードから問題は想像可能な筈。


非常に貴重な時間なのでこういう集まりは今後も大事にしたい。



2013年7月17日水曜日

[練習] ダイクストラアルゴリズム




バタバタしてたけど地味に進めてようやく終わり




シンプルなものが最も美しい

2013年7月5日金曜日

10パズル




この本もあと少し。
入力された4桁の数値を元にRPN式を生成し、それを解いて10になるか判定。
再帰だけでなくスタックの練習でもある。

2013年6月20日木曜日

バックトラック法(Eight Queens Puzzle)

徐々に終盤に近づいてきている。
 

ごく単純なアルゴリズム。
右側に駒が置かれていることが存在しないという前提で

  • 左側をチェック
  • 左上をチェック
  • 左下をチェック
分かりやすい。

2013年6月17日月曜日

[練習] 文字列探索アルゴリズム

昨日やった文字列内のパターン検索。grepを自分で実装する時とかに使う。


1. シンプルなアルゴリズム

1文字づつずらして見ていく方法。最も単純。


2. KMP法

1文字ずつずらすのではなくて、次に比較させる場所を記憶しておく。
アルゴリズムが複雑な分、実は1のシンプルなアルゴリズムの方が早い時もある。


3. BM法

現実的な早い方法。パターンを後ろから前に対象文字列と照合していく。


最近なかなか時間が取れないのが悩みどころ。

2013年5月28日火曜日

[練習] C++でハッシュマップ実装

ふと思い立って復習。ハッシュマップ。この本(↓)の7章。

 

最近はRailsアプリとjQuery使ってゴニョゴニョいじる系の仕事が多いので
却って直接関係無いと思えることに手をだしたくなるのが人情。

英語と日本語の対応を検索・削除・表示するC++プログラム



アーサーとリドじゃないけどPractice, Practice, Practice

2013年3月10日日曜日

二分探索木の基本

今日は、もくもくとプログラミングする会でツリー及び変更の実装を行った。
ここまで書き忘れていたが、最近のアルゴリズム勉強はこの本(↓)でやってる。

 

非常に良い書籍。
普段の業務ではこのような学習(復習)をする機会が少ないので
意図的に時間を費やしている。(C++に慣れることも副次的狙い)

ツリーのノードを表現する構造体
typedef struct tag_tree_node {
    int data;
    struct tag_tree_node *left;
    struct tag_tree_node *right;
} tree_node;


ノードの作成
tree_node* create_node(int data) {
    tree_node *new_node = (tree_node*)malloc(sizeof(tree_node));
    if (new_node == NULL) {
        exit(EXIT_FAILURE);
    }
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->data = data;
    return new_node;
}


ノードの挿入
void insert_node(int data, tree_node *node) {
    if (node == NULL){
        root_node = create_node(data);
        return;
    }
    if (node->data > data){
        if (node->left == NULL)
            node->left = create_node(data);
        else
            insert_node(data, node->left);
    } else {
        if (node->right == NULL)
            node->right = create_node(data);
        else
            insert_node(data, node->right);
    }
    return;
}


ノードの検索
tree_node* find_node(int data, tree_node *node) {
    if (node->data > data) {
        if (node->left == NULL)
            return NULL;
        return find_node(data, node->left);
    }
    if (node->data < data) {
        if (node->right == NULL)
            return NULL;
        return find_node(data, node->right);
    }
    return node;
}


ノードの削除
int delete_node(int data) {
    tree_node *node = root_node;
    tree_node *parent = NULL;
    tree_node *left_biggest;
    int dir = 0;

    while (node != NULL && node->data != data) {
        if (node->data > data) {
            parent = node;
            node = node->left;
            dir = -1;
        } else {
            parent = node;
            node = node->right;
            dir = 1;
        }
    }
    if (node == NULL)
        return 0;
    
    if (node->left == NULL || node->right == NULL) {
        if (node->left == NULL) {
            switch (dir) {
            case -1:
                parent->left = node->right;
                break;
            case 1:
                parent->right = node->right;
                break;
            case 0:
                root_node = node->right;
            }
        } else {
            switch (dir) {
            case -1:
                parent->left = node->left;
                break;
            case 1:
                parent->right = node->right;
                break;
            case 0:
                root_node = node->left;
            }
        }
        free(node);
    } else {
        left_biggest = node->left;
        parent = node;
        dir = -1;
        while (left_biggest->right != NULL) {
            parent = left_biggest;
            left_biggest = left_biggest->right;
            dir = 1;
        }
        node->data = left_biggest->data;
        if (dir == -1)
            parent->left = left_biggest->left;
        else
            parent->right = left_biggest->left;
        free(left_biggest);
    }
    return 1;
}


ノードの解放
void free_node(tree_node *node) {
    if (node == NULL)
        return;
    free_node(node->left);
    free_node(node->right);
    free(node);
}


ツリーの表示(雑だけど...)
void print_tree(int depth, tree_node *node, int dir) {
    int i;
    for (i = 0; i < depth; i++)
        cout << "  ";
    switch (dir) {
    case -1:
        cout << "L: ";
        break;
    case 1:
        cout << "R: ";
        break;
    }
    cout << node->data << endl;
    if (node->left != NULL)
        print_tree(depth + 1, node->left, -1);
    if (node->right != NULL)
        print_tree(depth + 1, node->right, 1);
}


メイン実装
int main() {
    srand((unsigned int)time(NULL));
    int i, ar[N];
    for (i = 0; i < N; i++) {
        ar[i] = rand() % 100 + 1;
        insert_node(ar[i], root_node);
    }
    // original
    print_tree(0, root_node, 0);

    // insert
    int insert = rand() % 100 + 1;
    cout << "---------- insert: " << insert << endl;
    insert_node(insert, root_node);
    print_tree(0, root_node, 0);

    // delete
    int del = ar[rand() % N];
    cout << "---------- delete: " << del << endl;
    delete_node(del);
    print_tree(0, root_node, 0);

    return EXIT_SUCCESS;
}




[追記]
前述のもくもくとプログラミングする会は最近大学院の同級生と始めたところ。
現時点では不定期なプライベートイベントだけど参加したい人がいれば連絡下さい。

2013年3月2日土曜日

配列とリスト


配列はメモリ上で連続しているので
array[0]やarray[5]のようなアクセスできる。
ただし、当然サイズを超えてアクセスするとエラーになる。

と思いきや手元のC++ではエラーにならなかった。
ここにある通り、


"It is left undefined what happens if you go out of bounds"

ということか。そういうもんなのか、意外。しかし

"there is no guarantee that it'll still work the next time you run the program."

とあるので意識して書く方が良い(当然)。

それは置いといて、今日も遊ぶ。
配列が一杯になったら2倍のサイズの配列を生成して中身を入れ替える。

int main() {
    int input, size, cnt;
    int *temp, *array;
    cnt = 0;
    size = 10;
    array = (int *)malloc(sizeof(int) * size);
    do {
        cout << "Input number you like (0 for finsh) ";
        cin >> input;
        array[cnt] = input;
        cnt++;
        if (cnt == size) {
            temp = (int *)malloc(sizeof(int) * size * 2);
            memcpy(temp, array, sizeof(int) * size);
            free(array);
            array = temp;
            size *= 2;
        }
    } while (input != 0);
    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

これを頻繁にやる場合には効率あまり良くない。ということでリストを考える。
リストはノードを連結したものということでノードはこんな構造体。

typedef struct tagListNode {
    struct tagListNode *prev;
    struct tagListNode *next;
    int data;
} ListNode;

prevは前ノードへのポインタ、nextは次ノードへのポインタ、dataはデータ。
次のコードは入力値を元にノードを作成し、リストへどんどん追加する。

   do {
        cout << "input new data (0 for end) : ";
        cin >> buf;
        if (buf) {
            newNode = (ListNode *)malloc(sizeof(ListNode));
            newNode->data = buf;
            newNode->next = NULL;

            if (lastNode != NULL) {
                lastNode->next = newNode;
                newNode->prev = lastNode;
                lastNode = newNode;
            } else {
                firstNode = lastNode = newNode;
                newNode->prev = NULL;
            }
        }
    } while (buf != 0);

そして、リストに入力値が含まれるか探索する。

    do {
        cout << "input search number (0 for end) : ";
        cin >> buf;
        if (buf) {
            for (thisNode = firstNode; thisNode != NULL; thisNode = thisNode->next) {
                if (thisNode->data == buf) {
                    cout << buf << " is found." << endl;
                }
            }
        }
    } while (buf != 0);

結局何が嬉しいのかという話。ポインタの付け替えを行えば良いだけなので値の追加や削除が簡単。厳密にはメモリーの解放が必要だけど。例えば、検索した値がリストに含まれる場合、最初のノードとする為のコード。例えば配列の自己組織化探索の例だと一番先頭に持ってくることは効率を悪くするが、リストだと効率を損なうこと無く実現できる。

    do {
        cout << "--- current sequence ---" << endl;
        for (thisNode = firstNode; thisNode != NULL; thisNode = thisNode->next) {
            cout << thisNode->data << " ";
            sum += thisNode->data;
        }
        cout << endl;

        cout << "input search number (0 for end) : ";
        cin >> buf;
        if (buf) {
            for (thisNode = firstNode; thisNode != NULL; prevNode = thisNode, thisNode = thisNode->next) {
                if (thisNode->data == buf) {
                    cout << buf << " is found." << endl;
                    if (thisNode != firstNode) {
                        prevNode->next = thisNode->next;
                        if (lastNode == thisNode)
                            lastNode = prevNode;
                        thisNode->next = firstNode;
                        firstNode = thisNode;
                    }
                    break;
                }
            }
            if (thisNode == NULL) 
                cout << buf << " is not found in list." << endl;
        }
    } while (buf != 0);

以上。

でもまさかこれ↓がコンパイルできて実行できるとは思わなかったな

#include 

using namespace std;

int main() {
    int *array = new int[3];
    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    array[3] = 3;
    array[4] = 4;
    array[5] = 5;
    for (int i = 0; i < 6; i++)
        cout << array[i] << endl;
    return 1;
}

2013年2月28日木曜日

サーチアルゴリズムおさらい

引き続きサーチアルゴリズムのおさらい + C++へ慣れる為の作業

# リニアサーチ O (N)
C++標準ライブラリのfind()はこれを使ってるらしい。
void linear_search(int s, vector<int> v) {
    cout << "search " << s << " ... ";
    int i;
    for (i = 0; i < v.size(); i++) {
        if (s == v.at(i)) {
            cout << "FOUND at " << i + 1 << endl;
            return;
        }
    }
    cout << "not FOUND" << endl;
}

# 番兵利用リニアサーチ O (N)
添字チェックを行わない。
void sentinel_search(int s, vector<int> v) {

    cout << "search " << s << " ... ";

    int i = 0, t = v[N - 1];
    v[N - 1] = s;

    while (v[i] != s)
        i++;

    if (i < N - 1) {
        cout << "FOUND at " << i + 1 << endl;
        return;
    }

    if (s == t) {
        cout << "FOUND at " << N << endl;
        return;
    }

    cout << "not FOUND" << endl;
}

# バイナリサーチ O (log N)
void binary_search(int t, int *array) {
    cout << "search " << t << endl;
    int l = 0, r = N-1, m;
    while (l <= r) {
        m = (l + r) / 2;
        if (array[m] == t) {
            cout << t << " found at " << m + 1 << endl;
            return;
        }
        if (array[m] < t) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    cout << "not found" << endl;
}

# バイナリサーチ改良版 O (log N)
同じ値が配列内で複数存在する場合に先頭の値を返す。
void binary_search(int t, int *array) {
    cout << "search " << t << endl;
    int l = 0, r = N-1, m;
    while (l < r) {
        m = (l + r) / 2;
        if (array[m] < t) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    if (array[l] == t) {
        cout << t << " found at " << l + 1 << endl;
        return;
    }
    cout << "not found" << endl;
}

# 自己組織化探索
見つかった値を1つ前へ移動する。
void organization_search(int t, int *array) {
    int i, tmp;
    while (array[i] != t && i < N)
        i++;
    if (i < N && 0 < N) {
        tmp = array[i];
        array[i] = array[i - 1];
        array[i - 1] = tmp;
    }
}

まだvector::iteratorの使い方に慣れてない...

ソートアルゴリズムおさらい

温泉でプログラミングしてたら
頭のなかに引っかかったことがあったので
ソートアルゴリズムのおさらいをした。

# バブルソート O (N^2) 安定
void bubble_sort() {
    int i, k, tmp;
    bool changed = false;
    k = 0;
    do {
        changed = false;
        for (int i = 0; i < MAX-1-k; i++) {
            if (array[i] > array[i+1]) {
                tmp = array[i];
                array[i] = array[i+1];
                array[i+1] = tmp;
                changed = true;
            }
        }
        k++;
    } while (changed);
}

# クイックソート O (N^2) ~ O (N log N) 不安定
void quick_sort(int bottom, int top,int data[]) {
    if (bottom >= top)
        return;
    int div = data[bottom];
    int lower = bottom;
    int upper = top;
    int temp;
    while (lower < upper) {
        while (lower <= upper && data[lower] <= div)
            lower += 1;
        while (lower <= upper && data[upper] > div)
            upper -=1;
        if (lower < upper) {
            temp = data[lower];
            data[lower] = data[upper];
            data[upper] = temp;
        }
    }
    temp = data[bottom];
    data[bottom] = data[upper];
    data[upper] = temp;
    quick_sort(bottom, upper-1, data);
    quick_sort(upper+1, top, data);
}

# 単純挿入ソート O (N^2) 安定
void insert_sort(int *array) {
    int i, sorted, temp, insert;
    for (sorted = 0; sorted < MAX - 1; sorted++) {
        insert = array[sorted + 1];
        for (i = 0; i <= sorted; i++) {
            if (array[i] > insert)
                break;
        }
        while (i <= sorted + 1) {
            temp = insert;
            insert = array[i];
            array[i] = temp;
            i++;
        }
    }
}

# コームソート O (N log N) 不安定
void comb_sort(int *array) {
    int i, tmp, sorted, gap;
    gap = N;
    do {
        gap = (gap * 10) / 13;
        if (gap == 0)
            gap = 1;
        
        sorted = true;
        for (i = 0; i < N - gap; i++) {
            if (array[i] > array[i + gap]) {
                sorted = false;
                tmp = array[i];
                array[i] = array[i + gap];
                array[i + gap] = tmp;
            }
        }
    } while((gap > 1) || !sorted);
}

# マージソート O (N log N) 安定
void merge_sort(int n, int* data, int offset) {
    if (n < 2)
        return;
    int i, j, k;
    int m = n/2;
    merge_sort(m, data, offset);
    merge_sort(n-m, data, offset+m);
    int buf[m];
    for (i = 0; i < m; i++)
        buf[i] = data[offset+i];
    j = m;
    i = k = 0;
    while (i < m && j < n) {
        if (buf[i] <= data[offset+j]) {
            data[offset+k] = buf[i];
            i++;
        } else {
            data[offset+k] = data[offset+j];
            j++;
        }
        k++;
    }
    while (i < m) {
        data[offset+k] = buf[i];
        k++;
        i++;
    }
}

あとはここの辺りを頼りにもう少し遊ぶ調べるか