コンピュータサイエンス第一 第6週

  1. 先週の復習
  2. Python における関数 (function) とは?
  3. 自前の関数を定義する
  4. シーザー暗号とは何か?
  5. 本日の課題

雑談

リスクとは? - 「平均余命が下がる度合」 Understanding Risk
さまざまな要素のリスク:

結論: 世の中に危険なことはいくらでもある (e.g. 隕石が落ちてきて頭に当たる、等)。 しかし、人間は「どれくらい危険なのか」を定量的に考えるのは苦手であるので、 その結果、多くのことについて必要以上に心配してしまう。

0. 先週の復習

0.1. 前回までのあらすじ

練習問題.
  1. 以下のプログラムで、リスト a の先頭の要素 (a[0]) を削除して a = [9,4,7,0,0] となるようにしたい。 ??? の中を埋めよ。
    a = [5,9,4,7,0]
    i = 0
    while i < 4:
       a[???] = a[???]
       i = i + 1
    
  2. 今度は逆に、先頭の要素をひとつ空けて a = [5,5,9,4,7] となるようにしたい。が… 以下のプログラムを実行したとき a の中身がどうなるかを予測せよ。
    a = [5,9,4,7,0]
    i = 0
    while i < 4:
       a[i+1] = a[i]
       i = i + 1
    
  3. 前回の教訓を生かし、今度こそ a = [5,5,9,4,7] となるようにしたい。 ??? の中を埋めよ。
    a = [5,9,4,7,0]
    i = ???
    while ???:
       a[i+1] = a[i]
       i = ???
    

実際には、Python にはリストの途中の要素を削除したり 途中から挿入したりするためのもっと簡単な方法がある。 しかし、実際に内部で起きているのはこういうことである。

類似の問題: 0〜4までの番号がついた5個のイスが並んでいる。 0番目のイスをはずして残りを詰めるにはどうすればよいか?

1. Python における関数 (function) とは?

print(...)input(...) のような部分。 引数をとり、値を返す。

1.1. これまでに習ったPython関数

注意: if文, while文, for 文などは 「文」であって関数ではない。

1.2. いろいろな関数

pow: べき乗を求める。
関数によっては、2つの値をとることがある。
>>> pow(3, 4)
81
>>> pow(2, 0.5)
1.4142135623730951
>>> 3 ** 4
81  # **演算子を使っても同じ
sum: リストの和を求める。
リストを与えるような関数も存在する。
>>> a = [5,9,4,0]
>>> sum(a)
18
注意事項
各関数によって、とれる値の数、およびそのデータ型が決まっている。
>>> chr("a")
Traceback (most recent call last):
  File "", line 1, in 
TypeError: an integer is required (got type str)
エラー: chr関数には、数値型を与えなければならない。
>>> sum(4) Traceback (most recent call last): File "", line 1, in TypeError: 'int' object is not iterable
エラー: sum関数には、リスト型を与えなければならない。
>>> input("x=", "y=") Traceback (most recent call last): File "", line 1, in TypeError: input expected at most 1 arguments, got 2
エラー: input関数は、値を1つだけしか与えてはいけない。

プログラムを書かずにPythonを使う

ターミナルで、プログラム (.pyファイル) を書かずに、ただ

