お茶の水女子大学人間文化創成科学研究科理学専攻情報科学コース 2017年8月実施情報基礎問題1

标签：

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

以下は、char 型の文字の配列 table に入っている $n$ 個の文字 table[1] から table[n] を昇順に整列する C 言語で書かれたプログラムの一部である。関数 sort は内部で関数 insert を使っている。char 型の値の間には、アルファベット順に 'a' < 'b' < ... という大小関係が定義されている。また、各行の行頭に行番号を付してある。

void insert(char w, int j) {
    if (j > 1 && w < table[j-1]) {
        table[j] = table[j-1];
        insert(w, j-1);
    } else {
        table[j] = w;
    }
}
void sort(int i) {
    if (i > 1) {
        sort(i-1);
        insert(table[i], i);
    }
}

関数 insert および sort の動作の概要をそれぞれ説明せよ。
関数 sort を引数 $1$ で呼び出す、すなわち sort(1) を実行すると何が起こるか。
$n=7$ で、配列 table の初期状態が table[0] から順に
```
i:         0 1 2 3 4 5 6 7
table[i]:  ? s e r v i c e
```
であったとする。ここで table[0] の値は不定である。このとき sort(7) を呼び出すと、その後 $11$ 行目で sort 自身が何度も再帰的に呼び出される。sort が呼び出されるたびに、その引数 $i$ の値を呼び出される順に書き下せ。sort(7) を $1$ 回目と数えると、最終的に何回 sort は呼び出されるか。
(3) で求めた sort の再帰呼出しのうち、最後の再帰呼出しである sort(1) が終了すると、次に $12$ 行目で insert が呼び出される。このときの insert の引数 $w$ と $j$ の値は何か。
(4) で insert が呼び出されるまでは table への代入は行われていないので、この時点での table の状態は (3) に示したままである。(4) の insert の呼出しを実行すると、 $3$ 行目の代入文は何回実行されるか。
(4) の insert の呼出しが終了した時点での table の内容を書き下せ。
同様に、その後 $12$ 行目で insert が呼び出されるたびに引数 $w$ と $j$ の値を順に書き下せ。さらに、各 insert の呼出しが終了した時点での table の内容も書き下せ。ただし、 $4$ 行目の再帰呼出し終了時は書き下さなくてよい。
(3) の sort(7) の呼出しを行うと、結局、合計で $3$ 行目の代入文は何回実行されるか。
一般に、整列するデータ数が $n$ だったとき、 $3$ 行目の代入文は最大で何回、最小で何回実行されるか。 $n$ を使って表せ。また、それぞれどのような場合か説明せよ。
このプログラムの計算量はいくらか。 $n$ を使って表せ。
関数 insert および sort の停止性をそれぞれ議論せよ。
番兵を使うことで、 $2$ 行目の if 文の条件のうち j > 1 を削除したい。どのように関数 insert を変更すればよいか、具体的に示せ。
このプログラムが正しいこと、すなわち、整列するデータ数が $n$ だったとき sort(n) の実行後は配列 table[1] から table[n] が昇順に並んでいることを示せ。

题目描述

给定一段以递归实现的插入排序程序：解释两个函数，追踪 service 的递归调用、参数、数组状态和移动次数；分析最好/最坏次数、复杂度与终止性；用哨兵改写边界判断，并证明程序正确。

Kai

(1)

insert(w,j) は、昇順に整列済みの table[1..j-1] に w を挿入する。w より大きい要素を一つずつ右へ移し、適切な位置に w を置く。

sort(i) はまず sort(i-1) で先頭 $i-1$ 個を整列し、次に table[i] をそこへ挿入する。したがって再帰的な挿入ソートである。

(2)

i > 1 が偽なので何も行わず、直ちに終了する。

(3)

呼出しは

\operatorname{sort}(7),\operatorname{sort}(6),\ldots,\operatorname{sort}(1)

であり、合計 $\boxed{7\text{ 回}}$ である。

(4)

sort(2) の第 $12$ 行から呼ばれるので

\boxed{w=\mathtt{'e'},\quad j=2}.

(5)

e < s なので s を一度右へ移す。したがって第 $3$ 行は $\boxed{1\text{ 回}}$ 実行される。

(6)

終了時は

e s r v i c e

である。

(7)

第 $12$ 行からの最上位の呼出しだけを順に示す。

$w$	$j$	呼出し終了時の `table[1..7]`
`r`	3	`e r s v i c e`
`v`	4	`e r s v i c e`
`i`	5	`e i r s v c e`
`c`	6	`c e i r s v e`
`e`	7	`c e e i r s v`

(8)

第 $3$ 行の実行回数は入力列の転倒数に等しい。service の転倒数は

5+1+3+3+2+0=\boxed{14}

である。

(9)

\boxed{0\le N_3\le\frac{n(n-1)}2}.

最小値 $0$ は初めから昇順の場合、最大値 $n(n-1)/2$ は全要素が相異なり降順の場合に達する。

(10)

最悪時間計算量は $\boxed{\Theta(n^2)}$ 、最良時間計算量は $\Theta(n)$ である。相異なる入力の順列が一様に与えられるとき、平均時間計算量も $\Theta(n^2)$ となる。再帰呼出しに使う補助領域は $O(n)$ である。

(11)

insert が再帰するとき $j$ は必ず $1$ 減少し、 $j=1$ では条件が偽になるので停止する。sort でも再帰ごとに $i$ が $1$ 減少して $i=1$ に到達し、その後に呼ぶ有限個の insert も停止する。ゆえに両関数は停止する。

(12)

table[0] に挿入対象自身を番兵として置けばよい。

void insert(char w, int j) {
    table[0] = w;
    if (w < table[j - 1]) {
        table[j] = table[j - 1];
        insert(w, j - 1);
    } else {
        table[j] = w;
    }
}

$j=1$ では w < table[0]、すなわち w < w が偽となるので、配列外へ進まない。

(13)

$i$ に関する帰納法で示す。 $i=1$ では明らかである。sort(i-1) の終了後に table[1..i-1] が昇順であると仮定する。

insert(table[i],i) は、挿入値 $w$ より大きい末尾要素だけを右へ移し、残った要素の直後に $w$ を置く。したがって要素の多重集合を変えずに table[1..i] を昇順にする。帰納法により sort(n) の終了後、table[1..n] は昇順である。

Author​

Description​

题目描述​

Kai​

(1)​

(2)​

(3)​

(4)​

(5)​

(6)​

(7)​

(8)​

(9)​

(10)​

(11)​

(12)​

(13)​