ページ一覧

ページ内

課題１

課題１

今回は、演習時間も短いし、プログラミングなしの課題となっています。

有向グラフを深さ優先探索してみましょう。 プログラムはこちら(srcのみ)にあるので、プログラムの実行理解をしましょう。 ついでに、デバッガでプログラムがどのように動作しているか、しっかり追っかけられるようになりましょう。

まずは、データ構造。 struct node はグラフのノードを表し、フィールド s, t がノードへの参照を値として持つことは，そのノードから参照先ノードへのエッジ（edge）が存在することを示している（NULL値の場合は対応エッジはない）． id はノードの識別子であり， visited はノードの訪問回数を示す．

typedef struct node {
    struct node * s; 
    struct node * t;
    int id;
    int visited;
} node_t, * node_tp;

#define BUFSIZE 100
struct node nodes[BUFSIZE];

一方で、探索プログラムはこんな感じ。 再帰的に探索をおこなうが、１度たどったところは、２度以上探索しないようにしています。 エッジは、s → t の順で調べていきます。

void dfs(node_tp node) {
    //    node_tp s = node;
    node->visited++;
    printNode(node); // ノード表示用関数
    if(node->visited == 1) {
        node_tp s = node->s;
        node_tp t = node->t;
        if(s != NULL) dfs(s);
        if(t != NULL) dfs(t);
    }
}

で下記が、グラフを作成してから探索を行っている部分。

void initNodes(int n) {
    int i;
    for(i = 0; i<n; i++) {
        nodes[i].id = i; nodes[i].visited = 0;
        nodes[i].s = nodes[i].t = NULL;
    }
}
void link(node_tp node, node_tp s, node_tp t) {
    node->s = s; node->t = t;
}

void test1(void) { /* 2021 version */
    initNodes(4);
    link(&nodes[0], &nodes[2], &nodes[1]);
    link(&nodes[1], &nodes[2], &nodes[3]);
    link(&nodes[2], NULL, &nodes[3]);
    link(&nodes[3], &nodes[0], NULL);
    dfs(&nodes[0]); /* ノード 0 から探索 */
}

例えば、test1() の場合、以下のようなグラフができているはず。

kadai1_21.png

さて、以下が課題になります。

問題１

test1() を実行した際の実行結果を確認しましょう。

int main(void)  {
    test1();
    return 0;
}

その上で、関数の Call Stack がどのように変化しながらプログラム実行が進んでいたか、コメント風に記述しなさい。 冒頭部だけ書くと、こんな感じ。

(0, 1) // stack:0
(2, 1) // stack:0:2
(3, 1) // stack:0:2:3
(0, 2) // stack:0:2:3:0
(1, 1) // stack:0:1
(2, 2)
(3, 2)

// stack:.. の部分は、頭で考えてもらっても良いし、デバッガでprintNodes()に break point をいれて、調べても良いし、以下の option 課題を解くことで実現しても良いです。

オプション課題

上記 //stack:... 部分を自動で生成できるようにプログラムを拡張しなさい。 データ構造としての stack を自分で生成すれば OK です。

オプション課題なので、全員がとかなくても大丈夫。

問題２

こちらは、全員トライしましょう。

dfs 関数中の if 文を以下のように書き換えたとします。

void dfs(node_tp node) {
    //    node_tp s = node;
    node->visited++;
    printNode(node); // ノード表示用関数
    if(1) { // 変更点！ 常に then 節を実行
        node_tp s = node->s;
        node_tp t = node->t;
        if(s != NULL) dfs(s);
        if(t != NULL) dfs(t);
    }
}

つまり、同じノードを何度でも探索しなおすこととします。 このとき test2 を実行した際の nodes[10] の訪問回数は、どうなるでしょう？

void test2(void) {
    int i;
    initNodes(12);
    for(i=0; i<10; i++) 
	link(&nodes[i], &nodes[i+1], &nodes[i+2]);
    dfs(&nodes[0]); /* ノード 0 から探索 */
}

真面目に手でやると大変なんですが、実は、nodes[10] の訪問回数は fib(10) に一致します。 理由を考え、簡単に答えましょう。 ちなみに、fib(n) はフィボナッチ関数のことで、

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

で求まる関数とします。

課題提出

レポートは、plain text もしくは pdf で作成し、Beef　から提出してください。

オプション課題を解いた人は、プログラムも提出すること。

課題の提出期限は、10/22 にします。まあ、少しぐらい遅れても受けとりますが、課題２以降を考えると、引っ張らない方がよいでしょう。

Read more

課題 課題２