東京科学大学大学院情報理工学院 2020 問題三 / 科学大院理工学 2020 問題三

📢 この記事は gemini-2.5-flash によって翻訳されました

問題一： https://blog.yexca.net/archives/198
問題二： https://blog.yexca.net/archives/201
問題三：この記事
問題四： https://blog.yexca.net/archives/202
問題五： https://blog.yexca.net/archives/203

はじめに

この解答はアルゴリズムの問題だよ。最初見たときは、もうダメだって諦めそうになったんだけど、一度やってみたら、そこまで難しくないって感じたんだ。ただ、既存のアルゴリズムに対する高い理解力は必要だね。なんで難易度がそこまで高くないって言ったかというと、たぶん僕の心の準備というか、期待値と関係してるかも。だって、なんか新しいアルゴリズムを設計しなきゃいけないのかなって思ってたからさ (僕が言いたいのは、この問題が簡単だとは思ってないってことね)

問題の著作権は東京科学大学に帰属するよ。閲覧しやすくするために引用しただけで、営利目的ではないからね。

1

ｎ個の要素からなる整数の配列aを昇順に整列させる処理を、二つの異なるアルゴリズムに基づきＣ言語で実装した。プログラム3.1、3.2のキャプションＡ、Ｂを埋めるのに最も適切なアルゴリズムの名称を選択肢から選び、その記号を答えよ。

「選択肢」

ア　選択ソート

イ　バブルソート

ウ　クイックソート

エ　挿入ソート

プログラム3.1：A

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void sort_a(int a[], int n)
{
    int i, j, tmp;
    for(i=0; i<n-1; ++i){
        for(j=n-1; i<j; --j){
            if(a[j]<a[j-1]){
                tmp=a[j];
                a[j]=a[j-1];
                a[j-1]=tmp;
            }
        }
    }
}

プログラム3.2：B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void sort_b(int a[], int n)
{
    int i, j, tmp;
    for(j=1; j<n; ++j){
        tmp=a[j];
        i=j-1;
        while(0<=i && tmp<a[i]){
            a[i+1]=a[i];
            --i;
        }
        a[i+1]=tmp;
    }
}

解答

この問題は、2つのソートアルゴリズムのコードを見て、どのソート方法が使われているかを判断するものだね。Aはバブルソート（イ）、Bは挿入ソート（エ）だよ。

2

ヒープソートに関して、次の問いに答えよ。ただし、ｎは正の整数とする。

a）二分ヒープにおいて、根以外の任意の節点の値が満たすべき条件を説明せよ（maxヒープ条件とminヒープ条件のどちらでもよい）

b）二分ヒープがｎ個の要素を格納しているとき、その木の高さをｎの式で表せ。なお、木の高さは、根と葉を結ぶ路の長さの最大値として定義される

c）ヒープソートでｎ個の要素を整列させるとき、その平均時間計算量と最悪時間計算量の漸近的評価として、最も適切なものを以下の選択肢からそれぞれ答えよ

ア　$O(1)$

イ　$O(\log n)$

ウ　$O(n)$

エ　$O(n\log n)$

オ　$O(n^2)$

この問題はヒープソートについてだよ。1問目は、根以外の任意の節点の値が満たすべき条件（最大ヒープか最小ヒープのどちらかを選ぶ）を書くんだ。2問目は、構築されるヒープの二分木の高さを書くよ。3問目は、平均時間計算量と最悪時間計算量を選ぶんだ。

解答

最大ヒープ条件：根以外の任意の節点の値は、その親の値以下である必要がある。
最小ヒープ条件：根以外の任意の節点の値は、その親の値以上である必要がある。

$$ \left \lfloor \log_2n \right \rfloor $$

平均時間計算量と最悪時間計算量: エ　$O(n\log n)$

3

$A=\{ A[0], A[1], \cdots, A[n-1] \}$ をｎ個の相異なる整数の配列とする。ｎ未満の非負整数 $i,j$ に対し、$i\lt j$ かつ $A[i]\gt A[j]$ のとき、対 $(i,j)$ をAの反転と呼ぶ、Aの反転の数をAの反転数と呼ぶ。例えば、配列 $\{ 5,7,4,6 \}$ の反転は $(0,2),(1,2),(1,3)$ であり、反転数は3である。次の問いに答えよ。

a）配列 $\{ 1,0,4,3,2, \}$ の反転数を求めよ。

b）集合 $\{ 1,2,\cdots,n \}$ の要素をすべて並べた配列（要素数はｎ個）の中で、反転数が最大となるものを示せ。また、その反転数をｎの式で表せ。

c）集合 $\{ 1,2,\cdots,n \}$ の要素をすべて並べた任意の配列B（要素数はｎ個）をバブルソートで昇順に整列させる。このとき、「バブルソートにおけるＸと配列Ｂの反転数は等しい」という関係が成り立つ。Ｘを埋めるのに適切な語句と、その関係が成り立つ理由を簡潔に答えよ。

