Pythonプログラミング(ステップ1・準備・アルゴリズム)
このステップの目標
- アルゴリズムとプログラムの関係と対応を理解する。
1. アルゴリズムを考え、それをプログラムとして表現する
Pythonプログラミングと全く関係無さそうな話題かもしれないが、ここで『炊飯器でご飯を炊く手順』を考えてみよう。 授業担当者の場合、ざっと以下のような感じになる:
Input: 精米済みの米
Output: 炊きあがったご飯
1: 容器に米を入れる
2: 水を入れ、米を撹拌する
3: 米が沈むまで待ち、上澄みの水を捨てる
4: 上澄みの水が大きく濁っている間は2:から繰り返す
5: 洗った米を炊飯器の容器に移す
6: 炊飯に容器内側の目盛り
7: 炊飯器をコンセントに接続する
8: 「炊飯」ボタンを押す
9: 「炊飯」ランプが消え、「保温」が点灯するまで待つ
10: 終了する
ご飯を炊いたことの無い人に「ご飯、3合炊いといてね」といったアバウトな指示は全く意味が無いように、 コンピュータへの指示(コンピュータ・プログラム)も具体的かつ詳細に記述する必要がある。 このように、問題解決に向けての一連の処理や作業の手順をステップに分解し、具体的に記述したものをアルゴリズム(algorithm)と呼ぶ。
炊飯器の中にもコンピュータが内蔵されており、エンジニアが炊飯のアルゴリズムを考え、それを(Pythonとは限らないが)プログラミングしているはずだ。
手順をどのくらい細かい手順にまで分解した上で、どのような語彙と文法を使ってアルゴリズムを記述する必要があるかは、もちろん、想定する機械(計算機)の機能によって変わる。 もし完全自動式の未来型の炊飯器があったら、その機械のための炊飯アルゴリズムは、『白米をn合を炊く』の1行で済んでしまうかもしれない。 一方、上に示したアルゴリズムは、現在普及している炊飯器を使い、人が作業することが暗に想定されている。
高度に抽象的なアルゴリズムを考えたとしても、それをPythonでコーディングする際には、より具体的で細かい手順に分解する必要が生じる。 コンピューターを極限まで数学的に単純化したモデルが チューリングマシン(Turing machine) で、TMの機能だけでアルゴリズムを記述するのは恐ろしく面倒な作業になる。
であるから、アルゴリズムを考える際には、我々がどれくらい賢い(あるいはおバカな)計算機システムを相手にしているのか を、あらかじめ想定しておく必要がある。 ここで我々が学ぼうとしているPython言語は、プログラミング言語の中では「高水準言語」に分類されているものの、あらかじめ備わっている機能はとても限られている(当然、「炊飯命令」などは無い)。
すると、きちんと手順(アルゴリズム)を記述するにはPython言語の語彙や文法を把握しておかねばならない一方で、Pythonでプログラミングするためには、 まずアルゴリズムを考えなければならないことになって、これでは完全に循環論法である。 良い例えではないかもしれないが、作曲の際には楽器の特性を考慮しながら楽譜を書かなければならない一方で、楽器を演奏するには楽譜が必要である。 プログラミングの学習というのは、作曲法と演奏を同時に勉強するのとどこか似ているかもしれない。
その感じを掴んでおくために、具体的なPythonプログラミングに入る前に、Python言語(を含む一般的なプログラム言語)を使って問題解決の自動化を行う際、 どれくらいの細かさでアルゴリズムを考える必要があるのか、トランプのカードを用いた簡単な例を使って、まずは頭の準備体操をしておきたい。
カードの並べ替え
以下では、データをトランプのカードに見立てて説明しているが、「コイン」や「麻雀牌の萬子や筒子」など、 数値の大小が明確ならば、より親しみのあるモノに対応させて考えても一向に構わない。
テーブルにカードが2枚あって、それぞれ、aとbと書かれた枠内に置かれているとしよう。 その他に、tと書かれた枠がもうひとつあるとする。 そして、以下のルールに従ってカードを操作できるとしよう。
- カードはちょうど1枚分の大きさの枠内にしか置けない
- カードは1枚ずつ枠から枠に動かせる
- カードの上に別のカードを重ねると、下側のカードは「消えて」しまう(あるいは、上のカードとひっついて、1枚になってしまう)。
このとき、aとbのカードの場所を入れ替える手順を、「コンピュータ・プログラミング流」に述べると、 以下のようになる(右側に、実際に動作するPythonコードの例も示した):
Algorithm:カードの交換 | Pythonによるコーディング例(swap2.py) |
Input: aとbに置かれたカード Output: 置き場所が入れ替わったカード 1: aにカード(例えば1)を置く 2: bにカード(例えば2)を置く 3: aをtに移動する 4: bをaに移動する 5: tをbに移動する 6: aのカードの数値を確かめる 7: bのカードの数値を確かめる 8: 終了する |
a = 1 b = 2 t = a a = b b = t print("a=",a) print("b=",b) |
Pythonには多重代入と呼ばれる機能があるので、a,b=b,a
と書くだけで変数の入れ替えは可能。
上記のアルゴリズムを『aとbのカードを交換する』と一言で表しても、論理的に間違っているわけではないが、 一般的なコンピュータのハードウェアには「二つのデータを1回の工程で交換する」という機能が備わっていないので、 そのことを反映して、プログラミングの際に、データをひとつずつ移動するステップにまで分解して考えなければならないのだ。
練習:5枚のカードの並べ替え
(左から)一列に並んだ置き場所a,b,c,d,e上にそれぞれ置かれた5枚のカードの順序を反転させるアルゴリズムを、2枚のカードの交換の例に倣って、記述しなさい。 ただし、一箇所、仮置き場 t が用意されているとしなさい。
解説:アルゴリズムの汎用化
あらゆる問題の規模に対応する
『カードの並べ替え』を考えるときに、2枚の場合、3枚の場合、... といった具合に、与えられたカードの枚数ごとに手順を考えるのは明らかにスマートではない。
置き場所を番号や変数で指定する
カードの並べ替えの場合、どんな規模(
反復動作の指示
置き場所 a, b にそれぞれカードが置かれている場合、 すべてのカードを仮置き場 t に片付けるには、
1: a のカードを t に移動する
2: b のカードを t に移動する
と書けば事足りる。
一方、
などと書きたくなる。ところが、
1:
2:
3: 繰り返しここまで
練習:N枚のカードの並べ替え
一列に並んだ
ここで、
Input:
Output: 置き場所が入れ替わったカード
1:
2: (
3: ...
4: ...
?: 繰り返しここまで
の様式で記述すること。
「整列」については、参考書 p.30 例題2.25を参照
練習:3枚のカードの整列
一列に並んだ置き場所(左から)a,b,c上に数値が書かれたカードが置かれている。カードの数値は全て異なるとしよう。 最初のカードの配置にかかわらず、最終的にカードの数値が左から小さい順になるよう整列させるアルゴリズムを、「ヒント」の2枚のカードの交換の例に倣って、記述しなさい。
ヒント
記述にあたり、二枚のカードの大きさを比較して、その大小に応じて、処理を切り替えることができるものとする。
例えば、カードが2枚の場合は
Input: aとbに置かれたカード
Output: 小さい順に並んだカード
1: a にカードを置く
2: b にカードを置く
3: a と b を較べ a >b ならば4:から実行
そうでなければ7:に移る
4: a を t に移動する
5: b を a に移動する
6: t を b に移動する
7: 終了する
あるいは、(この課題では記述量を減らすために)「交換」をひとつの操作として定義してしまって、
Input: aとbに置かれたカード
Output: 小さい順に並んだカード
1: a にカードを置く
2: b にカードを置く
3: a と b を較べ a > b ならば a と b を交換する
4: 終了する
と手短に書いてしまってもよいことにしよう。
発展問題として、参考書の例題2.25を参考に、
発展練習:カードの「山」の移動
ここまでは、「カードの上にカードは置けない(重ねたら、一番上のカードにまとまってしまう)」という状況設定を考えていた。 以下の練習課題では、このルールを変更して
- カードはちょうど1枚分の大きさの枠内にしか置けない
- カードの上に別のカードを重ねることができる。ただし、カードに書かれた数値が下のカードより小さくなければならない。
- カードは一番上のものを1枚ずつ枠から枠に動かせる
としてみよう。
三つの置き場所 a, b, cがあり、aに
カードの枚数が
ヒント
これは「ハノイの塔」という名前で良く知られている問題である。
カードが
記述の際には、aからbへの移動を
解説: 「関数」を使ったアルゴリズムの記述
となるだろう。
と記述することができる(moveの中の
この、moveという「関数」を使うと、アルゴリズムは
Input: aに積まれた
Output: cに積まれた
1: 関数
2: もし
3:
4:
5:
6: それ以外(
7:
8:
9:
10: 関数定義終わり
11:
12: 関数
のように表現することができる。このアルゴリズムをPythonに直訳したのが以下のコードである。
「ハノイの塔」のpythonコード例
hanoi.py
def move(n,x,y,z): if (n==2): print(x,"-->",z) ; print(x,"-->",y) ; print(z,"-->",y) ; else: move(n-1,x,z,y) ; print(x,"-->",y) ; move(n-1,z,y,x) ; move(4,"a","c","b")
10枚のカードについて解く様子(YouTube動画)
コードを実行すると、4枚の場合の手順が画面に出力されるはずだ。プログラムの最後の辺りの"4"の値を変えれば、異なる枚数についても計算可能である。
この例では、「カードを移動する作業は・・・・をすることである」という風に、新しい語彙(ある種の動詞句)を定義することを通じてアルゴリズムが記述されている。 このように、手順の記述方法には、いくつかの流儀があって、そうした流儀に適したプログラミング言語が(Python以外にも)沢山開発されている。