中央大学 理工学研究科 情報工学専攻 2025年8月実施 一般入試 問題II

标签：

• 中央大学
• 归并排序
• 递推关系的复杂度分析

Author

祭音Myyura (Based on 中央大学の公式解答例 refined with GPT 6 Astra)

Description

問題Iは必答。問題II〜Vのうち、2問を選んで解答すること。

問題II

下のアルゴリズム1は、2つの単調非減少な数列から別の数列を作成し出力する。

アルゴリズム1

入力．単調非減少な数列 $a=(a_1,a_2,\ldots,a_n)$ と $b=(b_1,b_2,\ldots,b_m)$

出力．数列 $c$

1. $i$ と $j$ をどちらも1とし、$c$ を空の数列とする。

2. $a_i\le b_j$ ならば $c$ の末尾に $a_i$ を加え、$i$ の値を1増やす。$a_i>b_j$ ならば $c$ の末尾に $b_j$ を加え、$j$ の値を1増やす。

3. $i>n$ ならば、$c$ の末尾に $b_j,\ldots,b_m$ を順番通りに加えた後に、$c$ を出力して終了。$j>m$ ならば、$c$ の末尾に $a_i,\ldots,a_n$ を順番通りに加えた後に、$c$ を出力して終了。それ以外ならば、ステップ2に戻る。

4. $a=(3,5,7,10,15)$、$b=(2,7,11,18,21)$ に対してアルゴリズム1を実行したときに出力される数列と、ステップ2が何回実行されるか答えなさい。

5. 入力の数列の長さが $n$ と $m$ の場合のアルゴリズム1の計算量を、$n$ と $m$ のオーダーで表しなさい。

次のアルゴリズム2は、数列 $x$ を並び替えて単調非減少な数列 $y$ を作成する。ただし、$x$ の長さは2の累乗である（つまり、非負整数 $d$ を用いて $2^d$ と表される）と仮定している。

アルゴリズム2

入力．数列 $x=(x_1,x_2,\ldots,x_k)$（$k$ は2の累乗）

出力．単調非減少な数列 $y=(y_1,y_2,\ldots,y_k)$

1. $k=1$ ならば数列 $x$ をそのまま数列 $y$ として出力して終了。$k\ge2$ ならば、以下のステップ2以降を実行する。
2. $a$ を数列 $(x_1,\ldots,x_{k/2})$、$b$ を数列 $(x_{(k/2)+1},\ldots,x_k)$ とする。
3. 数列 $a$ を入力としてアルゴリズム2を再帰呼び出し、出力された数列 $a'$ を得る。
4. 数列 $b$ を入力としてアルゴリズム2を再帰呼び出し、出力された数列 $b'$ を得る。
5. 数列 $a'$ と数列 $b'$ を入力としてアルゴリズム1を実行し、出力された数列 $y$ を得る。数列 $y$ を出力して終了。

例えば数列 $x=(2,1)$ を入力としてアルゴリズム2を実行すると全部で2回の再帰呼び出しが行われる。最初の呼び出しでは数2のみからなる数列 $(2)$、2回目の呼び出しでは数1のみからなる数列 $(1)$ が入力される。

3. 数列 $x=(3,1,4,2)$ を入力としてアルゴリズム2を実行した際には、全部で何回再帰呼び出しが行われるか答えなさい。また、それぞれの再帰呼び出しでの入力はどのような数列であるか答えなさい。解答の際は、どの数列が何回目の再帰呼び出しの入力か分かるように答えること。

4. 長さ $k$ に対する数列に対するアルゴリズム2の計算量 $f(k)$ が $k\ge2$ のときに満たす漸化式を与えなさい。アルゴリズムの細部について必要に応じて仮定を置いてもいいが、その場合はそれについて説明すること。

5. 小問4で与えた漸化式を元に、アルゴリズム1の計算量 $f(k)$ を $k$ のオーダーで表しなさい。結論だけではなく、説明も与えること。

题目描述

问题 I 必答。从问题 II～V 中选择两题作答。

问题 II

下面的算法 1 从两个单调不减数列生成并输出另一个数列。

算法 1

输入：单调不减数列 $a=(a_1,a_2,\ldots,a_n)$ 和 $b=(b_1,b_2,\ldots,b_m)$。

输出：数列 $c$。

1. 将 $i,j$ 均设为 1，将 $c$ 设为空数列。

2. 若 $a_i\le b_j$，则将 $a_i$ 追加到 $c$ 的末尾，并将 $i$ 增加 1；若 $a_i>b_j$，则将 $b_j$ 追加到 $c$ 的末尾，并将 $j$ 增加 1。

3. 若 $i>n$，则将 $b_j,\ldots,b_m$ 依次追加到 $c$ 的末尾，输出 $c$ 并结束；若 $j>m$，则将 $a_i,\ldots,a_n$ 依次追加到 $c$ 的末尾，输出 $c$ 并结束。否则返回步骤 2。

