第1回 - Python の復習、再帰とは

2021年12月6日

コンピュータサイエンス第一の復習
- 演習 1-1. いきなり復習問題
- 中課題3 (暗号解析)
Pythonでコマンドラインの引数を利用する
- 演習 1-2. プログラムへの引数を利用する
再帰とは
ブレイクアウトルーム練習
- 演習 1-5. 再帰を使った場合・使わない場合
本日の課題
- 小課題 1. 再帰を使って三角形を描画する (12月13日締切)

注意: 今回はブレイクアウトルームの練習をするので、 PCから参加すること。(休憩時間中に準備してもよい。)

0. コンピュータサイエンス第一の復習

以下の Python 式のデータ型を答えよ。

4 * 3
"a" + "b"
chr(65)
ord(chr(65))
str(1 + ord("A"))
int("xyz")

0.1. 中課題3 (暗号解析)

もとの文

もとの文は、リチャード・ファインマンの言葉からとってきたものである。ちなみに「ご冗談でしょう、ファインマンさん」は個人的にオススメの本。

The scientist has a lot of experience with ignorance and doubt and uncertainty, and this experience is of very great importance. When a scientist doesn’t know the answer to a problem, he is ignorant. When he has a hunch as to what the result is, he is uncertain. And when he is pretty darn sure of what the result is going to be, he is still in some doubt. We have found it of paramount importance that in order to progress, we must recognize our ignorance and leave room for doubt. Scientific knowledge is a body of statements of varying degrees of certainty - some most unsure, some nearly sure, but none absolutely certain.

科学者はみな、数多くの無知と疑いと確信のなさを体験している。科学者がある問題に対する答えを知らないとき、彼は単に無知だ。それに対してなんらかの予測をしているときも、まだ確信がもてない。そして答えにメチャ自信があるときでも、まだなにがしかの疑いが残っている。科学の進歩のためには、我々が自分の無知を認め、疑いの余地を残しておくことが非常に重要なのだ。科学の知識というものは、いろいろな確かさをもつ言明の寄せ集めである - そのいくつかは確かでないし、いくつかはかなり確かっぽいが、どれひとつとして絶対的に確かなものはない。

採点基準

標準的なレポート … 15点。
- レポートの形式に沿ってない (学籍番号、氏名、題名が書かれてない) ものは減点。
- プログラムおよび実行結果が載っていないものは減点。
- プログラムだけで説明が書かれていないものは減点。

追加問題: 「任意の k」といっても実際には暗号は k = 0〜25 で閉じているので、この範囲の k だけについて示せばよい。もとの文を記録しておき、すべて k について暗号化・暗号解析し、同じ文が復元できることをプログラムによってチェックしているものを正解とみなす。

回答例:

# もとの文章を求める。
original = ceaser(text, analyze(text))
# 鍵を 0〜25 まで変化させ、同じ文章が解読できるかどうかを見る。
for k in range(26):
    enc = ceaser(original, k)      # 鍵kによる暗号文
    dec = ceaser(enc, analyze(s))  # それを暗号解析した文
    if dec != original:
        print("FAIL!")
# FAIL! が表示されなければ、すべての k に対して成功。

秀逸なレポートの例 (抜粋)
- 例. 処理の流れを図で示しており、わかりやすい。
- 例. 数式をわかりやすく説明している。

現代の暗号技術に興味がある方のために

シーザー暗号のような暗号は、 ECB方式と呼ばれている。これは「ある文字を特定の別の文字に直す」方法で、暗号化した後も元の文章のパターン (統計など) が残ってしまうという弱点がある。これに対して現在の高度な暗号は CBC方式を使っており、これは「前の暗号結果を利用して次の文字用の鍵をつくり、文字(ブロック)ごとに鍵をつぎつぎ変えていく」という方式をとっている。この方法だと、非常に解析しにくい。ちなみに著名な暗号学者はみな、数学が得意なチョーー頭のいい人である。

1. Pythonでコマンドラインの引数を利用する

以下のプログラムを実行してみよう:

showargs.py

import sys
a = sys.argv
print(a)

じつは Python では関数だけではなく、 Python プログラム全体にも引数を渡すことができる。

$ python showargs.py
$ python showargs.py abc 123 (←引数)

Python プログラムの最初に import sys文を実行すると、 sys.argv という名前の特殊なリストが利用できるようになる。このリストには、コマンドプロンプトで Python を実行したときに与えた引数が、文字列のリストとして入っている。ちなみにこのリストの 0番目の要素にはプログラムの名前 (ここではshowargs.py) が文字列として入っており、それ以降の引数が 1番目、2番目… の要素に入っている。これらはすべて文字列型であるので、数値として使うさいには int()関数などを利用して変換する。

以下のプログラム plus.py を エラーを出さずに実行する方法を答えよ。これは何をしているのか?
```
# plus.py
import sys
a = sys.argv
x = int(a[1])
y = int(a[2])
print(x+y)
```

コンピュータサイエンス第一の授業では Python でキーボードから文字を入力する方法として input() 関数を使ってきたが、本授業では入力はすべてプログラム全体の引数を使う。このほうが (コマンドプロンプトの履歴機能を使って) プログラムを繰り返し実行するのがラクだからである。

2. 再帰とは

再帰 (recursion) とは、ある関数の中で自分自身を再帰的に呼び出すことである。

2.1. これが再帰だ

def S(n):
    if n == 0:
        return 0
    else:
        return S(n-1) + n

これは数学における「漸化式」に似ている。

S_n = 0 (n が 0 の場合)
S_n = S_n-1 + n (それ以外)

