①FizzBuzz ゲームを作ろう

概要

FizzBuzz（フィズバス）は、１から順番に数字を表示して、それが３の倍数のときは「Fizz」と表示、５の倍数のときは「Buzz」と表示、３の倍数かつ５の倍数（15の倍数）のときは「FizzBuzz」と表示するゲームである。単純な１つの条件式による分岐だけでなく、２つの条件を満たす必要がある書き方の「and」のような論理演算を使うので、条件分岐の練習には最適な題材だ。

指導のポイント

制御構造は「for」と「if・el if・else」を使っているだけなので、「６制御構造 2(for)」までを学習後にアルゴリズムさえ理解できれば、取り組ませることができる。判定も「%」演算子なので、既習事項である。
「割り切れる」かどうかを判定するために「余りがあるかどうか」を「%」で行う。
３で割り切れると５で割り切れると、その両方を含むという条件をどのような順番で立てればよいかのアルゴリズムを理解する。大事なのは条件で絞り込んでいく順番である。どこから「ふるいかけ」を始めるかが１つのポイントである。

プログラミングのポイント

入力はキーボードからさせず、forを使って 1から30までの範囲で連番を発生させ、都度判定して表示するだけである。すべての条件に当てはまらない時だけ elseに落ちてくる。条件とその順番さえアルゴリズムに沿っていれば、間違えない簡易なプログラムだ。

②文字列から単語を検索しよう

概要

変数内に格納された文字列とキーボードから入力させた文字列を比較するプログラムである。すべてのキーワード検索の基礎を学ぶことができる。いわゆる文字列処理の最も基本的なやり方で、頭から順番に比較していくアルゴリズムである。

指導のポイント

制御構造は「for」と「if」を使っているだけなので、「６ 制御構造2(for)」までを学習後にアルゴリズムさえ理解できれば、取り組ませることができる。
「.split」がしている作業内容と「for」の判定の意味がわかればよい。英文は単語ごとに空白があるので、その部分をどう処理するかがポイントである。

プログラミングのポイント

英文の文字列を変数s に入れているが、これはそのまま比較には使わない。「.split」メソッドを使うと指定した方法（ここでは1 文字の空白）によって単語単位で分割し、リスト形式で変数に格納してくれる。
あとはキーボードから入力された文字列とfor によって１単語ずつ比較をして、一致したら表示するだけである。実は s.split() と書いても空白を認識して動作するのだが、ここでは分ける条件を明示的に書けるということを知るためにも、そもまま練習させたい。

③パスワードを作成しよう

概要

学校では入学後に１人１台の端末が貸与されるため、あらゆる場面でのパスワードの重要性が高まっている。自他との区別や認証などの学習は別途授業内で行われると思われるが、ここでは作成の実践が行えるわけである。自分でランダムな文字列を使ったパスワードを作ることは無いだろうが、運営側が２段階や２要素認証として利用するワンタイムパスワードとしてはよく使われる手法である。

指導のポイント

「８乱数」の学習後に取りかかることができるプログラム。用意した文字列からランダムに取り出した文字を、指定した文字数分どのように格納していくかを理解する。たびたび結果表示に利用してきた print()内での文字列の合体をパスワード生成に利用する。
なお、2020年に米連邦捜査局（FB I）が出した勧告によれば、パスワードは複雑さより長さが大切ということで、15文字以上を推奨している。なお、 NIST(National Institute of Standards and Technology)では、人間が作るなら 8文字以上、自動生成なら少なくとも 6文字と推奨。日本の内閣サイバーセキュリティセンターが発行しているインターネットの安全・安心ハンドブックでは Webサービスでは 10文字以上、ファイルや記憶媒体の暗号化なら 15文字以上としている。

プログラミングのポイント

乱数を使うので、先頭で必ず randomを importしておく。パスワードの種となる文字列を用意しておくわけだが、サイトの仕様によって利用できる記号があれば、含めておくとより強度の高いパスワードを生成できる。ただし、ワンタイムパスワードの場合は、利便性が下がってしまうので善し悪しである。
生成したパスワードを格納する変数 passwordを文字列型で準備して、len()によって数えたパスワードの種の文字数までを乱数によって１文字ずつ取り出して変数 paswordに合体して代入し直している。あとはパスワードの文字数分繰り返して完成したら表示するだけである。

④素数を判定しよう

概要

素数は「その数と１以外で割り切れない、２以上の整数」である。つまり、入力させた値を２以上からその数字未満までの値で順番に割ってみて、どの数字でも割り切れなければ素数ということが判定できる。順番に繰り返すということで、コンピュータ得意の繰り返しを使えば解決することは、すぐ分かるだろう。
あとは繰り返し回数を正確に記述することと、割り切れるか割り切れないかという判断を式で書くだけである。

