イテレータ・再帰・計算量

章末演習（10問）

ここには解答を載せていません。

1. 章末演習章末演習 1▶ この演習を開く

   【基本】enumerate を使い，名簿に1から始まる出席番号を付けて表示し，番号が偶数の人だけを別のリストに集めてください。

   入力

   キーボード入力なし。名簿はプログラムの中で names = ["佐藤", "鈴木", "高橋", "田中"] とします。

   処理条件

   • for 文で enumerate(names, start=1) を回し，番号と名前を同時に受け取ります。range(len(names)) や names.index で番号を作りません。
   • 同じ for 文の中で，番号が偶数（2で割った余りが0）の名前を空リストに追加していく。スライス names[1::2] で代用しません。

   出力

   • 5行を出力します。1〜4行目は「番号: 名前」（半角コロンの直後に半角空白1つ），5行目は偶数番号の名前のリストを print したもの。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   1: 佐藤
   2: 鈴木
   3: 高橋
   4: 田中
   ['鈴木', '田中']
   

   ヒントを見る

   enumerate は何も指定しないと0から数え始めます。開始番号を変えると，偶数・奇数の判定結果がどう変わるかも考えましょう。

2. 章末演習章末演習 2▶ この演習を開く

   【基本】得点データを先頭から読み，負の値は入力ミスとして読み飛ばし，999 はデータの終わりの印として読み取りを打ち切って，有効な得点の合計と件数を求める関数 valid_total(data) を作ってください。

   入力

   キーボード入力なし。次の3つのリストを，この順に valid_total に渡す。

   [72, -1, 85, 90, 0, 999, 60]
   [999, 50]
   [10, -5, 20]
   

   処理条件

   • for 文で data を先頭から1つずつ調べます。999 なら break で打ち切り，負の値なら continue で次へ進みます。0 は有効な得点として数える。
   • 999 より後ろの値は数えません。999 がなければ最後まで調べます。
   • 合計と件数は for 文の中で変数に足し込んで求めます。sum・len・filter・リスト内包表記は使いません。
   • 関数は (合計, 件数) のタプルを返し，表示は呼び出し側で行います。

   出力

   • 3行を出力します。各行は「合計 値 件数 値」（各語と値の間は半角空白1つ）。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   合計 247 件数 4
   合計 0 件数 0
   合計 30 件数 2
   

   ヒントを見る

   1つの値について「終わりの印か」「入力ミスか」「有効か」を順に判定します。どの判定を先に置けば，3つのデータすべてで意図どおりになるかを考えましょう。

3. 章末演習章末演習 3▶ この演習を開く

   【基本】リストから iter でイテレータを作り，next で最初の要素だけを取り出したあと，for 文で残りを取り出してください。取り尽くしたイテレータに既定値付きの next を使った結果と，元のリストが何度でも使えることも確かめます。

   入力

   キーボード入力なし。データはプログラムの中で queue = ["受付", "検温", "診察"] とします。

   処理条件

   • it = iter(queue) でイテレータを作り，next(it) で最初の要素を取り出します。
   • 続けて for 変数 in it: で残りの要素を空リストに追加します。スライス queue[1:] で代用しません。
   • その後 next(it, "終わり") を呼び，戻り値を表示します。
   • 最後に元のリスト queue を for 文で回して要素数を数える。len は使いません。

   出力

   • 4行を出力します。順に「最初: 値」「残り: リスト」「追加の next: 値」「元のリストの要素数: 値」。コロンは半角で，その直後に半角空白1つ。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   最初: 受付
   残り: ['検温', '診察']
   追加の next: 終わり
   元のリストの要素数: 3
   

   ヒントを見る

   イテレータは「どこまで進んだか」を覚えていますが，リストそのものは位置を持ちません。for 文に渡したものがどちらなのかを意識しましょう。

4. 章末演習章末演習 4▶ この演習を開く

   【基本】0以上の整数 n の各桁の和を返す再帰関数 digit_sum(n) を作ってください。

   入力

   キーボード入力なし。次の5つの値を，この順に digit_sum に渡す。

   9045, 7, 0, 1000, 99999
   

   処理条件

   • 停止条件は「n が1桁（0〜9）のとき n を返す」とします。
   • それ以外は「一の位」と「一の位を除いた残りの数に対する digit_sum の結果」の和を返します。一の位と残りの数は % と // で求めます。
   • 関数の中では str への変換，for 文・while 文，sum を使わない（呼び出し側で5つの値を順に渡す for 文は可）。負の数は与えません。

   出力

   • 5行を出力します。各行は「n -> 各桁の和」（-> の前後に半角空白1つ。-> は半角のハイフンと不等号）。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   9045 -> 18
   7 -> 7
   0 -> 0
   1000 -> 1
   99999 -> 45
   

   ヒントを見る

   呼び出すたびに n の桁数が1つずつ減ることを確かめましょう。1桁になったら，それ以上分ける必要はありません。