$ python
と入力すると、Pythonが「対話モード」で起動する。 この場合、Pythonのプログラムを1行ずつ直接入力して実行することができる。 これは、ちょっとした動きを確かめたいときなどに便利だが、 複雑なプログラムは書けない。
$ python
Python 3.7.4 (default, Oct  4 2019, 06:57:26)
[GCC 9.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> x=2
>>> y=3
>>> x+y
>>> print(x,y)
2 3

2. 自前の関数を定義する

Python では、自前の関数を新しく定義することができる。 新しく定義された関数は、従来からある関数とまったく同じように使える:

# 関数 plus(a, b) … aとbの和を求める。
def plus(a, b):
    return a + b

x = 2
y = 3
z = plus(x, y)  # zの値は 5。

プログラムが複雑になってくると、プログラムを全部一度に書くのではなく、 部分ごとに分けて書く、ということが必要になってくる。 関数はもともと数学の概念だが、Python における関数とは、 プログラムの処理の一部をおこなう部品である。 ここでは入力と出力をもった「ブラックボックス」に近い。

関数 入力A 入力B 入力C 出力

2.1. 関数を定義するには

def 関数名(変数名1, 変数名2, ...)
    関数の中身
    ...
    return 関数が返す値

2.2. 定義した関数を利用するには

変数名 = 関数名(値1, 値2, ...)

図示すると、以下のようになる:

plus return 2 3 x y 5 z a b
def plus(a, b):
    return a + b

x = 2
y = 3
z = plus(x, y)
練習問題
  1. 上のプログラムで関数 plus(x, y) を呼び出したとき、 関数の中で変数 a, b に入る値は何か?
  2. 以下のように呼び出したとき、 関数の中で変数 a, b に入る値は何か?
    p = 1
    z = plus(3, p)
    

2.3. いろいろな関数

2つの値の平均を求める関数

def avg(a, b):
    c = (a+b)/2
    return c

print(avg(3, 5))  # 4

関数の中で別の変数を使うこともできる。

関数の中で関数

print(1 + avg(3, 5))      # 5
print(avg(avg(3, 5), 8))  # 6

関数の返り値を計算したり、それをさらに関数を渡すこともできる。

文字列を返す関数

def sign(x):
    if x < 0:
        return "negative"
    elif 0 < x:
        return "positive"
    else:
        return "zero"

print(sign(-3))  # "negative"と表示される。
print(sign(4))   # "positive"と表示される。
関数の中で if文や while文を使うこともできる。 関数が返すデータの型は、数値以外のものでもOK。 また、関数の中に return文を複数書いてもよい。

値を返さない関数

def greet(name):
    print(f"Good morning, {name}")
    return

greet("euske")  # "Good morning, euske"と表示される。

(数学ではありえない) 値を返さない関数というものも存在する。 この場合、関数の中で print文を実行させることで 画面にものを表示させることのみが目的となる。

引数をとらない関数

def constant():
    return 1279

print(constant())  # 1279
print(constant())  # 1279
print(constant())  # 1279

引数をとらない関数は、何回実行しても同じ結果となる (当然)。

リストを返す関数

# 与えられた画面にフィットする画像の大きさを計算する。
def fitsize(x, y, w, h):
    if w*y < x*h:
        return [w, y*w/x]  # 横フィットの場合
    else:
        return [x*h/y, h]  # 縦フィットの場合

print(fitsize(20,10,100,100))  # [100, 50]
print(fitsize(20,10,400,100))  # [200, 100]

リストを返すこともできる。

関数の中でさらに関数

# aとbを足す
def plus(a, b):
    return a + b

# xに2を足す
def add2(x):
    # 定義した関数を使っている。
    return plus(x, 2)

print(add2(3))  # 5

一度定義した関数は他の関数と同じように使えるので、 さらに別の関数からも使える。

複数のreturn文

def navi():
    print("Hey!")
    return
    print("Listen!")  # 表示されない。
    return

navi()  # "Hey!" のみが表示される。

関数の実行は、最初の return文を実行した時点で終了する。

2.4. 関数内における変数の扱い

注意: 関数の内と外で同じ名前の変数を使っている場合、 関数内の変数は、外の変数とは別物として扱われる:

def plus(x, y):
    print(f"x={x}")  # ???
    print(f"y={y}")  # ???
    z = x + y
    print(f"z={z}")  # ???
    return z

x = 100
y = 200
z = 300
a = 2
b = 3
print(plus(a,b))  # 5
print(f"x={x}")    # ???
print(f"y={y}")    # ???
print(f"z={z}")    # ???

これは、関数がプログラムの他の部分とは完全に独立した プログラムと考えられているためである。 関数の外でどんな名前の変数を使っていようが、 関数の実行結果が影響を受けるべきではないからである。 関数内で使われる変数には、引数の値が一時的にコピーされるだけと 考えるのがよい。

演習 6-1.
  1. 上の例を実行して、関数の内と外で x, y, z の値が それぞれどう表示されるかを確認せよ。
  2. 以下のリストの平均値を求める関数 averageを完成させよ:
    def average(a):
        x = 0
        for i in range(len(a)):
            x = x + ???
        return ???
    
    print(average([1,2,3]))        # 2
    print(average([10,15,17,20]))  # 15.5
    
  3. 与えられた個数のアスタリスクを表示する関数 bar を書け。
    bar(3)  # "***" を表示する
    bar(5)  # "*****" を表示する
    
  4. 3. で定義した関数を bar を使って、 与えられた大きさの三角形を表示する関数 triangle を書け。
    # 以下のように表示する:
    # *
    # **
    # ***
    triangle(3)
    
    # 以下のように表示する:
    # *
    # **
    # ***
    # ****
    # *****
    triangle(5)
    

アニメーション・コンテスト審査

演習の合間に、 11月4日に提出したアニメーション・コンテストの 審査をおこなう。

以下のリンクをたどり、個人的に優れていると思う作品を 3つ選べ。

選考基準:

  1. 面白いか?
  2. 努力の跡が見られるか?
  3. フェアな勝負をしているか?

投票は、以下のページからおこなう:

投票の結果、本授業の最後に優秀者を決定する。

新山の感想: プログラム本体を提出する OCWi のところに間違えてレポート文書を 提出した (あるいはその逆の) 人が多かった。

3. シーザー暗号とは何か?

「シーザー暗号」とは、ジュリアス・シーザー (Julius Caesar, ユリウス・カエサル) が 使ったと言われる暗号で、アルファベットの順番をずらして文を作成する方法である。 暗号を元にもどす (復号) ためには、順番を逆方向にずらせばよい。 このとき、ずらす回数 k をその暗号の (key) とよぶ。

シーザー暗号の例:

このような暗号は、Python のプログラムで簡単に作ることができる。 入力された文字が英文のアルファベットであると仮定して、 各文字コードに与えられた数 k を足せばよい:

caesar.py
# 与えられた文字列 text を k回先にずらす。
def caesar(text, k):
    # 結果を入れる文字列変数を準備する。
    result = ""
    for i in range(len(text)):
        c1 = text[i]  # i番目の文字を取得する。
        n1 = ord(c1)  # その文字コード。
        n2 = n1 + k   # k 回ずらした文字コード。
        # ずらした文字を結果に追加する。
        result = result + chr(n2)
    # できた文字列を返す。
    return result

print(caesar("HELLO", 1))   # "IFMMP" と表示する。
print(caesar("IFMMP", -1))  # "HELLO" と表示する。
演習 6-2.
  1. 上のプログラム caesar.py にはバグがある。 入力した文字列が hello で k=1 の場合はよいのだが…
    print(caesar("HEY!", 2))
    # "JG[#" と表示される。
    
    問題は、文字コードをずらしたときに A〜Z の範囲を超えてしまうことである。 このような場合でもうまく動くように、以下の改良を加えよ:
    1. 英文アルファベット (A〜Z) 以外の文字は変更せず、そのまま表示する。
    2. 「"Z" の 1つ先の文字」が "A" になるようにする。(2つ先の文字は "B")
      ヒント: % を使うべし。

3.1. 暗号解析とは?

上のような簡単な英文のシーザー暗号は、すぐに解読することができる。 エドガー・アラン・ポーが 19世紀に発表した推理小説 「黄金虫」では、 このような暗号が使われていた (こちらは任意の文字が別の文字と対応するので、より難しい)。 暗号解析 (cryptoanalysis) とは、暗号の鍵がわからない状態で 暗号文だけからもとの文を推測 (解読) することである。 暗号解析技術は、現在でも各国の軍事機関でさかんに研究されている。

英文でもっともよく現れる文字は "e" であることから、 ある英文がシーザー暗号で書かれていると仮定すると、 暗号解析は以下のように行える:

  1. 暗号の中でもっとも多く現れている文字をさがす。
  2. その文字が E になるように、シーザー暗号の鍵 k を決定する。
  3. その値を使って文字を k回文だけ逆にずらし、元の文を復元する。

「暗号の中でもっとも多く現れている文字をさがす」処理は、 前々回にやった投票システムの課題と似ている。 つまり、暗号中の各文字をその文字に対する票と考え、 もっとも票の多かった文字を見つければよい。

暗号解析をおこなう関数 analyze.py (未完成版):
def analyze(text):
    # 26文字分の投票結果を用意する。
    votes = [0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0]
    # 1文字ずつ調べる。
    for i in range(len(text)):
        c = ord(text[i])  # i番目の文字の文字コードをとりだす。
        # それが英大文字の範囲であれば、票を1増やす。
??? ...
# votes の中で、最も多く得票したものを見つける。 maxi = 0 for i in range(len(votes)):
??? ...
# この時点で、「maxi番目の文字」がもっとも多く現れることが判明。 # これが "E" を表すように、k の値を計算する。 k = ??? return k

3. 本日の課題

中課題 4. シーザー暗号の暗号解析をおこなうプログラム analyze.py
analyze.py (未完成版)
# 関数 caesar の定義
def caesar(text, k):
    ...

# 関数 analyze の定義
def analyze(text):
    ...

# 解読対象の暗号文。
cipher = (
 "GUR FPVRAGVFG UNF N YBG BS RKCREVRAPR JVGU VTABENAPR NAQ " +
 "QBHOG NAQ HAPREGNVAGL, NAQ GUVF RKCREVRAPR VF BS IREL TERNG " +
 "VZCBEGNAPR. JURA N FPVRAGVFG QBRFA’G XABJ GUR NAFJRE GB N " +
 "CEBOYRZ, UR VF VTABENAG. JURA UR UNF N UHAPU NF GB JUNG GUR " +
 "ERFHYG VF, UR VF HAPREGNVA. NAQ JURA UR VF CERGGL QNEA FHER " +
 "BS JUNG GUR ERFHYG VF TBVAT GB OR, UR VF FGVYY VA FBZR QBHOG. " +
 "JR UNIR SBHAQ VG BS CNENZBHAG VZCBEGNAPR GUNG VA BEQRE GB " +
 "CEBTERFF JR ZHFG ERPBTAVMR BHE VTABENAPR NAQ YRNIR EBBZ SBE " +
 "QBHOG. FPVRAGVSVP XABJYRQTR VF N OBQL BS FGNGRZRAGF BS INELVAT " +
 "QRTERRF BS PREGNVAGL — FBZR ZBFG HAFHER, FBZR ARNEYL FHER, " +
 "OHG ABAR NOFBYHGRYL PREGNVA.")

# 暗号解析をおこない、鍵の値 k を決定する。
k = analysis(cipher)
# その値を使って暗号文を元にもどす。
text = caesar(cipher, -k)
# 復号した文字列を表示する。
print(text)

以下の課題は難しいので、希望者 (= 点数がほしい人) のみ提出すればよい。

小課題 4. 「自分暗号方式」の提案 (希望者のみ)