問題一：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;
}
}
解答
这个题目就是对两个排序算法的代码，判断使用了什么排序方法。A 是冒泡排序 (イ バブルソート)，B 是插入排序 (エ 挿入ソート)
2
ヒープソートに関して、次の問いに答えよ。ただし、ｎは正の整数とする。
a）二分ヒープにおいて、根以外の任意の節点の値が満たすべき条件を説明せよ（maxヒープ条件とminヒープ条件のどちらでもよい）
b）二分ヒープがｎ個の要素を格納しているとき、その木の高さをｎの式で表せ。なお、木の高さは、根と葉を結ぶ路の長さの最大値として定義される
c）ヒープソートでｎ個の要素を整列させるとき、その平均時間計算量と最悪時間計算量の漸近的評価として、最も適切なものを以下の選択肢からそれぞれ答えよ
ア $O(1)$
イ $O(\log n)$
ウ $O(n)$
エ $O(n\log n)$
オ $O(n^2)$
这题考堆排序，第一问写出除了根节点以外的任意节点的值需要满足什么条件 (二叉树大顶堆或者小顶堆选一个)；第二问是写出构成的堆的二叉树的高度；第三问就是选择平均时间复杂度和最坏情况复杂度
解答
a
- 最大ヒープ条件：根以外の任意の節点の値は、その親の値以下である必要がある。
- 最小ヒープ条件：根以外の任意の節点の値は、その親の値以上である必要がある。
b
\[\left \lfloor \log_2n \right \rfloor\]c
平均時間計算量と最悪時間計算量: エ $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（要素数はｎ個）をバブルソートで昇順に整列させる。このとき、「バブルソートにおけるＸと配列Ｂの反転数は等しい」という関係が成り立つ。Ｘを埋めるのに適切な語句と、その関係が成り立つ理由を簡潔に答えよ。
这题首先引入了“逆序”的概念 (宋浩老师的线性代数课程有讲)，问题一求逆序；问题二求最大逆序；问题三写出冒泡排序的什么和逆序数是相等的，并给出理由
解答
- a
逆序数为 4，分别为 (1,0), (4,3), (4,2), (3,2)
- b
最大的逆序数是当排列为
\[\{ 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}\]- c
X：交換回数
理由：スワップが反転を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);
- 選択肢
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
- 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];即 キ
b
-
3 行目:
(0,1) -
5 行目:
(1,1) -
7 行目:
(3,4)
c
-
8 行目:
c += mergesort(a, begin, mid, w); -
9 行目:
c += mergesort(a, mid + 1, end, w); -
31 行目:
return c;
这题乍一看是挺唬人的，但仔细阅读后发现考的内容倒是还行，理解了归并排序后倒是可以比较容易解出来。顺便因为我已经快忘完了算法，又之前都是看动画理解 (比较直观)，解题时得幸发现了不错的动画算法网站