擬似コード・再帰ドリル

目的

第5章「擬似コードと再帰」を定着させるための追加問題です。コードを実行せず、手で状態変化を追う訓練をします。

難易度ラベル

[A] 基本: 定義を読む・単純計算をする。

[B] 標準: 複数の定義を組み合わせる。

[C] 発展: 証明・設計・実装の説明が必要。

[D] 実装: 実行可能なコードまたは明確な擬似コードが必要。

[E] 接続: 本体教科書の概念へ橋渡しする。

A. 状態を追う

[A][再帰] 次の実行後の x,y,z を答えよ。

x = 2
y = 5
z = x + y
x = z - x
y = x + y

[A][再帰] 次の出力を順に書け。

for i = 1 to 3:
    print(i)

[A][再帰] 次の出力を順に書け。

for i = 1 to 3:
    for j = 1 to 2:
        print(i, j)

[A][再帰] 次のループ終了後の i を答えよ。

i = 1
while i < 20:
    i = 2 * i

B. 関数

[A][再帰] 次の f(4) を求めよ。

f(n):
    return 2*n + 1

[A][再帰] 次の g(3) を求めよ。

g(n):
    x = n
    x = x + 1
    return x * x

[A][再帰] 関数の前提条件と事後条件の違いを説明せよ。

C. 再帰

[A][再帰] Fact(4) の呼び出し列と戻り値をすべて書け。
[B][再帰] 次の関数 Sum(n) が返す値を説明せよ。

Sum(n):
    if n == 0:
        return 0
    return n + Sum(n-1)

[B][再帰] Sum(n) が停止する理由を説明せよ。
[B][再帰] Sum(n)=n(n+1)/2 を帰納法で証明せよ。
[B][再帰] 次の関数は停止するか。理由を述べよ。

Bad(n):
    if n == 0:
        return 0
    return Bad(n+1)

[B][再帰] 次の関数は n≥0 で停止するか。

Half(n):
    if n == 0:
        return 0
    return Half(floor(n/2))

D. 探索

[B][再帰] 線形探索の仕様を書け。
[B][再帰] 線形探索の最悪計算量を説明せよ。
[B][再帰] 二分探索の仕様を書け。
[C][再帰] 二分探索が失敗するソートされていない配列の例を作れ。
[C][再帰] 二分探索の不変条件を書け。
[C][再帰] 二分探索の計算量が Θ(log n) になる理由を説明せよ。

E. 実装

[C][再帰] 線形探索を Python で実装せよ。
[C][再帰] 二分探索を Python で実装せよ。
[C][再帰] 再帰版階乗を Python で実装せよ。
[C][再帰] ループ版階乗を Python で実装せよ。
[C][再帰] 配列の最大値を返す関数を Python で実装せよ。ただし空配列はエラーにする。
[D][再帰] 配列が昇順ソート済みかどうかを返す関数を Python で実装せよ。

代表解

1

初期: x=2, y=5
z=x+y=7
x=z-x=7-2=5
y=x+y=5+5=10
結果: x=5, y=10, z=7

4

i は 1,2,4,8,16,32 と変化する。32 になった時点で i<20 が偽になるため、終了後の i は 32。

9

Sum(n) は 1+2+...+n を返す。

12

n>0 のとき Bad(n+1) を呼ぶため、0 に近づかない。したがって停止しない。

13

n=1 のとき floor(1/2)=0 なので停止する。n>1 でも再帰呼び出しごとに自然数 n が小さくなるため、停止する。

24

def max_value(a):
    if not a:
        raise ValueError("empty array")
    m = a[0]
    for x in a[1:]:
        if x > m:
            m = x
    return m

25

def is_sorted(a):
    for i in range(len(a) - 1):
        if a[i] > a[i + 1]:
            return False
    return True