4. 对 $a=(3,5,7,10,15)$、$b=(2,7,11,18,21)$ 执行算法 1，给出输出数列及步骤 2 的执行次数。

5. 当两个输入数列的长度分别为 $n,m$ 时，用 $n,m$ 的阶表示算法 1 的计算复杂度。

下面的算法 2 对数列 $x$ 进行排序，生成单调不减数列 $y$。假定 $x$ 的长度为 2 的幂，即可写为 $2^d$，其中 $d$ 为非负整数。

算法 2

输入：数列 $x=(x_1,x_2,\ldots,x_k)$，其中 $k$ 是 2 的幂。

输出：单调不减数列 $y=(y_1,y_2,\ldots,y_k)$。

1. 若 $k=1$，则直接将 $x$ 作为 $y$ 输出并结束。若 $k\ge2$，则执行以下步骤 2 及后续步骤。
2. 令 $a=(x_1,\ldots,x_{k/2})$，$b=(x_{(k/2)+1},\ldots,x_k)$。
3. 以 $a$ 为输入递归调用算法 2，得到输出数列 $a'$。
4. 以 $b$ 为输入递归调用算法 2，得到输出数列 $b'$。
5. 以 $a',b'$ 为输入执行算法 1，得到数列 $y$，输出 $y$ 并结束。

例如，以 $x=(2,1)$ 为输入执行算法 2，共进行两次递归调用。第一次调用的输入是只含 2 的数列 $(2)$，第二次调用的输入是只含 1 的数列 $(1)$。

3. 以 $x=(3,1,4,2)$ 为输入执行算法 2，总共进行多少次递归调用？依调用顺序列出每次递归调用的输入数列，使各数列与调用次数的对应关系清晰。

4. 写出算法 2 对长度为 $k$ 的数列进行处理时，其计算复杂度 $f(k)$ 在 $k\ge2$ 时满足的递推式。必要时可对算法细节作出假设，但须说明假设内容。

5. 根据第 4 问中的递推式，用 $k$ 的阶表示算法 1 的计算复杂度 $f(k)$。除结论外，也须说明推导过程。

Kai

1.

ステップ2で取り出す要素を順に並べると

$$2_b,\ 3_a,\ 5_a,\ 7_a,\ 7_b,\ 10_a,\ 11_b,\ 15_a$$

となる。添字は元の数列を表す。8回目で数列 $a$ を使い切り、残った $18,21$ はステップ3で追加される。よって

$$\boxed{c=(2,3,5,7,7,10,11,15,18,21)},\qquad \boxed{\text{ステップ2の実行回数}=8}.$$

2.

要素の比較と末尾への追加をそれぞれ定数時間とする。各要素はちょうど1回出力され、ステップ2での比較回数は高々 $n+m-1$。残りの要素を追加する処理も含め、

$$\boxed{O(n+m)}$$

である。全 $n+m$ 要素を実際に出力するため、より厳密には $\Theta(n+m)$ となる。

3.

最初の呼び出し自体は再帰呼び出しに数えない。左半分を再帰的に処理し終えてから右半分へ進むので、順序は次のとおり。

再帰呼び出しの順番	入力数列
1	$(3,1)$
2	$(3)$
3	$(1)$
4	$(4,2)$
5	$(4)$
6	$(2)$

したがって再帰呼び出しは $\boxed{6\text{ 回}}$。

4.

長さ $k/2$ の部分列に対する再帰呼び出しが2回あり、その後に長さの合計が $k$ のマージを行う。部分列の分割・コピーに要する時間を高々 $O(k)$、比較・要素の追加を定数時間とすれば、

$$\boxed{f(k)=2f(k/2)+\Theta(k)\quad(k\ge2),\qquad f(1)=\Theta(1)}.$$

従って $f(k)=2f(k/2)+O(k)$ と書いてもよい。末尾への追加は、毎回配列全体をコピーせずに行うものとする。

5.

小問4で定義された $f(k)$ はアルゴリズム2の計算量なので、ここではその漸化式を解く。

$k=2^d$ とすると再帰の深さは $d=\log_2 k$。深さ $\ell$ の段には大きさ $k/2^\ell$ の問題が $2^\ell$ 個あり、各段の再帰以外の処理の合計は

$$2^\ell\Theta\left(\frac{k}{2^\ell}\right)=\Theta(k).$$

内部の段は $d$ 段、葉は $k$ 個であるから

$$f(k)=\Theta(k)\log_2 k+\Theta(k) =\boxed{\Theta(k\log k)}.$$

よって求めるオーダーは $\boxed{O(k\log k)}$。アルゴリズム1自体の計算量は、小問2のとおり、入力長の合計を $k$ とすれば $\Theta(k)$ である。

Reference

• 中央大学公式問題：2026年度 情報工学専攻、冊内 pp.3,5（PDF 第4,6頁）
• 中央大学公式解答例・出題の意図：問題II、冊内 p.6（PDF 第7頁）