初めに
本記事はアルゴリズムをRubyを使って解説を行なっております。
今回は 特殊な探索~成績優秀者の列挙~ これをテーマに解説しています。
アルゴリズムシリーズ第2話
いつも午後12時にお昼を作りはじめる、といってもインスタントラーメンだったりで大したものは作っていない。
最近はお腹の調子が悪いことが多いから納豆だったりキムチだったりお腹にいいものを食べるように心がけている。つまりは腸活ってやつだ。
午後1時昼食を終えたところで友達から電話がかかってきた、
友人：何やってんだ集合時間に遅れるぞ！
自分：え？なんだっけ？
友人：今日集まるって話だっただろ！もうみんな来てるぞ！
自分：ああ、そうだっけか、まあそうか！でも待って！今お昼食べたばっかだからお皿洗わなきゃ！
友人：そうか、わかったけど2時までには来いよ！
〜〜お皿を洗い始める〜〜
杉浦太陽はお皿洗いのスピードでギネス記録を持っている。ちなみに、みちょぱは水ですすいでお皿を拭くスピードでギネスを持っているらしい。なんてことを考えていたとき、
しばらくして誰かが家を訪ねてきた。
さっき電話をよこした友達のお父さんだった。
友人の父：2時までに集まるんでしょう？早く準備しないとダメじゃないか！
なんで友達のお父さんが家まで来たのかは全くわからないが、まあいいか。
友人の父：皿洗いを手伝うから早くしなさい。
友達のお父さんなんかが登場しちゃったもんだから急がないわけにはいかないし、なんかさっきから皿を洗っている気がする。あれ？待てよ、フライパンをつかって、ラーメン用のでかい器と、小皿と箸しか使ってないのに、まだお皿があるのか。あれ？おかしいなお皿がなくならない、洗っても洗っても新しい食器が出てくる。どういうことだ？怖い、なんか怖い。永遠にお皿洗いが終わらない。時間も迫ってきている。でも皿洗いしないと！やばい！！
という夢をこの前見たんですよね。怖かった〜
最近卒制やったり勉強ももっとしなきゃなとか考えたり焦ることがいろいろあって、そんな時って夢の中でもなんか焦ってたりするよね。でも、今って多分暇な時期なんだよな、これから就職して実際働き始めたらもっと忙しいだろうし。結局人間って常に何かに追われてるんだなぁ。
では今回の問題を見ていただきたい。今回の問題は、特殊な探索~成績優秀者の列挙~です。
問題
n 人の生徒がテストを受けました。このテストで k 点以上 l 点以下の点数を取った人が合格です。
n 人の各生徒について、その人の名前とその人が取った点数が入力として与えられるので、このテストに合格した人の名前をすべて、入力された順に改行区切りで出力してください。
なお、合格者が一人もいない場合は、何も出力しないでください。
これはpaizaからの問題です
ではこの問題の意味を理解していくところから始める。
この問題は簡単にいうと、n人のテストを受けた生徒のうち、テストの点数が、k点以上l点以下の人の名前を出力しろという問題である。
まずnというのは生徒の数のことで、kとlは、問題が要求する点数のこと。
では、このアルゴリズムの手順をまずはじめに日本語で整理してみよう。
入力を受け取る処理
1．生徒の人数を取得
2．n人分の名前と点数を取得
3．合格点の範囲を取得
合格判定
4．k以上l以下なら合格
結果を出力する
5．合格者がいれば出力
大雑把にこの３つの入力、判定、出力に分けることができる。そしてこのアルゴリズムのメインとなる部分は合格判定のアルゴリズムとなる。
それでは、次にこの３つのステップごとにコードに変換していきたいと思う。
入力を受け取る処理
# 生徒の人数を取得
n = gets.to_i
# 生徒の情報を格納する配列
students = []
# n人分の名前と点数を取得
n.times do
line = gets.chomp.split(' ')
name = line[0]
score = line[1].to_i
students << { name: name, score: score }
end
# 合格点の範囲を取得
k, l = gets.chomp.split(' ').map(&:to_i)
上記が入力を受け取る処理である。
まずはじめに生徒の人数を取得するgets。※getsは、キーボードから入力された1行を文字列として受け取るメソッド。
to_iは、文字列を整数に変換するメソッド。つまり生徒の数を整数で受け取るというコードになる。
次にこれらの処理で受け取りたい情報をstudentsとして空の配列を用意して、その次に空の配列に格納したい情報を得るための処理を書く。
まず、n人の生徒の数だけ繰り返し処理を行う、
n.times do
次にlineとして、生徒の情報を格納する。
line = gets.chomp.split(' ')
先ほどgetsに関する説明をしたが、実はgetsは受け取った文字列の最後に改行文字（\n）が含まれている。なのでそれを削除するためにchompメソッドを使う。※chompは、文字列の末尾にある改行文字（\n）を削除するメソッド。
そして、splitは、文字列を指定した区切り文字で分割して、配列にするメソッドで、こうすることで、得たい情報を今回の場合、["alice", "97"]のように名前と点数で、区切って配列にすることができる。
そして、nameとしてlineの0、つまり左から一番目（配列を左から数えるときは0からスタートする）。scoreとしてlineの1番目に整数として格納する。
そしてstudentsにnameとscoreで配列を作り、格納する。
その次に合格点の範囲を取得する。
k, l = gets.chomp.split(' ').map(&:to_i)
mapメソッドは、配列の要素の数だけブロック内で処理を繰り返して、新しい配列を返すメソッドのこと。
ここでは配列で受け取ったものを&:to_iを使い文字列を整数にしている。
つまり、ここでは整数で''で分けて、格納されるということである。
という流れが入力を受け取る流れである。
合格判定
# 合格者を格納する配列
passed_students = []
# 合格判定
students.each do |student|
if student[:score] >= k && student[:score] <= l
passed_students << student[:name]
end
end
上記が合格判定に関するコードである。
まず、今回求めたいk以上l以下の点数の生徒をpassed_students(合格者)とし、空の配列を用意する。その次に、その配列に入れたい情報である、k以上l以下の生徒を判定するコードを書いていく。
合格判定は先ほど入力を受けとる処理の時に作ったstudentsを使い、そのstudentsの数だけ繰り返し処理を行う。
students.each do |student|
次に、
if student[:score] >= k && student[:score] <= l
生徒のscore(先ほど作ったもの)がk以上かつ生徒のscoreがl以下だったならば、
passed_students << student[:name]
passed_students(合格者)に生徒のname(先ほど作ったもの)を追加する。
結果を出力する
passed_students.each do |name|
puts name
end
最後に配列に生徒の名前が格納されたpassed_studentsを繰り返し処理し、生徒の名前を出力する。この時、繰り返し処理で名前を一つずつ出力するのは、問題が名前を縦に改行区切りで出力しろといっているからである。
n = 5
alice 97
bob 25
carol 57
dave 46
ellen 10
k = 35, l = 80
今回の問題では入力は以上のようになっている
以下はこの処理の一連の流れである。
passed_students = [] ← 空の配列を用意
students.each で繰り返し:
1回目: student = { name: "alice", score: 97 }
├ score(97) >= k(35) → true
├ score(97) <= l(80) → false
└ 97 >= 35 && 97 <= 80 → false
→ passed_studentsには追加しない
2回目: student = { name: "bob", score: 25 }
├ score(25) >= k(35) → false
├ score(25) <= l(80) → true
└ 25 >= 35 && 25 <= 80 → false
→ passed_studentsには追加しない
3回目: student = { name: "carol", score: 57 }
├ score(57) >= k(35) → true
├ score(57) <= l(80) → true
└ 57 >= 35 && 57 <= 80 → true ⭕️
→ passed_students << "carol"
4回目: student = { name: "dave", score: 46 }
├ score(46) >= k(35) → true
├ score(46) <= l(80) → true
└ 86 >= 35 && 86 <= 80 → true ⭕️
→ passed_students << "dave"
5回目: student = { name: "ellen", score: 10 }
├ score(10) >= k(35) → false
├ score(10) <= l(80) → true
└ 49 >= 35 && 49 <= 80 → false
→ passed_studentsに追加しない
passed_students = ["carol", "dave"]
passed_students.each で出力:
1回目: name = "carol"
→ puts "carol"
2回目: name = "dave"
→ puts "dave"
終わりに
今回は2回目のアルゴリズムの記事だったのだが、どうだっただろうか。以前とは違いステップに分けて解説したりしてみたのだが、わかりやすくなったのだろうか。
アルゴリズムを学習する手順のようなものがあれば理解もしやすいし、解説しやすくもなるのだがまだそのようなものがつかめていないので、数をこなすしかないのだろう。
また、このアルゴリズム解説の中に間違い等がある場合は指摘をしてくれるとありがたく思います。