初めに
本記事はアルゴリズムをRubyを使って解説を行なっております。
今回は 線形探索の指定された値の探索 をテーマに解説しています。
アルゴリズムシリーズ第1話
プログラミング学習始めてから7ヶ月くらいが経過したわけですが、やはり就活を視野に入れないといけないわけです。そこで技術記事を書いたら就活で使えるのかなと思いつつも、技術記事の書き方なんてわからないわけで、でもとりあえずやり始めないとなと思っていたところで、今回の記事を書き始めたわけですが、技術記事でこんなにおしゃべりしてるのもおかしいというふうに感じているわけです。なんかワケワケ言ってるワケですが、私だってそりゃあもう打ち勝たねばならぬこと多き現代人ですから、一生懸命学習を進めているのですけど、たまにはこうやって文章書いて気持ちを整理したい時だってあるんですよね。オフがないとオンもできないし、ブレーキがあるからアクセルを強く踏めるわけで、何事も根性だけではうまくいかないんですね〜。でも、ブレーキだけしっかりして馬力の出ない車ってのも誰も乗らないわね〜。 というわけで、この記事は技術記事というものを書いたことがないのでひとまずは簡単なアルゴリズムの解説でも書いてみようと思い始めた続くかもわからないシリーズである。 今回は線形探索の~指定された値の探索~のアルゴリズムを解説していきたいと思う。
では今回の問題文を見ていただきたい。
問題
整数 n と、数列 a_1, ... , a_n と、整数 k が与えられます。
整数 k が数列の何番目にあるかを求めてください。最初の要素 (a_1) を 1 番目とします。
数列に整数 k が複数含まれている場合は、そのすべてについて何番目にあるかを求め、数列を先頭から見たときに現れる順にすべて出力してください。
ただし、整数 k が数列に含まれていない場合は、何も出力しないでください。
この問題はpaizaからの出題です。
問題文をもっと簡単に説明すると、
まず、nというのは配列に含まれている数字の数のこと。つまり、配列が[1, 3, 8, 9, 5, 2, 1]このようになっていたとしたらnは7である。
次に、数列a_1, ... ,a_nというのは、配列に並ぶ数字が0から先ほど示したnまでということである。つまりnが 7 であれば上記の配列のように数字が 7 つしか並ばないということである。
整数kというのは、どの整数でもいいのだが、仮にk = 1としたならば、上記の配列のなかに1は左端と右端にあるので、配列にkは2つあるということになる。
そこで、問題はそのkが配列の中の何番目にあるかと問うているわけである。
n = 7で、[1, 3, 8, 9, 5, 2, 1]この配列があったときに、k = 1ならば、出力される値は1と7になる。この配列において1は配列の1番目と7番目だからである。
なんとなく問題文が何を私たちにして欲しいのかがわかってきたと思う。
次にこれらを行うためのプロセスを言語化していこうと思う。
問題文は長く感じるかもしれないが、この問題文がやって欲しいことは一つ、整数 k が数列の何番目にあるか ということである。そして今回のアルゴリズムは、 kが配列のどこにあるのかを求めるときには、配列の頭から順番に一つ一つkであるかどうかを確認する というものである。
では、これを流れに沿って順番を整理していく。
配列を以下とする。
[1, 3, 8, 9, 5, 2, 1]
n = 7となる
今回はk = 1とする
1 .
0番目からn-1番目まで、今回は0番目から6番目まで(配列を数える時、左端は1ではなく0から始まるので）順番に対応する数字を代入し繰り返し処理を行う。これはkがどれに当たるのかを先頭から一つ一つ確認するためである
[1, 3, 8, 9, 5, 2, 1]
↓ ↓ ↓ ↓ ↓ ↓ ↓
0 1 2 3 4 5 6
2 .
配列の一番左の0番目に当たる1をまずはじめにkであるか確認する。次に左から1番目の3がkであるか確認する。この時にkとその数字が同じだった場合は、その数字が何番目だったかをi番目として、i+1(今回の問題では配列の一番左を1番目とすると書かれているが、私たちは配列の一番左を0として数え始めるため、+1をして何番目なのかを合わせる）として出力する
これを一番右の6番目まで行い、処理を終了する。
3 .
そして、最後は問題にある通り、kに当たる数字が何番目にあったかを縦に出力しろということなので、答えの出力が縦になるようにコードを書く。
では実際のコードを書いていく
まずはじめに、この一連のアルゴリズムをfind_numbersと名付け、(n, 配列, k)は
(7, [1, 3, 8, 9, 5, 2, 1], 1)とする。
def find_numbers(n, array, k)
# ここに処理を書いていく
end
find_numbers(7, [1, 3, 8, 9, 5, 2, 1], 1)
↓
答えとなる数字を保存する空の配列を用意
def find_numbers(n, array, k)
numbers = []
end
find_numbers(7, [1, 3, 8, 9, 5, 2, 1], 1)
↓
先ほど話した1.と2.の処理を書く
0番目からn番目まで順番にi番目として入れていき、i番目に対応する数字がkと同じならi+1と出力
def find_numbers(n, array, k)
numbers = []
(0...n).each do |i|
if array[i] == k
numbers << i + 1
end
end
end
find_numbers(7, [1, 3, 8, 9, 5, 2, 1], 1)
↓
最後に
numbers配列に要素があるかどうか確認して、存在するなら、各要素を一行ずつ出力
def find_numbers(n, array, k)
numbers = []
(0...n).each do |i|
if array[i] == k
numbers << i + 1
end
end
numbers.each { |num| puts num } if numbers.any?
end
find_numbers(7, [1, 3, 8, 9, 5, 2, 1], 1)
以下のような処理が行われていたということである。
i = 0の時: array[1] == 1 → 1 == 1 → true
i = 1の時: array[3] == 1 → 3 == 1 → false
i = 2の時: array[8] == 1 → 8 == 1 → false
i = 3の時: array[9] == 1 → 9 == 1 → false
i = 4の時: array[5] == 1 → 5 == 1 → false
i = 5の時: array[2] == 1 → 2 == 1 → false
i = 6の時: array[1] == 1 → 1 == 1 → true
終わりに
今回初めてアルゴリズムの解説を書いてみたのだが、どうだっただろうか。解説が長く、ひどく丁寧なようで、その実あまり詳しくもないと言った具合だろうか。あくまで私の勉強として書いた記事なのであまり期待はしないでほしい。また、このアルゴリズム解説の中に間違い等がある場合は指摘をしてくれるとありがたく思います。