5. 章末演習章末演習 5▶ この演習を開く

   【応用】リスト nums の中から k の倍数を先頭から探し，最初に見つかった値とその位置を返す関数 find_multiple(nums, k) を作ってください。

   入力

   キーボード入力なし。次の4組の (nums, k) を，この順に find_multiple に渡す。k は1以上の整数とします。

   ([12, 15, 22, 35, 40], 7)
   ([1, 2, 3], 7)
   ([14, 21], 7)
   ([], 7)
   

   処理条件

   • for 文で enumerate(nums, start=1) を回し，位置（1から数える）と値を受け取ります。
   • k で割った余りが0の値が見つかったら結果の文字列を変数に入れ，break で探索を打ち切る。ループの途中で return しません。
   • 見つからなかった場合の結果は，for 文の else 節で "なし" に設定します。フラグ変数や index で代用しません。
   • 見つかったときの結果は「値 は 位置 番目」（各語の間は半角空白1つ）の文字列とします。関数は結果の文字列を返し，表示は呼び出し側で行います。

   出力

   • 4行を出力する（空リストのときも「なし」）。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   35 は 4 番目
   なし
   14 は 1 番目
   なし
   

   ヒントを見る

   for 文の else 節がどんなときに実行され，どんなときに実行されないかを確かめましょう。空のリストでは繰り返しが1回も起きないことにも注意します。

6. 章末演習章末演習 6▶ この演習を開く

   【応用】昇順に並んだデータから値を探すとき，先頭から順に調べる線形探索と，範囲を半分ずつ狭める二分探索とで，要素を比べた回数を比べてください。

   入力

   キーボード入力なし。データはプログラムの中で data = list(range(0, 1000, 2))（0から998までの偶数500個）とします。目標値は 998 と 500 の2つで，この順に調べます。目標値は必ず data の中にあります。

   処理条件

   • 関数 linear_count(data, target) は先頭から1つずつ比べ，見つかったら break し，比べた要素の個数を返します。
   • 関数 binary_count(data, target) は lo = 0，hi = len(data) - 1 から始め，while lo <= hi: の中で mid = (lo + hi) // 2 の値と目標値を比べて範囲を狭める（data[mid] が目標値より小さければ lo を mid + 1 に，大きければ hi を mid - 1 にする）。見つかったら break し，while の繰り返し回数を返します。
   • 回数は「1回比べる（または1回 mid を調べる）たびに1増やす」ように数え，見つかった回も含める。in 演算子による存在確認，index，bisect モジュールは使いません。

   出力

   • 2行を出力します。各行は「目標 値: 線形探索 回数 回，二分探索 回数 回」。コロンは半角，読点は全角の「，」，それ以外の区切りは半角空白1つ。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   目標 998: 線形探索 500 回，二分探索 9 回
   目標 500: 線形探索 251 回，二分探索 8 回
   

   ヒントを見る

   回数を数える変数を増やす位置が，比較の前か後か，break の前か後かで結果が変わります。まず要素数の少ないデータで，手で数えた回数と一致するかを確かめましょう。

7. 章末演習章末演習 7▶ この演習を開く

   【応用】リストの中にリストが何重にも入ったデータを，1段のリストに平らにする再帰関数 flatten(items) を作ってください。

   入力

   キーボード入力なし。データはプログラムの中で data = [1, [2, [3, 4]], 5, [[6]], []] とします。要素はリストか整数のどちらかとします。

   処理条件

   • flatten は新しい空リストを用意し，items の要素を for 文で順に調べます。
   • 要素がリストかどうかは type(x) == list で判定します。リストなら flatten を呼び直した結果を extend でつなげ，そうでなければ append で加える。
   • 元の要素の並び順を保つ。itertools，文字列への変換，sum(..., []) は使いません。

   出力

   • 2行を出力します。1行目は flatten(data) の結果，2行目は flatten([]) の結果をそれぞれ print したもの。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   [1, 2, 3, 4, 5, 6]
   []
   

   ヒントを見る

   この関数では，中身が空のリストを受け取ると繰り返しが1回も起きずに終わります。それが停止条件の役割を果たすことを確かめましょう。

