跳到主要内容

大阪大学 情報科学研究科 情報工学 2017年8月実施 アルゴリズムとプログラミング

标签：

Author​

祭音Myyura

Description​

図1に示す ANSI-C 準拠である C 言語のプログラム (program) は任意の 2 人が同じ組織 (organization) に所属するか判定し, その結果を出力 (output) するものである. 人(構成員(member)と呼ぶ)は NN 人 (NN は正の整数 (positive niteger)) 存在し, 各構成員には直属の上司 (direct supervisor) である構成員が 1 人以下 (1 or less) 存在する. 組織は一つ以上存在し, 各組織は, 各構成員を点 (ノード (node)), その直属の上司を親 (parent) とする木 (tree) で表される. 同じ組織に所属する構成員は, その組織の最上位の上司を根 (root) とする一つの木を構成する.

各構成員にはそれぞれ 0∼N−10 \sim N-1 の整数 (integer) が構成員番号として重複なく付与されている. 配列 (array) p は構成員番号 i である構成員の直属の上司の構成員番号を要素 (element) として p[i] に格納し, 直属の上司が存在しない場合は自身の構成員番号を格納する. このデータ構造を用い, 関数 same は 2 人の構成員番号を引数とし, 同じ組織に所属するかどうかを標準出力に出力する. input.txt, pair.txt という図 2 および図3にそれぞれ示すようなフォーマットのファイルが存在するものとし, 図 1 のプログラムでそれらを読み込み実行する. input.txt の 1 行目には構成員の総数 NN (NN は N_MAX 以下の正の整数), 2 行目以降の各行には, 構成員とその直属の上司の構成員番号のペア (pair) がこの順でかれている. pair.txt の各行には, 同じ組織に所属するか判定したい構成員のペアの構成員番号が書かれている. 以下の各問に答えよ.

(1) 図1のプログラムは, 図2の input.txt と図 3 の pair.txt を読み込み実行する. 以下の各小問に答えよ.

  • (1-1) 21 ~ 29 行目で読み込まれる全ての木を示せ, ただし図 4 にならい, 丸でノードを, 丸の中の数字で機成員番号を, 線で枝 (edge)を表すこと.
  • (1-2) find(x) が意味する内容を, xを用いて説明せよ.
  • (1-3) 14 行目の空欄 A に当てはまる式を, 15 行目の空欄 B に当てはまる条件式をそれぞれ書け.

(2) 非常に大きな数の構成員に対し, 多数の無作為に選ばれた構成員のペアのそれぞれが同じ組織に所属するか判定したい. そのため, このようなデータを含む input.txt および pair.txt を図 1 のプログラムで読み込み実行する, ただし, 図 1 のプログラム 2 行目の N_MAX の値を適切に変更するものとする. 以下の各小問に答えよ.

  • (2-1) 関数 same を実行する際の, 1 回当たりの平均時間計算量 (average time complexity) をオーダ表記 (order notation) で表せ, また理由も答えよ, ただし, ノードの平均の深さ (average depth) を hh とする.
  • (2-2) ここで, 関数 find の 9 行目を変更し, 最上位の上司を格納するように配列 p を更新することで, 実行時間を短縮できる場合がある. 以下に答えよ.
    • (2-2-1) 変更後の 9 行目を一文で書け.
    • (2-2-2) 関数 same を十分大きな回数実行した場合に漸近する, 1 回当たりの平均時間計算量をオーダ表記で表せ. また理由も答えよ.
#include <stdio.h>
#define N_MAX 1000
int p[N_MAX];

int find(int x) {
    if (p[x] == x)
        return x;
    else
        return find(p[x]);
}
void same(int x, int y) {
    int n, m;
    n = find(x);
    m = [   空欄 A   ];
    if ([   空欄 B   ])  /* 同じ組織に所属する */
        printf("%d & %d are in the same organization. \n", x, y);
    else
        printf("%d & %d are in different organization. \n", x, y);
}
int main(void) {
    FILE *fp;
    int n, i, j, sv;
    fp = fopen("input.txt", "r");
    fscanf(fp, "%d", &n);
    for (i = 0; i < n; i++)
        p[i] = i;
    while (fscanf(fp, "%d %d", &i, &sv) != EOF)
        p[i] = sv;
    fclose(fp);
    fp = fopen("pair.txt", "r");
    while (fscanf(fp, "%d %d", &i, &j) != EOF)
        same(i, j);
    fclose(fp);
    return 0;
}

図１ プログラム
​

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

図２ input.txt
​

9   7
6   4
0   2

図３ pair.txt
​

                                    (0)
                                  /     \
                                (1)     (2)
                                 |     /   \
                                (3)  (4)   (5)

図４ 木の表記例
​

题目描述​

图 1 的 ANSI C 程序判断任意两名成员是否属于同一组织。每名成员至多有一名直属上司；每个组织构成一棵以最高上司为根的树。成员编号为 00 至 N−1N-1，数组 p[i] 保存成员 i 的直属上司编号；根节点保存自身编号。find(x) 沿父指针查找根，same(x,y) 比较两人的根。

程序从 input.txt 读取成员总数与“成员—上司”对，再从 pair.txt 读取待判断成员对。示例文件、程序和树形记法见上文。

  1. 对给定输入：
    1. 画出程序读取到的所有组织树；
    2. 用 xx 说明 find(x) 的返回值含义；
    3. 填写 same 中空格 A 的函数调用和空格 B 的判断条件。
  2. 对成员数量极大、随机查询对很多的情形：
    1. 若节点平均深度为 hh，给出每次 same 的平均时间复杂度并说明理由；
    2. 把 find 改为路径压缩，使沿途 p 直接指向最高上司：
      • 写出修改后的递归返回语句；
      • 当 same 执行足够多次后，给出每次查询趋近的平均时间复杂度并说明原因。

考点​

  • 有根森林表示：用父指针数组表示多个组织树。
  • 并查集查找：沿父节点找到集合代表元，并通过代表元判断同属关系。
  • 路径压缩：递归返回时把访问路径上的节点直接挂到根。
  • 复杂度分析：比较普通父链查找的 O(h)O(h) 与大量压缩后接近常数的查询代价。

Kai​

(1)​

(1-1)​

            (0)                         (1)
             |                        /     \
            (2)                     (3)     (7)
                                  /     \
                                (4)     (6)
                                 |
                                (8)
                                 |
                                (9)

(1-2)​

Function find(x) recursively find x's parent until p[x] = x, which finally find the root of inital input x.

(1-3)​

  • 空欄 A: find(y)
  • 空欄 B: n == m

(2)​

(2-1)​

Let xx be a node of a tree TT. Since the length of path from xx to the root of TT is exactly the depth of xx in TT, we know that for a node in TT of depth kk, function find takes O(k)O(k) to find the root.

Therefore, if the average depth of node is hh, the average time complexity of function same is O(h)O(h).

(2-2-1)​

return p[x] = find(p[x])

(2-2-2)​

O(1)O(1)

After calling function same a sufficiently large number of times, almost all the parent of nodes will be modified to root, i.e. the average depth of nodes converges to 11.

本页目录