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

标签：

Author

祭音Myyura

Description

図 1 に示す ANSI-C 準拠である C 言語のプログラム (program) は所有している複数のくじ (lottery) のそれぞれが当選 (win) しているかを調べて、当選しているくじ番号 (lottery number) と等級 (grade) をもれなく出力 (output) するものである. くじ番号は 10000 未満の自然数 (natural number) で定められており, いずれのくじ番号のくじもたかだか一つしか存在しない. 所有しているくじ番号が、当選番号 (winning number) と一致した場合に、その当選番号に対応する等級に当選したとする. 当選番号は 10000 未満の自然数から重複なく選ばれた $N$ 個 ( $N$ は $3 \le N \le 100$ の自然数) の数字で, 等級は 1 等から 3 等まであり、1 等が 1 本、 2 等が 1 本、 3 等が $N - 2$ 本である.

当選番号と等級は図 2 に示すような形式 (format) のファイル win.txt で与えられ、1 行目に当選番号の総数 $N$ 、2 行目以降の $N$ 行は全ての当選番号とその等級 $r$ ( $r$ は $1 \le r \le 3$ の自然数) が書かれている. また、所有しているくじ番号は図 3 に示すような形式のファイル lots.txt で与えられ、所有しているくじ番号が 1 行目から各行に一つずつ書かれている. 以下の各問に答えよ.

(1) 図 2 の win.txt、図 3 の lots.txt を与えてプログラムを実行することを考える. プログラムの 36 行目で関数 functionA が呼び出されたときに、プログラム 6~13 行目の for 文処理において、i=1 および i=3 の時に、j に関する for 文が終了した時点で a[0] ~ a[9] および b[0] ~ b[9] の値が以下のようになった. 8 行目の空欄(A)を配列 a に関する適切な条件式で埋めよ.

	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]
i=1	5308	900	7888	3500	8	4905	8698	1328	89	9003
i=3	900	3500	8	4905	5308	1328	89	7888	8698	9003

	b[0]	b[1]	b[2]	b[3]	b[4]	b[5]	b[6]	b[7]	b[8]	b[9]
i=1	3	3	2	3	3	1	3	3	3	3
i=3	3	3	3	1	3	3	3	2	3	3

(2) 36 行目で呼び出された関数 functionA の処理によって、配列 win および配列 grade はどのようになるか、説明せよ、またその処理の平均時間計算量 (average case time complexity) を、変数 $n$ を用いて, オーダ表記 (order notation) で表わせ、その理由も答えよ. ただし、win.txt 内では、当選番号は無作為 (at random) な順序で並んでいる.

(3) 39 行目で呼び出された関数 functionB はどのような処理をしているのか、配列 win、変数 lot、変数 n を用いて説明せよ. また、関数の戻り値 (return value) についても言及すること.

(4) 4 ~ 14 行目で定義されている関数 functionA を以下のように変更することで、36 行目で functionA を実行する時の平均時間計算量を少なくすることを考える. 以下の各小問に答えよ.

void functionA(int a[], int b[], int t, int w) {
    if (t < w) {
        int i, j, x, tmp;
        i = t, j = w;
        x = a[t];

        while (1) {
            while (a[i] < x) i++;
            while (a[j] > x) j--;
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp; tmp = b[i]; b[i] = b[j]; b[j] = tmp;
            i++; j--;
        }

        functionA(a, b, 空欄(あ), 空欄(い));
        functionA(a, b, 空欄(う), 空欄(え));
    }
}

(4-1) 空欄(あ)~(え)に入るものの組み合わせとして、適切なものを下の (i) ~ (iv) から一つ選び、答えよ.

	(あ)	(い)	(う)	(え)
(i)	i-1	t	w	j+1
(ii)	t	j-1	i+1	w
(iii)	t	i-1	j+1	w
(iv)	j-1	t	w	i+1

(4-2) 関数 functionA の変更後の平均時間計算量を、変数 $n$ を用いて、オーダ表記で表わせ. ただし、win.txt 内では、当選番号は無作為な順序で並んでいる.

(5) 図 1 のプログラムを、下線 (ア) および下線 (イ) で示した main 関数中の関数 functionA の引数 (argument) と if 文の条件式のみを変更し、1 等に当選している場合にのみ、当選しているくじ番号と等級を出力するようにする. 当選番号と等級、および所有しているくじ番号は図 2 および図 3 と同じ形式で与えられる. 39 行目の下線 (イ) における判定を平均時間計算量 $O(1)$ で実現するためには、下線 (ア) および下線 (イ) をそれぞれどのように変更すればよいか，(ア) には適切な引数を、(イ) には適切な式をそれぞれ答えよ.

#include <stdio.h>
#define MAXN 100

void functionA(int a[], int b[], int t, int w) {
    int tmp, i, j;
    for (i = t+1; i <= w; i++) {
        for (j = t; j <= w-i; j++) {
            if ([   空欄(A)   ]) {
                tmp = a[j+1]; a[j+1] = a[j]; a[j] = tmp;
                tmp = b[j+1]; b[j+1] = b[j]; b[j] = tmp;
            }
        }
    }
}

int functionB(int a[], int x, int n) {
    int t, w, m;
    t = 0; w = n - 1;
    do {
        m = (t + w) / 2;
        if (x < a[m]) w = m - 1;
        else t = m + 1;
    } while (t <= w);
    if (w >= 0 && x == a[w]) return w;
    else return -1;
}

int main() {
    int n, i, k;
    FILE *fp;
    int win[MAXN], grade[MAXN], lot;
    fp = fopen("win.txt", "r");
    fscanf(fp, "%d", &n);
    for (i = 0; i < n; i++) fscanf(fp, "%d %d", &win[i], &grade[i]);
    fclose(fp);
    functionA(win, grade, 0, n-1);  // 下線 (ア): (win, grade, 0, n-1)
    fp = fopen("lots.txt", "r");
    while (fscanf(fp, "%d", &lot) != EOF) {
        if ((k = functionB(win, lot, n)) != -1) {  // 下線 (イ): (k = functionB(win, lot, n)) != -1
            printf("***winning number: %4d, grade: %d\n", lot, grade[k]);
        }
    }
    fclose(fp);
    return 0;
}

図１プログラム

図２ win.txt

図３ lots.txt

Kai

(1)

バブルソートなので、空欄は a[j] > a[j+1]。

(2)

win が昇順に整列し、grade も同じ交換を行うため、grade[i] は常に win[i] の等級を保持する。比較回数は

\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}2

なので、平均時間計算量は $\boxed{O(n^2)}$ 。

(3)

昇順の win[0]～win[n-1] に対して lot を二分探索する。等しい要素があればその添字を返し、なければ $-1$ を返す。

(4)

(4-1) $\boxed{\text{(iii)}}$ 、すなわち (t, i-1) と (j+1, w)。

(4-2) ランダムな入力順のクイックソートなので平均時間計算量は $\boxed{O(n\log n)}$ 。1回の分割は線形時間で、平均的な分割の深さが $O(\log n)$ となる。

(5)

/* (ア) */ (grade, win, 0, n-1)
/* (イ) */ lot == win[k = 0]

等級で昇順に整列すれば、唯一の1等が先頭になる。k=0 も設定することで、後続の grade[k] が正しく1を出力する。判定は $O(1)$ 。

Author​

Description​

図１ プログラム​

図２ win.txt​

図３ lots.txt​

Kai​

(1)​

(2)​

(3)​

(4)​

(5)​

Author

Description

図１プログラム

図２ win.txt

図３ lots.txt

Kai

(1)

(2)

(3)

(4)

(5)