メインコンテンツへスキップ
見出し画像

線形探索を覚えて欲しい!

    こんにちは「つけらっとゲームス」プログラム担当のとちです。

    ゲームを作る他に専門学校のシステム系学科で外部講師もやってます。
    今回は「フローチャートを覚えて欲しい!」の記事中で予告していた線形探索について、詳しくお話したいと思います。

    情報関連の勉強をしていて「学校で習ったけどよくわからん」という方や、これからプログラムを勉強しようという方にオススメの内容です。

    プログラミング学習の関連記事は以下にまとめてます!


    線形探索とは?

    たくさんあるデータの中から必要なモノを探し出す探索アルゴリズム、つまり、処理の考え方のひとつです。

    前回「フローチャートを覚えて欲しい!」の記事中に出てきたフローチャートも線形探索だったりしますが、前回はさらっと説明しただけなので改めて記事にまとめてみました。

    基本情報技術者試験にて「アルゴリズムと擬似言語プログラミング」に出てくる中でも基本的な考え方になりますし、それ以外でもアルゴリズムを学ぶ上でも基本形として覚えておくと何かと便利です。

    例題

    それでは9教科のテストの点数表を例に説明しますね。
    このデータは配列Mei と配列Ten に入っているとします。

    画像
    (例:9教科のテストの点数表データ)

    では、この中から英語の点数を知りたいとします。
    人間の目でも探せるデータ量なので、そこまで大変じゃありません。

    英語の点数は84点です。
    アルゴリズムとは処理の手順や考え方でしたよね。
    これをプログラムでやりたい場合、どういう手順なのか想像しましょう。

    線形探索ではデータの先頭(または末尾)から必要なデータかどうかを確認していきます。上記の例ですと英語が必要なデータです。

    配列の先頭に入っているデータは国語です。英語ではありません。
    配列の次に入っているデータは数学です。英語ではありません。
    配列の次に入っているデータは理科です。英語ではありません。
    配列の次に入っているデータは社会です。英語ではありません。
    配列の次に入っているデータは英語です。見つけました! 84点です!

    線形探索での処理手順を想像してみました!

    フローチャート

    もう少し詳しく、わかりやすく処理の流れを表現してみます。
    これが前回のメインテーマでした。
    処理の流れを図で表現したものをフローチャート(流れ図)と言います。

    画像

    つまり、このフローチャートが線形探索の基本的な形になります。
    線形探索の説明としては、これで終わりですがもう少し勉強を進めますね。

    プログラムコード

    では、フローチャートからプログラムコードを書いてみましょう。
    今回はVBAで処理してみます。
    VBAは以下の記事に詳しくありますので気になった方はご覧ください。

    では、あらためて…こんな感じのユーザーフォームを作りました。
    ExcelのSheet1に教科名と点数が設定されています。

    画像

    フォームのコンボボックスから教科名を選んで「点数検索」ボタンをクリックすると点数を表示します。例では英語の点数を知りたいので英語を選んで「点数検索」をクリックしています。

    プログラムコードはこんな感じです。

    Option Explicit
    Dim Ten(8) As Integer                               '【配列定義】点数のデータが入る配列
    Dim Mei(8) As String                                '【配列定義】教科のデータが入る配列
    
    '────────────────────────────────────────────────────────────
    '
    ' ユーザーフォームがアクティブになった時に発生する
    '
    '────────────────────────────────────────────────────────────
    Private Sub UserForm_Activate()
        
        Dim ix As Integer                               '【変数定義】配列にデータを入れるための添字
        
        For ix = 0 To 8                                 '■ 初期データを代入しておくループ
            Ten(ix) = Sheet1.Cells(ix + 1, 2).Value     '├ Sheet1の点数を配列Tenに代入
            Mei(ix) = Sheet1.Cells(ix + 1, 1).Value     '├ Sheet1の教科を配列Tenに代入
            ComboBox1.AddItem (Mei(ix))                 '└ ユーザーフォームのコンボボックスで選べるように教科を入れておく
        Next ix
        
        ComboBox1.Text = Mei(0)                         'ユーザーフォームのコンボボックスの初期値をMei(0)つまり国語にしておく
    
    End Sub
    
    '────────────────────────────────────────────────────────────
    '
    ' 【線形探索】
    '  点数検索のボタンを押された時に発生する
    '
    '────────────────────────────────────────────────────────────
    Private Sub CommandButton1_Click()
        
        Dim ix    As Integer                            '【変数定義】配列探索のための添字
        Dim wName As String                             '【変数定義】入力された教科名
        
        wName = ComboBox1.Text                          'コンボボックスで選ばれた教科名をwNameに代入する
        
        Do While wName <> Mei(ix)                       '■ wNameとMei(ix)が違う場合は以下を繰り返すループ
            ix = ix + 1                                 '└ 添字ix を1ずつ増やす
        Loop
        
        MsgBox Ten(ix)                                  'Ten(ix)をメッセージボックスで表示する
    
    End Sub

    今回のフローチャートで表現したプログラムコード(線形探索)は
    「Private Sub CommandButton1_Click()」 から 「End Sub」 までです。
    全体の下半分くらいですね。

    なんか面倒臭くない?

    そうですよね、そう思いますよね。
    英語の点数なんて表をみればすぐに見つけられますし、エクセルならわざわざVBAでプログラムを組まなくても検索したらすぐに見つかります。

    わたしも実際にゲームを作る時に、上記のようなプログラムを組みません。
    Unity(c#)でRPGを作っているとしましょう。
    武器の攻撃力が欲しい、アイテム番号で配列を探索する場合は…

    添字 = Array.IndexOf(配列名,アイテム番号)

    これで配列の中を探索してくれます。

    「じゃぁ覚える必要ないの?」

    いや、覚えた方がいい、線形探索がアルゴリズムとして資格試験などに出てくるのは線形探索を覚えるというより、その考え方を覚えて欲しいんですよ、きっと!

    線形探索を表現する為には、配列についても理解が必要だし、添字を変数定義して探索するので、変数についても理解が必要です。

    前にもチラっと触れましたが、他のアルゴリズムを理解するうえでも、覚えていた方が何かと便利なんです。

    というわけで、もうちょっと勉強を進めてみますね。
    こういうのは何個かの例題を解いて覚えちゃうのが一番です!


    探索データを用いてデータを探す

    ゲームに限らず、システムは色々なデータで構成されています。
    単純に「〇〇番号のデータは何?」という例題だけでは作ったプログラムが本当に便利なモノかわからない!

    そこで、少しだけ複雑になりますが別の例題で説明しますね。

    例題(2)

    どっかの生鮮食料品店のデータだと思ってください。
    大まかにデータが分かれています。
    配列群sは商品データが、配列群uは売り場/分類データが入っています。

    配列群sの売り場番号sUNo と、配列群uの売り場番号uUNoは関連付けられているデータです。

    では問題、指定された野菜が置かれている売り場はどこでしょう?
    大型書店でも本を検索する端末がありますよね、あれと同じで野菜の名前を入れたら売り場が表示される仕組みを考えてみましょう。

    画像

    では処理手順を想像してみます。
    もしハクサイが指定されたら?

    入力されるのは商品名、表示したいのは売り場です。
    配列群sには商品名があります。
    配列群uには売り場があります。

    まずは配列群sから売り場番号を見つけます!
    次に配列群uから売り場を見つけないといけません!

    配列群s、配列sNameでハクサイを線形探索します。
    配列の先頭はリンゴです。ハクサイではありません。
    配列の次はミカンです。ハクサイではありません(繰り返し…)
    配列の次はハクサイです。見つけました。売り場番号sUNoは12です。

    売り場番号を取得できました。

    配列群u、配列uUNoで12を線形探索します。
    配列の先頭は1です。12ではありません。
    配列の次は2です。12ではありません(繰り返し…)
    配列の次は12です。見つけました。売り場は「2番通路 北側」です。

    処理手順を想像してみました!

    フローチャート(2)

    処理手順をなんとなく思い浮かべることができました。
    これをフローチャートにしてみましょう。
    難しく考えると、どこまでも難しくなるので問題を小分けに考えます。

    画像

    前半で商品名を使って線形探索し、売り場番号を取得します。
    フローチャートの真ん中あたりにある赤文字までが、その部分ですね。

    後半では、前半で取得できた売り場番号を使って線形探索して売り場を探しています。難しいと思ったら問題を分けて解決していきましょう。

    プログラムコード(2)

    では、フローチャートからプログラムコードを書いてみましょう。

    エクセルで以下のようなデータがあって、ユーザーフォームのコンボボックスで選んだ商品から売り場を表示するプログラムを作ります。
    (テストの点数を表示するプログラムを改造しました!)

    画像
    Option Explicit
    
    '--- 配列群s「商品データ」---
    Dim sNo(20)   As Integer                                      '【配列定義】商品番号 のデータが入る配列
    Dim sName(20) As String                                       '【配列定義】商品名  のデータが入る配列
    Dim sUNo(20)  As Integer                                      '【配列定義】売り場番号のデータが入る配列
    
    '--- 配列群u「売り場/分類データ」---
    Dim uUNo(20)   As Integer                                     '【配列定義】売り場番号のデータが入る配列
    Dim uText(20)  As String                                      '【配列定義】売り場    のデータが入る配列
    Dim uBName(20) As String                                      '【配列定義】分類名    のデータが入る配列
    
    '────────────────────────────────────────────────────────────
    '
    ' ユーザーフォームがアクティブになった時に発生する
    '
    '────────────────────────────────────────────────────────────
    Private Sub UserForm_Activate()
        
        Dim ix As Integer                                         '【変数定義】配列にデータを入れるための添字
        
        For ix = 0 To 20                                          '■ 初期データを代入しておくループ
            If Sheet2.Cells(2, ix + 3).Value = 0 Then Exit For    '├ 商品番号がZeroだったらループを抜ける
            sNo(ix) = Sheet2.Cells(2, ix + 3).Value               '├ Sheet2の商品番号  を配列sNo   に代入
            sName(ix) = Sheet2.Cells(3, ix + 3).Value             '├ Sheet2の商品名  を配列sName に代入
            sUNo(ix) = Sheet2.Cells(4, ix + 3).Value              '├ Sheet2の売り場番号を配列sUNo  に代入
            ComboBox1.AddItem (sName(ix))                         '└ ユーザーフォームのコンボボックスで選べるように教科を入れておく
        Next ix
        
        For ix = 0 To 20                                          '■ 初期データを代入しておくループ
            If Sheet2.Cells(8, ix + 3).Value = 0 Then Exit For    '├ 売り場番号がZeroだったらループを抜ける
            uUNo(ix) = Sheet2.Cells(8, ix + 3).Value              '├ Sheet2の売り場番号を配列uUNo  に代入
            uText(ix) = Sheet2.Cells(9, ix + 3).Value             '├ Sheet2の売り場  を配列uText に代入
            uBName(ix) = Sheet2.Cells(10, ix + 3).Value           '└ Sheet2の分類名  を配列uBNameに代入
        Next ix
        
        ComboBox1.Text = sName(0)                                 'ユーザーフォームのコンボボックスの初期値をsName(0)にしておく
    
    End Sub
    
    '────────────────────────────────────────────────────────────
    '
    ' 【線形探索】
    '  売り場検索のボタンを押された時に発生する
    '
    '────────────────────────────────────────────────────────────
    Private Sub CommandButton1_Click()
        
        Dim wName As String                                       '【変数定義】入力された商品名
        Dim i     As Integer                                      '【変数定義】配列群sの探索のための添字
        Dim j     As Integer                                      '【変数定義】配列群uの探索のための添字
        
        wName = ComboBox1.Text                                    'コンボボックスで選ばれた商品名をwNameに代入する
        
        Do While wName <> sName(i)                                '■ wNameとsName(i)が違う場合は以下を繰り返すループ
            i = i + 1                                             '└ 添字i を1ずつ増やす
        Loop
        
        Do While sUNo(i) <> uUNo(j)                               '■ sUNo(i)と uUNo(j)が違う場合は以下を繰り返すループ
            j = j + 1                                             '└ 添字j を1ずつ増やす
        Loop
        
        MsgBox uText(j)                                           'uText(j)をメッセージボックスで表示する
    
    End Sub
    

    今回のフローチャートで表現したプログラムコード(線形探索)は
    「Private Sub CommandButton1_Click()」 から 「End Sub」 までです。
    全体の下半分くらいですね。

    上半分はエクセルのシートから各配列にデータを代入しているプログラムコードです(問題の前提とか必要なデータをここで準備しちゃってるんです)

    今回の記事ではコードそのものは詳しく説明しませんが、
    コード内にコメントで解説を付けているので興味があったら1行ずつ中身を確認していくとよいでしょう。

    独学するときは、
    誰かが書いたコードそのものが参考になるんですよ!
    いや割とマジで!


    おわりに

    いかがでしたでしょうか?
    「線形探索」理解できたでしょうか?

    資格試験や学校での勉強で出てくるかもしれない…ので勉強するというのも大事ですが、プログラムを組む上でアルゴリズムを頭の中に幾つも持っておくと、長いプログラムを組む時に少し楽になります。

    線形探索は探索アルゴリズムのひとつですし、色々なデータを扱うシステムを構築する際の基本的な考え方として覚えておくと今後の為になるはずです。

    〇〇データベースからあのデータを取得して、××配列からそのデータを取得して突き合わせると、△△データを算出できる。

    …みたいな処理、作ったりしますもん!

    基本的なアルゴリズムについて今後も記事にまとめていきたいと思います。
    内容的に基本情報技術者試験の問題集にも書いていると思いますが、
    こちらの記事では「なぜそれが必要なのか知りたい」とか「授業中に理解できなかったから復習する」といった方に発信していけたらと思います!


    すごく難しそうなことを書いていますが、普段はこんなゲームを作っているサークルの人です。ご興味がございましたらご覧ください(↓)

    それでは、また別の記事でお会いできるのを楽しみにしております!

    あなたへのおすすめ