この問題ではまず「反転」の概念が導入されてるね ( 宋浩先生の線形代数の授業で話があったよ)。1問目は反転数を求めるんだ。2問目は最大の反転数を求めるんだね。3問目は、バブルソートの何が反転数と等しくなるか、その理由とともに答えるんだ。

解答

反転数は4だよ。(1,0), (4,3), (4,2), (3,2)の4組だね。

最大の反転数になるのは、配列がこう並んだ時だね。

$$ \{ n, n-1, n-2, \cdots, 2, 1 \} $$

n個の要素はn-1個と、n-1個の要素はn-2個と、という具合に続くね。反転数自体はその合計になるよ。

$$ (n-1)+(n-2)+\cdots+2+1+0=\frac{n(n-1)}{2} $$

X：交換回数

理由：スワップが反転を1つ解消する操作であるため

バブルソートは2つの要素を比較して、順序が間違っていたら交換するよね。1回の操作で1つの反転を解消するってことなんだ。

4

プログラム3.3は、整数の配列を昇順に整列させる処理を、マージソートのアルゴリズムに基づき、C言語で実装したものである、次の問いに答えよ。

プログラム3.3：マージソート

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int mergesort(int a[], int begin, int end, int w[]){
    int mid = (begin+end)/2;
    int i = begin, j = mid+1, k, c=0;
    
    printf("(%d, %d)\n", begin, end);
    if(begin<end){
        mergesort(a, begin, mid, w);
        mergesort(a, mid+1, end, w);
        
        for(k=begin; k<=end; ++k){
            if(mid<1){
                A
            }else if(end<j){
                B
            }else{
                /* ++c */
                if(a[i]<a[j]){
                    C
                }else{
                    D
                }
            }
        }
        for(k=begin; k<=end; ++k){
            E
        }
    }
    return 0;
}

a）空欄A、B、C、D、Eを埋めるのに適切なコードを、選択肢から選び、プログラムを完成させよ。ただし、整列させたい配列をa整列時の作業領域に用いる配列をｗとし、mergesort 関数を以下の2行のコードで呼び出すこととする。

1
2
int a[5] = {3, 5, 1, 4, 2}, w[5];
mergesort(a, 0, 4, w);

選択肢

$$ \begin{matrix} ア. a[k]=w[i] & イ. a[k]=w[i++] & ウ. a[k]=w[++i] \\ エ. a[k]=w[j] & オ. a[k]=w[j++] & カ. a[k]=w[++j] \\ キ. a[k]=w[k] & ク. a[k]=w[k++] & ケ. a[k]=w[++k] \\ コ. w[k]=a[i] & サ. w[k]=a[i++] & シ. w[k]=a[++i] \\ ス. w[k]=a[j] & セ. w[k]=a[j++] & ソ. w[k]=a[++j] \\ タ. w[k]=a[k] & チ. w[k]=a[k++] & ツ. w[k]=a[++k] \end{matrix} $$

b）a）に示したコードで mergesort 関数を呼び出したとき、標準出力の1行目に $(0,4)$ が書き出される。3行目、5行目、7行目に書き出される内容をそれぞれ答えよ。

c）mergesort 関数が引数で指定された範囲の配列の要素を整列させるまでにプログラム3.3の18行目を実行した回数の総数（要素の比較回数）を求めたい。そこで、17行目を（コメントアウトを外して）++c; に変更したが、これだけでは不十分である。以下の2行のコードで比較回数を変数 count に格納するには、プログラム3.3をどうのように変更すればよいか答えよ。

1
2
int a[5] = {3, 5, 1, 4, 2}, w[5];
int count = mergesort(a, 0, 4, w);

ただし、大域変数や静的変数を使っていけない。また、17行目の変更に加えて行うプログラムの変更は3回までの行の差し替えに限定する。行の差し替えとは、ある行のコードを60文字以内（空白文字は数えない）の別のコードに置き換えることを指す。解答の際は、以下の「答案の書き方（例）」のように、変更する行の番号と差し替え後のコードを記すこと。17行目のコメントは外してあることとし、それ以外に必要な変更を記述すること。

「答案の書き方（例）」

6行目：printf("hello\n");

30行目：c= end - begin + 1;

解答

A: w[k] = a[j++]; 即セ
B: w[k] = a[i++]; 即サ
C: w[k] = a[i++]; 即サ
D: w[k] = a[j++]; 即セ
E: a[k] = w[k]; 即キ

3 行目: (0,1)
5 行目: (1,1)
7 行目: (3,4)

8 行目: c += mergesort(a, begin, mid, w);
9 行目: c += mergesort(a, mid + 1, end, w);
31 行目: return c;

この問題、最初見たときはちょっとビビっちゃったんだけど、よく読んでみたら、出題内容はまあまあいける感じだったよ。マージソートを理解していれば、結構簡単に解けるんじゃないかな。ちなみに、僕もうアルゴリズムのことほとんど忘れかけてたし、前はアニメーションで（直感的に分かりやすいからね）理解してたんだけど、問題解いてるときに、いい感じのアニメーションアルゴリズムサイトを見つけられたのはラッキーだったよ。