指導のポイント

制御構造は「for」と「if」を使っているだけなので、「６制御構造2(for)」まで学習後にアルゴリズムさえ理解できれば、取り組ませることができる。判定も「%」演算子なので、既習事項である。
forの range()の範囲指定（初期値と終端値）を間違えなければ、繰り返しはたやすい。ただ、√nをどう表現するかは苦労するかもしれない。数学で使われる考え方をどのような式に置き換えればよいのかを、プログラムとして記述する前にじっくり考えさせたい。
ifの条件は「%」を使って、余りがゼロなら割り切れるので「素数ではない」と表示させている。ここでは繰り返し（ループ）を強制的に抜ける breakを使っている点に注目すべきである。

プログラミングのポイント

実数を排除するために int()でくくってキーボードから入力させている。とりあえず結果を表示するための変数 pnに「素数です」という初期値を与えている。
rangeで値を２つ指定すると、後ろの数字未満の値まで繰り返される。入力された値を 2から繰り返し増加している値で割って余りを求め、余りがゼロなら「素数ではない」という文字列を変数 pnに代入し直し、breakによって繰り返しを抜ける。素数ではないという判定をした時点で繰り返し作業は終わっているので、breakで抜け出している点は重要である。
あとは結果を表示するだけである。
ただ、実際は n-1まで試す必要は無く、√nまでの計算で済むことが分かっているので、ルートを実現する数式として n **0.5 とし、さらに整数値に変換、range指定なので +1 で求めた値まで計算するようにしている点には注意が必要だ。

⑤探索アルゴリズム（線形探索法）

概要

探索アルゴリズムの定番であり、文部科学省が提供する『高等学校情報科「情報Ⅰ」教員研修用教材』でも題材として取り上げられている。
リストから検索（探索）したいときに用いる最もシンプルな方法のプログラム。最初から順番に比較して該当データを探す。リニアサーチとも呼ばれ、初心者が理解しやすいのでアルゴリズムの勉強に使われる。プログラム内に書かれているリストのデータそのまま見た目の左から順番に探していくので、動作が分かりやすい。

指導のポイント

制御構造は「for」と「if」を使っているだけなので、「６制御構造2(for)」まで学習後にアルゴリズムさえ理解できれば、取り組ませることができる。
「あるのかどうかわからない」ので、リスト内に該当するデータがあるかどうかを総当たりで順番に探していく。探索アルゴリズムは何種類もあるので、プログラムはシンプルだが「この方法だと一致データが最後にあったらデータ数が増えるほど探すのに時間がかかる」ということを意識したい。

プログラミングのポイント

探す元のデータは比較的バラバラな順番で格納されている。forの繰り返し回数は len( )によってリストのデータ数行われる。回数は変数 iに入り、一致した段階で「○番目に見つかりました。」と表示する。なぜそうするのかの理屈が分かればプログラム自体は難しくない。
実はデータの一致を見つけるだけなら、len( )でリストの数を数えなくても、直接 for i in numbers:と記述することでも、リストの内容は順番に変数 iに入るので、比較も if i == target: と記述してしまうこともできる。ここでは一致データを見つけたリスト内の位置を求めているので、この記述になっている。実用プログラムでは一致させてお終いということはなく、一致したら次の処理（紐付けられたデータを表示するなど Webの検索を思い浮かべてみよう）を行うから一致位置が大切なのである。

⑥探索アルゴリズム（二分探索法）

概要

探索アルゴリズムの定番であり、文部科学省が提供する『高等学校情報科「情報Ⅰ」教員研修用教材』でも題材として取り上げられている。
リストから検索（探索）するが、あらかじめデータが昇順か降順に整列している必要があるアルゴリズムである。整列さえしていれば、線型探索より効率よく探し出すことができる。ともかく並んでいるデータの真ん中を攻めて見つからなかったら、さらに残り半分の真ん中を攻めることで探していく手法を採る。

指導のポイント

制御構造は「while」と「if・el if・else」を使っているだけなので、「７制御構造 3(while)」まで学習後にアルゴリズムさえ理解できれば、取り組ませることができる。
これまでのアルゴリズムではずっと forによって繰り返しを行っていたのに、ここでは whileを使っているのはなぜかという疑問を持たせ、理由を考えさせたい。
考え方としては整列しているのだから、まずデータの中央値と一致を調べて「大きすぎる・小さすぎる」が判定できたら、中央値より左右のどちらかは捨ててしまえるという考え方である。

プログラミングのポイント

