京都大学 情報学研究科 知能情報学専攻 2022年8月実施 情報学基礎 F2-1

标签：

• 京都大学
• 算法复杂度
• 表达式树
• 逆波兰表示法
• 后序遍历
• 栈
• 子集和问题
• 子集和方案数的动态规划

Author

Isidore, 祭音Myyura

Description

大学公表の原題

設問1

自然数 $n$ の関数 $f(n)$ に対するビッグオー記法 $f(n)=O(g(n))$ を考える。 ここで、$g(n)$ は自然数 $n$ の関数である。以下に示す各 $f(n)$ について、最も簡潔な形を持つ $g(n)$ を答えよ。

(1) $f(n) = 5 \log n + 2(\log n)^3 + 3n^3$

(2) $f(n) = n\log n + 10n^2 + 100n$

(3) $f(n) = 4n! + 2n^n + 8n \log n$

設問2

スタックマシンを用いて計算式 $((5-3)*2) + ((7-4)/(2+1))$ の値を求めることを考える。 ここで、「+」は加算、「-」は減算、「*」は乗算、「/」は除算を表す。 このとき、以下の問いに答えよ。

(1) 上記の計算式に対応する構文木を図示せよ。

(2) 上記の計算式に対応する逆ポーランド記法を示せ。

(3) 構文木を走査することで逆ポーランド記法出力する疑似コードを示せ。但し、再起呼び出しを用いるとこ。

(4) 上記の計算式の値を得るまでのスタックの変化を図示せよ。

設問3

互いに異なる $n$ 個の正の整数の集合 $A = \{a_1, a_2, \ldots, a_n\}$ と非負の整数 $s$ を考える。 正の整数 $i \ (\leq n)$ および非負の整数 $j \ (\leq s)$ について、$d(i,j)$ は、$A_i = \{a_1, a_2, \ldots, a_i\}$ の部分集合 $A'_i$ であって、$\sum_{a \in A'_i} a = j$ を満たすものの数を表すものとする。

(1) $A = \{10, 3, 6, 13, 11, 4\}$ とする。$d(4,16)$ と $d(6,20)$、また、それぞれに対して等式を満たす部分集合を全て求めよ。

(2) $d(i,j)$ を、$\{d(i-1,k)\}_{0 \leq k \leq j}$ のうちのいくつかを用いて表せ。但し、便宜上 $d(0, 0)=1$, $d(0,1)=0$, $d(0,2)=0$, $\ldots$, $d(0,j)=0$ とする。

题目描述

1. 对下列 $f(n)$，给出最简洁的渐近上界 $g(n)$ 使 $f(n)=O(g(n))$：
   1. $5\log n+2(\log n)^3+3n^3$；
   2. $n\log n+10n^2+100n$；
   3. $4n!+2n^n+8n\log n$。
2. 用栈机器计算 $((5-3)*2)+((7-4)/(2+1))$。
   1. 画表达式树；
   2. 写逆波兰式；
   3. 写出递归遍历表达式树并输出逆波兰式的伪代码；
   4. 图示直到求值完成的栈变化。
3. 设 $A=\{a_1,\ldots,a_n\}$ 为互异正整数集，$s\ge0$。令 $d(i,j)$ 为 $A_i=\{a_1,\ldots,a_i\}$ 中元素和为 $j$ 的子集个数。
   1. 对 $A=\{10,3,6,13,11,4\}$，求 $d(4,16)$、$d(6,20)$，并列出相应全部子集。
   2. 用若干 $d(i-1,k)$ 表示 $d(i,j)$；约定 $d(0,0)=1$、$d(0,j)=0$（$j>0$）。

Kai

設問1

• (1) $g(n) = n^3$
• (2) $g(n) = n^2$
• (3) $g(n) = n^n$

設問2

(1)

(2)

$$5\;3-2*7\;4-2\;1+/+$$

(3)

The answer is a Postorder Traversal for a binary tree:

outputRPN(node):
    if node->left_child is not Null then:
        outputRPN(node->left_child)
    if node->right_child is not Null then:
        outputRPN(node->right_child)
    output(node->value)

(4)

5
5 3
2
2 2
4
4 7
4 7 4
4 3
4 3 2
4 3 2 1
4 3 3
4 1
5

設問3

(1)

By definition we need to find subsets $A'_4$ of $A_4=\{10, 3, 6, 13\}$ that satisfy $\sum_{a \in A'_4} a = 16$. Therefore, the answer is

$$d(4,16) = 2, A'_4=\{10, 6\}, \{3, 13\}$$

Similarly, we have

$$d(6, 20) = 3, A'_6=\{10, 6, 4\}, \{3, 13, 4\}, \{3, 6, 11\}$$

(2)

$$d(i,j) = \begin{cases} d(i-1,j) + d(i-1,j-a_{i})&(a_{i}\leq j)\\ d(i-1,j)&(a_{i}>j) \end{cases}$$