再帰的な関数定義を使うと、いろいろな数学の関数を簡単に定義することができる。たとえば

べき乗

a^b = 1 (b が 0 の場合)
a^b = a ・ a^b-1 (それ以外)

であるから、a^b = power(a, b) という関数として考えると

def power(a, b):
    if b == 0:    # b が 0 の場合
        return 1
    else:         # それ以外
        return a * power(a, b-1)

階乗

n! = 1 (n が 0 の場合)
n! = n・(n-1)! (それ以外)

であるから、n! = fact(n) という関数として考えると

def fact(n):
    #print(f"fact {n}")  この文を入れると途中の様子が表示される。
    if n == 0:    # n が 0 の場合
        return 1
    else:         # それ以外
        return n * fact(n-1)

2.2. 再帰を使うさいの注意

以下のプログラムを実行するとどうなるか?

def f(n):
    return f(n-1) + 1

print(f(3))

再帰を使う場合には必ず停止条件を書くことが必要である。これは、漸化式の場合に必ず初期条件が必要なのと似ている。つまり Python では、再帰的な関数では必ず中に if文が必要である。

上の関数 power() および fact() を実行し、結果を確認せよ。
上で紹介したべき乗を計算する関数 power() は効率がよくない。以下のような原理を使って、べき乗を効率的に計算するように改造せよ。
- a^b = 1 (b が 0 の場合)
- a^b = (a^b/2)² (b が偶数の場合)
- a^b = a ・ a^b-1 (b が奇数の場合)
```
def power(a, b):
    if b == 0:         # b が 0 の場合
        return 1
    elif (b % 2) == 0: # b が偶数の場合
        ????
    else:              # b が奇数の場合
        ????
```

2.3. 再帰の能力

じつは再帰を使うと、どのような繰り返し処理でも実現可能である。たとえば以下のようなプログラムを考えよう:

i = 0
while i < 10:
    print(i)
    i = i + 1

これを再帰を使って書くと、以下のようになる:

def f(i):
    print(i)
    if i < 10:
        f(i+1)
    return

f(0)

(再帰的な関数の引数はべつに減るだけでなく増えてもよい)

再帰があれば、実は while文や for文はいらない。それどころか、while文では簡単に表せないような繰り返しも、再帰を使うと簡単に書くことができる。

以下の再帰的な関数 combo(n, s) が何をするか、 実行する前に 考えよ。実際に実行して自分の予想が正しいかどうか確認せよ。

def combo(n, s):
    if n == 0:
        print(s)
        return
    else:
        combo(n-1, s+"0")
        combo(n-1, s+"1")
        return

combo(5, "")

結局のところ、この関数 combo(n, s) は n と s に対して「何をしている」と言えるのか?

上に挙げたように、再帰は非常に強力である。これはとくに、組み合わせが指数的に増えるような問題を簡単にプログラムできてしまう。しかし同時に、再帰を使うと問題を非常に抽象的に (数学的に) 定義しなければならないので、直感的にわかりにくくなる危険性もある。

注意: 休憩後にブレイクアウトルームの練習をするので、準備しておくこと。

3. ブレイクアウトルーム練習

本授業では、Zoom のブレイクアウトルームを使った演習をおこなう。クラスを 2〜3人のグループに分け、簡単なプログラムを書き、画面共有をしてグループの人に見せる。

まず自己紹介をする。名前・所属・趣味などを簡単に説明する。 (今回はカメラを使わなくてもよいが、次回からはブレイクアウトルーム中は顔を出すこと)
最初の問題をやる担当者を決める。その人が自分の PC の画面共有をおこない、課題のプログラムを考えながら書く。このとき周囲の人は手助けすること。
終わったら、次の担当者が次の問題をやる。これを繰り返す。
授業終了の5分前にブレイクアウトルームを終了させるので、それまでに全問題を終わらせる。

以下のフィボナッチ数列を計算する関数 fib() を、再帰を使って書け:
- a_n = 1 (n が 0 または 1 の場合)
- a_n = a_n-2 + a_n-1 (それ以外)
```
def fib(n):
    ...
```
同じ関数 fib() を、今度は再帰を使わずに while文を使って書け。どのように面倒くさくなるか?

4. 本日の課題

提出期限: 12月13日 (1週間後)
本日の成果を使って、再帰だけで (while文やfor文を使わずに) 三角形を表示するプログラム triangle.py を書け。
T2SCHOLA で .pyファイルのみを提出すればよい。
三角形の大きさをコマンド引数で指定できるようにすること:
```
$ python triangle.py 2
*
**

$ python triangle.py 5
*
**
***
****
*****
```
注意: 採点はロボットが自動で行うので、必ず実際に動くものを提出すること! また「*」以外の余計なものは表示しないこと。実行できなかったり、余計なものが表示された場合は容赦なく不正解として扱われる。

ヒント

まずコマンド引数から大きさを得るには、先に説明したリスト sys.argv を使う:

import sys
a = sys.argv
n = int(a[1])

つぎに、与えられた長さ n個 * の列を返す関数 makebar() を定義しよう。

def makebar(n):
    if n == 0:   # n が 0 の場合 - 空列
        return ""
    else:        # それ以外
        return "*" + makebar(n-1)

print(makebar(10))  # "**********" が表示される。

あとはこの makebar() を使って、三角形を表示する関数 triangle() を定義すれば OK。

def triangle(i, n):
    ...
    # 三角形の1行を表示する。
    print(makebar(...))
    ...
    return

# 最後にそれを実行する。
triangle(0, n)

関数 triangle() は、上のように引数を2つとる形式にしたほうがラクである。

Yusuke Shinyama