探す元のデータは完全に整列した順番で格納されている。
変数 leftにはリスト numberの最初の要素番号であるゼロを、変数 rightには len( )でデータ数を求めてそこから -1 することで最後の要素番号を代入している。データ数（要素数）ではなく、最後の要素番号（添え字・インデックス）を求める方法はよく使われるので、覚えておくと良い。
何回の繰り返しで検索が終了できるかわからないので、forではなく whileを使っている。要素の始めと終わりの番号を次々に狭めていって、一致データを見つけると左右の番号が同じになったら終了である。左右の位置を足しで２で割ることで、現在の範囲内での中央を求めている点や、２回目以上は中央値に＋１や－１した位置が新たな左右の開始位置に設定している点を読んでもらいたい。

⑦整列アルゴリズム（バケットソート）

概要

整列を行うアルゴリズムのうちの一つ。ビンソートとも呼ばれる。あらかじめ並べておいた入れ物に、対応する値を移すことでデータを整列させるアルゴリズム。
入れ物をバケツに例えたことから、バケットソートという名前で呼ばれている。

指導のポイント

制御構造は「for」と「if・el if・else」を使っているだけなので、「６制御構造 2(for)」までを学習後にアルゴリズムさえ理解できれば、取り組ませることができる。
整列させたい値をあらかじめ用意した配列の入れ物（バケツ）の要素番号と対応させて格納し、配列から値を取り出すだけのため、直感的に理解しやすいアルゴリズムである。
バケットソートは、整列させたい値が重複しない整数であり、その整数の範囲が事前に分かっている必要がある。とりうる値の範囲が大きくなると、順番に並べるために用意する配列の要素数が膨大になり、大きな範囲のデータが扱えないことは理解させたい。
ここでは、整列アルゴリズムの一歩として学習するが、のちの『⑩アルゴリズムの効率性』では、バケットソートは扱う値に制約はあるが、値同士を比較しないため、高速なソートであるという理解へ繋げたい。

プログラミングのポイント

整列させたい値を bucketsの配列の要素番号に対応させて格納し、取り出すだけである。
値を順番に bucketsの中へ入れるときは for文を用い、並べた値を取り出すときも for文を用いて表示させる。
動作が理解できた後に、整列させたい値の範囲を変え、対応する bucketsの要素数をどの程度変更すればよいかを考えさせることで、より深い理解が得られる。

⑧整列アルゴリズム（バブルソート）

概要

整列を行うアルゴリズムのうちの一つ。端から順番に隣り合う値の大小を比較しながら交換を繰り返してデータを整列させる。左から小さい順に並べ替える場合、隣り合う２つのデータを比較して、左側の方が大きかったら隣の右側と並べ替える。末尾のデータまで比較が終わったら、再度最初から２つずつ比較と入れ替えを繰り返す。

指導のポイント

だんだん大きな（もしくは小さな）値が右側に浮かび上がっていくような動きを「泡（バブル）」に見立てたアルゴリズムである。考え方は理解しやすくプログラムは平易に書けるが、データ量が多くなると時間がかかる欠点がある。単純交換法とも呼ばれ、並べ方の考え方は分かりやすい。
データの交換は、コイントスといって空中に２つのコインを放り投げて入れ替えるというやり方では無く、コインの置き場所を用意して、左右の手に持ったコインを置いて、握り替えて、置き場所から拾うという手順で実演をしてみると理解が進む。

プログラミングのポイント

●ステージ１
まず最初は、並べ替えるという考え方を学ぶために、２つの数字だけで書かれている。並べ替えが発生したら、移動元を一時的な変数にデータを避難させ、上書きを行い、避難させたデータを移動先の変数に入れる、という動作を３行で行っている。データ一時置き場なのでテンポラリーということで変数tmpを使っている。

●ステージ２
並べ替え元のデータは一気に６個に増える。データの数を決め打ちで書けないので、len() -1 によって作業を繰り返す回数を決め、添え字 + 1 を使って隣り合うデータを比べている。並べ替えの作業は同一である。

●ステージ３
隣り合うデータを比較して入れ替えるという考え方は同じだが、forを入れ子にすることによって、繰り返し部分と比較部分を分離している。
全体の繰り返し回数を指定している変数 iの forと、比較・入れ替えをしている変数 jの forに分かれている。

●ステージ４
ステージ３を元にバブルソート部分を関数化したもの。リスト宣言の位置や、defの指定、末尾の「:」などに注意したい。呼び出し側はリストnumbersを引数として渡し、受け取ったものを新たにリストに入れ直し並べ替えを行って戻り値で渡している。
これは元のリストの順序は破壊しないでそのまま保持したいときに使う手法である。

