大阪大学 情報科学研究科 情報工学 2017年8月実施 アルゴリズムとプログラミング
Author
祭音Myyura
Description
図1に示す ANSI-C 準拠である C 言語のプログラム (program) は任意の 2 人が同じ組織 (organization) に所属するか判定し, その結果を出力 (output) するものである.
人(構成員(member)と呼ぶ)は
各構成員にはそれぞれ
(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) を
とする. - (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;
}
図1 プログラム
10
2 0
3 1
4 3
6 3
7 1
8 4
9 8
図2 input.txt
9 7
6 4
0 2
図3 pair.txt
(0)
/ \
(1) (2)
| / \
(3) (4) (5)
図4 木の表記例
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 find
takes
Therefore, if the average depth of node is same
is
(2-2-1)
return p[x] = find(p[x])
(2-2-2)
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