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

Author

Isidore, 祭音Myyura

Description

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) = d(i-1, j-a_i) + d(i-1, j) \]