8. 章末演習章末演習 8▶ この演習を開く

   【複合】和が target になる2つの数の組を2通りの方法で求め，調べた回数を比べてください。

   入力

   キーボード入力なし。データはプログラムの中で nums = [3, 8, 1, 6, 4, 5]，target = 9 とします。nums の値はすべて異なります。

   処理条件

   • 方法(1)：for i, a in enumerate(nums): で位置 i と値 a を取り，内側の for 文で nums[i + 1:] の値 b と組にします。a + b を1回調べるたびに比較回数を1増やし，和が target なら (a, b) をリストに加える。
   • 方法(2)：空の集合を用意して nums を先頭から1回ずつ調べ，1つ調べるたびに回数を1増やす。今の値を x としたとき，target - x がすでに集合にあれば (target - x, x) をリストに加え，その後 x を集合に加える。
   • 組の並び順はどちらの方法も見つかった順とします。itertools は使いません。

   出力

   • 2行を出力します。1行目は「二重ループ: 組のリスト 比較 回数 回」，2行目は「集合を使う: 組のリスト 調べた回数 回数 回」。コロンは半角，各要素の区切りは半角空白1つ。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   二重ループ: [(3, 6), (8, 1), (4, 5)] 比較 15 回
   集合を使う: [(8, 1), (3, 6), (4, 5)] 調べた回数 6 回
   

   ヒントを見る

   方法(2)では，今の値と組になる相手の値を先に計算し，それを「これまでに見た値」の中から探します。2つの方法で組の並び順が違って見える理由も考えましょう。

9. 章末演習章末演習 9▶ この演習を開く

   【複合】フィボナッチ数を求める再帰関数を2通り作り，fib(20) を求めるまでに関数が呼ばれた回数を比べてください。

   入力

   キーボード入力なし。求める値は n = 20 とします。

   処理条件

   • (1) 関数 fib(n) は，n < 2 なら n を返し，それ以外は fib(n - 1) + fib(n - 2) を返します。
   • (2) 関数 fib_memo(n) は，計算済みの値を関数の外で用意した辞書 memo = {} に覚えます。n < 2 なら n を返し，n が memo になければ fib_memo(n - 1) + fib_memo(n - 2) を計算して memo に入れ，memo[n] を返します。
   • 呼び出し回数は，関数の外で用意した辞書 calls = {"naive": 0, "memo": 0} を使い，各関数の先頭（停止条件の判定より前）で該当する値を1増やして数える。
   • fib(20) を先に，fib_memo(20) を後に，それぞれ1回だけ呼ぶ。functools.lru_cache や for 文による反復計算で代用しません。

   出力

   • 2行を出力します。各行は「関数名(20) = 値 呼び出し 回数 回」（= の前後と各要素の区切りは半角空白1つ）。
   • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

   実行例

   fib(20) = 6765 呼び出し 21891 回
   fib_memo(20) = 6765 呼び出し 39 回
   

   ヒントを見る

   まず小さな n（たとえば 4）で呼び出しの木を紙に描き，同じ引数で何度も呼ばれている箇所を探しましょう。memo はその重複をどこで止めるのかを考えます。

10. 章末演習章末演習 10▶ この演習を開く

    【複合】CSV 形式の行を集めたリストを読み，見出しを分けて取り出したあと，行番号を付けながら得点を集計してください。不正な行は記録して読み飛ばし，終わりの印で読み取りを打ち切ります。

    入力

    キーボード入力なし。データはプログラムの中で次のように用意します。

    rows = ["name,score", "A,80", "B,abc", "C,95", "END", "D,70"]
    

    処理条件

    • it = iter(rows) でイテレータを作り，next(it) で1行目を取り出してカンマで分け，見出しのリストにします。
    • 残りの行は enumerate(it, start=2) で行番号（rows の中で1から数えた番号）を付けて for 文で処理します。
    • 行が "END" なら break で打ち切る。それ以外の行はカンマで名前と得点に分け，得点が isdigit() で数字だけと判定できなければ行番号をリストに記録して continue します。数字だけなら int に変換して辞書に「名前→得点」で加える。
    • csv モジュールは使いません。"END" より後ろの行は処理しません。

    出力

    • 3行を出力します。順に「見出し: リスト」「得点: 辞書」「不正な行: 行番号のリスト」。コロンは半角で，その直後に半角空白1つ。
    • 上記以外の行（見出し，入力の確認表示，デバッグ用の print など）は出力しません。

    実行例

    見出し: ['name', 'score']
    得点: {'A': 80, 'C': 95}
    不正な行: [3]
    

    ヒントを見る

    見出しを next で取り出した後のイテレータは，2行目から始まります。enumerate に渡す開始番号がそれと合っているかを確かめましょう。