●ステージ５
ここでは、「８乱数」で学んだ知識も必要となる。importで randomを宣言し、空のリストを作って、rand intによって 0～9までの 10個のランダムなデータを格納して表示する。
次にそのリストを引数として関数に送る。関数はステージ４と同一である。最後に戻り値を表示して比較出来るようになっている。

⑨整列アルゴリズム（クイックソート）

概要

整列アルゴリズムの定番であり、文部科学省が提供する『高等学校情報科「情報Ⅰ」教員研修用教材』でも題材として取り上げられている。グループを分割しながらデータを整列していくという考え方で、これ以上分割できなくなった段階で並べ替えが終了している。一般的には最も並べ替えを速く行えるアルゴリズムであるとされている。

指導のポイント

再帰処理を行っているので、「11再帰」まで学習をしておくことが望ましい。
データの比較と交換回数が少なく抑えられるのが特徴で、比較的バラバラなデータに対しては強みを発揮する。適当な基準値を決め、基準値より小さい値と大きい値のグループに分ける。分けたグループ内で再度基準値を決めて大小のグループ分けをして・・・という作業を繰り返すことで並べ替える。グループの分割ができなくなれば、並べ替え終了である。分割統治法というアルゴリズムの一種で「大きな問題があるとき、それを構成する小さな問題の集合単位ですべて解けば元の大きな問題の解決を図る」という手法である。
基準値となる値がグループの中央値に近いほど分割が効率よく行われ高速になるが、これが偏っていると分割回数が増えて速度に影響する。

プログラミングのポイント

乱数を使う宣言をし、関数の定義を開始する。
関数の呼び出し元から受け取った引数のリストの要素数が 1つかそれ以下ならば整列済みと判断し、そのままリストを返す処理が先頭に入っている。これは再帰呼び出しが行われるため、受け取ったリストの内容がどんどん減っていくので、その終了条件を書いている。
次にリストの先頭の値を基準値として変数 pivotに入れ、グループ分けのためのリスト leftと rightを用意している。
forを使って２番目以降の値と基準値を比較して、基準値以下の場合は leftリストに、基準値より大きい場合は rightリストに格納していく。
分けた leftと rightとリストの両方をそれぞれ自分自身の引数として渡し（再帰呼び出し）を行い、基準値を決めて分割の処理を繰り返していく。
最後は leftリストと基準値、さらに rightリストを順番に結合したリストを戻り値として呼び出し元に返す。「+」記号は文字列の結合だけでなく、リスト要素の結合も可能なのである。ただ、pivotは通常の変数なので[]でくくることによって、リスト化してから結合している点に注意したい。
メインルーチンでは要素が 10個のランダムな値のリストを作り、元データを表示後、関数に渡して得た結果を表示している。

⑩アルゴリズムの効率性

概要

今まで探索や整列など、求める結果は同じでもアルゴリズムの違いによってスピードや効率の違いがあった。ここでは複数の整列アルゴリズムを比較して、効率の良いアルゴリズムとは何かを考える。

指導のポイント

これまでに３つ（バケット、バブル、クイック）の整列アルゴリズムを学習し、プログラムで動作を確認してきた。同じ整列をするというプログラムであっても、並べ替えの手法（アルゴリズム）が異なるため、数値を比較する回数や交換する回数が大きく異なる・・・だろうということは想像できるはずだ。
Webを調べれば理屈上の最低値などの計算式を参照することはできると思うが、実感として感じるのは難しい。そこで、プログラム内に３つとも並べて比較してみようというのが趣旨である。
乱数で生成するデータの数 nの値を50、100、150、200に変え、それぞれの結果を［比較表とグラフを開く］をクリックして記入していく。ボタンを押すと表が表示されるので、表にそれぞれの計算回数を入れてグラフを表示するだけである。
バブルソートはデータ量が増えるほど比較回数と入れ替え回数が増えるため、一番不利であることがわかる。バケットソートは条件によっては高速に並び替えられることなどを読み取って欲しい。

プログラミングのポイント

２つのライブラリをインポートする。今までも使ったおなじみの乱数を使うための randomと、このサイト独自のライブラリである minpro_sortである。これは、各種の整列アルゴリズムが関数化されて格納されているので、プログラム内での比較が容易となる。
整列に使用するデータの個数を変数 nに設定し、その範囲内で list()を用いてリスト samp le_dataを作成する。samp le_dataはシャッフルされ、これが整列前のデータとして表示される。
minpro_sortに入っているバケットソート、バブルソート、クイックソートに引数として sample_dataを渡して結果を表示している。表示も関数が担当しているので、プログラムはシンプルである。