はじめに

こんにちは。Python勉強会第四回です。3週間ぶりで前回までの内容を忘れた人もいるかと思うので、復習メインでいきたいと思います。

復習

問題1

整数nを受け取り1からnまでの和を返す関数sum_nを作ってみましょう。ここで等差数列の和の公式を用いずループで解いてみて下さい。

関数は覚えていますか？for文は？

答えはできるだけ見ずに自分で考えてみましょう。

>>> def sum_n(n):
...   ans = 0
...   for i in range(1, n+1):
...     ans += i
...   return ans
... 
>>> sum_n(3)
6

思い出してきましたか？range関数は半開区間なのでn+1にするのは注意です。

問題2

整数nを受け取り$2^n$を返す関数pow2を作って下さい。ここでもループで解いてみましょう。

>>> def pow2(n):
...   ans = 1
...   for i in range(n):
...     ans *= 2
...   return ans
... 
>>> pow2(10)
1024
>>> 2 ** 10
1024

問題3

整数nを受け取り$n!$を返す関数factを作って下さい。

>>> def fact(n):
...   ans = 1
...   for i in range(1, n+1):
...     ans *= i
...   return ans
... 
>>> fact(5)
120

問題4

整数nを受け取りnが素数の時Trueを、素数でないときFalseを返す関数is_primeを作って下さい。

ヒント: n(> 1)が素数なのと2以上n-1以下の整数でnを割り切る整数が存在しない事は同値です。

>>> def is_prime(n):
...   if n <= 1:
...     return False
...   for i in range(2, n):
...     if (n % i == 0):
...       return False
...   return True
... 
>>> is_prime(5)
True

このコードのfor文は最大で2からn-1までのn-2回ループが回ります。大雑把に解析すると、これは最悪nに比例した時間がかかります。これをO(n)という形で表現します。(厳密に書くと面倒なので、ふわっと解釈で大丈夫です)

もしこのコードを速くしようとすればどう工夫しますか？実は、n(> 1)が素数なのと2以上√n以下の整数でnを割り切る整数が存在しない事は同値です。nがx(>√n)で割り切れる時、n/x(<=√n)でも割り切れるからです。

なので上のコードに2行追加してみましょう。

>>> def is_prime(n):
...   if n <= 1:
...     return False
...   for i in range(2, n):
...     if (n % i == 0):
...       return False
...     if (i * i > n):
...       return True
...   return True
... 
>>> is_prime(5)
True

これでも上のコードと同じ動作をし、より高速です。これが計算量という大切な概念です。競プロとかではここの工夫方法が主に問われています。

競プロをやる気が無い人でも計算量の概念を知っておく事は重要です。例えばデータ数をnのデータを処理する時、3重for文を書いたとします。これはnが1000を超えるデータを処理しようとすると既にヤバイです。3重for文を書かなくても、2重for文の中でO(n)の関数を呼び出すと同じです(そしてこれは割と書いてしまいがち)。

初心者のうちは深く考えなくていいですが、中級者以上になろうと思うなら意識しましょう。

問題5

整数nを受け取りn以下の素数のlistを返す関数get_primelistを作って下さい。

is_prime関数を用いて大丈夫です。listの使い方を覚えていますか？

>>> def get_primelist(n):
...   ans = []
...   for i in range(1, n+1):
...     if is_prime(i):
...       ans.append(i)
...   return ans
... 
>>> get_primelist(20)
[2, 3, 5, 7, 11, 13, 17, 19]

再帰関数

関数は実は自分自身を呼び出す事も可能です。これは再帰と呼ばれる汎用的なテクニックで、複雑な事をしようとする時に重宝します。

簡単な例を挙げます。問題1を再帰で実装してみます。

>>> def sum_n(n):
...   if n <= 0:
...     return 0
...   return n + sum_n(n-1)
... 
>>> sum_n(10)
55

理解できますか？sum_n関数は「nを受け取りn以下の自然数の和を返す」ので、return n + sum_n(n-1)を言葉で説明すると、「nとn-1以下の自然数の和を返す」わけです。確かに。数学的帰納法に似ていますね。

数学的帰納法と同じく終了条件を書く事は大切です。この場合、n=0の時が終了条件です。(念の為にn<=0にしています)

終了条件を書き忘れると無限ループになるので注意して下さい。

では問題2を再帰で書いてみましょう。

>>> def pow2(n):
...   if n == 0:
...     return 1
...   return 2 * pow2(n-1)
... 
>>> pow2(10)
1024

$2^n = 2^{n-1} \times 2$を利用します。終了条件はちゃんと書きましょうね。

さっと実装できた人はこれを高速化する方法について考えてみましょう。$log n$に比例する時間で動かす事も可能です。

では同様に問題3も...

>>> def fact(n):
...   if n == 0:
...     return 1
...   return n * fact(n-1)
... 

慣れてきましたか？では少し難しいかもしれない問題を出します。

$a_1 = 1$

nが3の倍数の時$a_n = 2 a_{n/3}$

n+1が3の倍数の時$a_n = a_{n+1} + 1$

n+2が3の倍数の時$a_n = a_{n-1} + 2$

整数nが与えられた時$a_n$を返す関数を書いて下さい。

漸化式が複雑で一般項を出すのは恐らく不可能では無いでしょうか。こんな複雑な漸化式も再帰関数を使えばそのままコードに落とし込めます。

>>> def f(n):
...   if n == 1:
...     return 1
...   if n % 3 == 0:
...     return 2 * f(n/3)
...   if n % 3 == 1:
...     return f(n-1) + 2
...   return f(n+1) + 1
... 
>>> f(3)
2
>>> f(10)
6

どうでしょうか。このレベルならループで書くのとそんなに変わらない(というかループで書けるならループ使う方が速いし楽)と思いますが、遷移がぐちゃぐちゃで複雑な時には使えるテクニックなので覚えておきましょう。アルゴリズムで言う所の深さ優先探索のコードをシンプルに書くことが出来ます。