今日は「アルゴリズムの実装」について学びます。具体的には、線形探索のアルゴリズムを例に、フローチャートからPythonのコードに落とし込む過程を学びます。これにより、アルゴリズムがどのようにプログラムとして実装されるのかを理解します。
黒板
授業
アルゴリズムとは何か?
さて、今日は「アルゴリズムの実装」について学ぶんだよ。アルゴリズムって、なおや君、覚えているかな？
前回習ったじゃないですか、先生。問題を解決するための手順、ですよね？
さすがだね、なおや君。そうだよ、その通り。今日はその手順を具体的にプログラムに落とし込む方法を学ぶんだ。
プログラム初心者の私でも大丈夫ですか？
線形探索アルゴリズムとは何か
まずは、「線形探索」について説明しよう。線形探索とは、リストや配列などに入ったデータを先頭から順番に調べ、目的のデータを探し出す手法だよ。
「アルゴリズム」の勉強の時に紹介のあった2つの探索のうち、効率が良くない方でしょ。
そうだね。前回紹介した例では、探索回数が多い方だったけれど、事前にソート（並べ替え）していなくても探すことができるというメリットがあるよ。本格的なアルゴリズムの実装になるけれども、覚悟はいいかな！？
プログラミングに挫折した僕でもわかるよう、詳しくお願いします
線形探索のアルゴリズムとフローチャート
それではこのフローチャートを一緒に見ていきましょう。まず、フローチャートは「start」から始まります。ここでまず、配列と検索対象の値を設定します。つまり、どのデータを探すのかを決めるんだよ。
なるほど、最初にどのデータを探すのかを決めるんですね。
そのとおり。その後は配列の先頭から順に値をチェックしていくんだ。これを「探索」ステップと呼んでいます。
それはつまり、1つずつデータを見ていくってことですよね？
そうだよ。そして、現在見ているデータが検索対象の値と一致するかどうかを確認するんだ。
一致したらどうなるんですか？
一致した場合は、その位置（インデックス）を返して、フローチャートはそこで終了します。つまり、探していた値を見つけたら、その場所を教えて、仕事は終わりなんだ。
でも、一致しなかったらどうなるんですか？
一致しなければ、次の要素に移動して、また同じように検索対象と一致するかどうかをチェックするんだよ。そして、全てのデータをチェックし終えてもまだ探している値が見つからなかった場合は、’None’を返して、フローチャートは終了します。
なるほど、探していたものが見つからなかったら、Noneが返るんですね。
その通りだよ。そして最終的に「end」に到達し、フローチャートは終了します。これが探索のアルゴリズムの全体像だよ。
すごいですね、これで探索がどう行われるのかがよくわかりました。ありがとうございます！
フローチャートをPythonコードに
# 配列と検索したい値の定義
list = [1,2,3,5,8,10,13,15,20]
target = 15
# for文と探索ステップ
for i in range(len(list)):
# 条件分岐と一致の確認
if list[i] == target:
# 一致すればそのインデックスを返す
print(i)
break
else:
# 一致する要素がなければNoneを返す
print(None)
さて、上に記したものが、線形探索のアルゴリズムのPythonのコードだ。
それほど長くなさそうなので、頑張れそう！
良いね！それでは、コードを１行ずつ解説していきましょう。まず最初の行（リストの2行目、3行目）でデータが入っている配列listと、検索したい値targetを定義しています。
# 配列と検索したい値の定義 list = [1,2,3,5,8,10,13,15,20] target = 15
配列って何ですか？
配列とは、複数のデータを一列に並べて保存するデータ構造のことを指すよ。Pythonではリストとも呼ばれますね。これにより、データを効率良く扱うことができるんだ。
なるほど、つまり複数のデータをまとめて管理するんですね。
for文と探索ステップ
次にリストの6行目、”for i in range(len(list)):”について説明するよ。ちょっと複雑なので、for 文と、range関数、len関数に分けて説明するね
# for文と探索ステップ for i in range(len(list)):
おっと、この1行だけで3つの命令の組み合わせなんですね。難しすぎる・・・
はずはlen関数だ。これは引数として与えられたリスト（ここではlist）の長さ、つまりリストに含まれる要素の数を返します。list = [1, 2, 3,5,8,10,13,15,20]の場合、9つの要素が含まれるから、len(list)は9を返すよ。
なるほど。じゃあrangeというのは？
range関数はある範囲の整数を生成するんだ。たとえばrange(9)だったら、0, 1, 2,4,5,6,7,8の８つの整数を生成するよ。
ふむふむ、じゃあfor i inの部分は？
ここで i はループ変数と呼ばれ、ループが回る度に新しい値が格納されます。forとinは「何かを順に取り出して行く」という操作を意味するんだ
ややこしいけど、結局これを組み合わせるとどうなるの？
要するに、リストの長さ（つまり要素の数）だけループを回すという事だよ。ループを回すたびに、ループ変数iの値が1つずつ増えていくんだ。
それだけの事か？なんだかややこしいけれど・・・。
python文はパターンとして覚えてしまえば、ここまで考えなくても使えるから、そんなに悩まなくてもよいよ。
はい、ではあまり考えすぎずに、 for I in range(リスト):という形で覚えるようにします。
条件分岐と一致の確認
次（リストの9行目）”if list[i] == target:”について説明します。これは「if文」と呼ばれ、条件分岐を行うための構文です。ここでは、配列の現在の要素が検索対象の値と一致するかどうかを確認しています。
# 条件分岐と一致の確認
if list[i] == target:
なんとなくわかるようなわからないような。かみ砕いて説明してください
もちろんだよ。If文は、次に来る条件がTrueであるかどうかをチェックします。もし条件がTrueであれば、その次に書かれているブロックのコードが実行されるよ。
なるほど。list[i]というのは？
list[i]で、配列のi番目の要素を取り出しています。for文で指定したループ変数がiだったから、ループを回るたびに配列の1番目の要素、2番目の要素という順番に取り出していくよ。
list = [1, 2, 3,5,8,10,13,15,20]だったから、list[0]の値は1で、list[1]は2でという具合に取り出すという事だね
理解しているね。さすが！この値とここで取り出した値とtargetが等しいかどうが確認できるんだ。
そういうことだったんですね。これで、探したかった15が見つかるまでループを回すんですね。
その通り。見つかったら、print(i)で、何番目に見つかったかを表示するんだ。そして、この時点で探索は終了し、プログラムも終了します。
# 一致すればそのインデックスを返す
print(i)
break
でも、それ以外の場合はどうなるんですか？
良い質問だね。全ての要素をチェックした後にまだ見つからなかった場合は、ループを抜けるんだ。このままだと何が行ったかわからないから、Noneと表示して終わるようにしているんだ。
else:
# 一致する要素がなければNoneを返す
print(None)
なるほど、見つからない場合には、そのことをちゃんと表示するようになっているんですね。
その通りです。このプログラムは、探索対象の値が見つかればその位置を、見つからなければNoneを返す、というアルゴリズムになっています。
すごいですね、これでアルゴリズムがプログラムになるんですね。
はい、その通りです。アルゴリズムはプログラムにとっての基本的な手順ですから、このように具体的なコードに落とし込むことで、問題を解決するためのツールとして利用できます。
今日はとても勉強になりました。次回も楽しみです。
まとめ
- アルゴリズムの概念
アルゴリズムとは、問題を解決するための手順である。具体的な手法や計算方法などを組み合わせて、特定の問題を解くための手続きを指す。 - 配列
配列とは、複数の値を一度に格納できるデータ構造である。Pythonではリストとして実装され、値の追加、削除、検索などの操作が可能である。リスト（配列）の使い方
リスト名＝[要素１,要素2,要素3,,,,] - for文
for文とは、繰り返し処理を行う制御文である。指定した回数だけ、またはリストや配列の各要素に対して処理を行う。for文（リストを指定）
for 要素を入れる変数 in リスト:
繰り返す処理
- for 変数 in range
range関数を用いたfor文は、指定した回数だけ繰り返し処理を行う。for文（回数を指定）
for カウント変数 in range(回数):
繰り返す処理 - if文
if文とは、特定の条件が満たされたときに限り、一部の処理を行う制御文である。条件が真であればブロック内の処理が実行され、偽であれば実行されない。if文
if 条件式:
条件式が正しい時にする処理
名言解説
Programs must be written for people to read, and only incidentally for machines to execute. Harold (Hal) Abelson
ハロルド（ハル）・アベルソン教授は、マサチューセッツ工科大学(MIT)の電気工学・コンピュータ科学科教授で、その貢献は多岐にわたります。また、彼はクリエイティブ・コモンズとフリーソフトウェア財団の創設事務局長としても知られています。複数の教育賞を受賞しており、彼の教育への情熱とコンピュータ科学への貢献は認められています。
彼の名言、「プログラムは読む人のために書かれなければならない、あとついでに実行できるように。」は、コードを書くときの考え方について重要な洞察を与えています。これは、プログラムがただ機械に動かされるためだけではなく、人間にとって理解しやすく、明確であるべきだという考え方を示しています。
これは、プログラムの読みやすさが重要であることを示しています。コードはチームで開発され、メンテナンスされることが多く、他の人が理解でき、修正できるように書くことが求められます。また、自分自身が後日見返したときに理解できるようにするためにも、コードは明確に書くべきです。
これから、皆さんがコードを書くときは機械だけでなく、人間が読むことを忘れないでください。プログラミングはコミュニケーションの一部であり、よりよいコードは、自分自身と他の人々が理解しやすいように書かれたものです。これからの学習で、アベルソン教授の考え方を心に留めておきましょう。
問題
「クイズをスタート」のボタンをクリックすると、５問出題します。さあチャレンジ！
編集者ひとこと
スマホで学べるブログを目指していますが、コードと文章を同時に表示させるのはちょっと無理があったかもしれません。
理解出来そうもなかったら、いったんメモ用紙にでもコードを書いてみて、文章を追ってみてください。
また、「プログラム」の章と同様に、実行できるプログラムを掲載しています。リストの値を変えたり、探索するあ値を変えてみて、結果がどうなるか試してみてくださいね。
<RANKING>
高校教育ランキング
