情報学入門(データ演習) / 第 10 章

構造化プログラミング(2)

部品を組み合わせる ── 互除法・篩・フィボナッチ

この章のねらい

資料について。 元資料「155-2019」のもくじは、前の回の「150-2019」とまったく同じです (副手続き/関数副プログラム/並べ替え/総和/階乗/最大公約数)。 実際の中身は4 枚目以降から始まる新しい題材 (互除法の関数化・エラトステネスの篩・フィボナッチ数列)なので、 この章はそこを扱います。前半の内容は第 9 章にあります。

1. 互除法を関数にする(元資料 4〜6 枚目)

ユークリッドの互除法を用いて、2 つの正の整数の最大公約数を求めよ。 さらに、最小公倍数も求めよ。
「繰り返し」で扱ったプログラムを関数とせよ。割り算(÷)を用いた例題。

第 8 章で書いた互除法を、そのまま関数に切り出すという課題です。 これは構造化プログラミングの典型的な流れです ── まず動くものを書き、それから部品に切り出す

元資料 5 枚目は、関数の見出しをこう書いています。

最大公約数を求める関数
ggcd(ByVal m, ByVal m) 返り値 最大公約数(整数型)

引数の名前が両方とも m になっています。 VBA でこう書くとコンパイルエラー(「引数の名前が重複しています」)になり、 実行できません。2 つの数を受け取るのですから、 ggcd(ByVal m As Long, ByVal n As Long) のように別の名前が必要です。

なお関数名が全角の ggcd になっていますが、 これは資料の書体の問題で、実際には半角の ggcd です (VBA では日本語の名前も使えますが、全角英字は避けるのが無難です)。

Sub Macro1()
    Dim a As Long, b As Long
    Dim g As Long

    a = Cells(1, 2).Value
    b = Cells(2, 2).Value

    g = ggcd(a, b)                     ' 関数を呼ぶだけ

    Cells(4, 1) = "最大公約数 GCD"
    Cells(4, 2) = g
    Cells(5, 1) = "最小公倍数 LCM"
    Cells(5, 2) = a * b / g            ' もとの a, b が残っているので使える

    ' 関数にしておけば、何組でも続けて呼べる
    Cells(7, 1) = "GCD(1071, 1029)"
    Cells(7, 2) = ggcd(1071, 1029)
    Cells(8, 1) = "GCD(17, 5)"
    Cells(8, 2) = ggcd(17, 5)
End Sub

Function ggcd(ByVal m As Long, ByVal n As Long) As Long
    Dim r As Long

    Do While n <> 0
        r = m Mod n                    ' 余りを求める
        m = n
        n = r
    Loop

    ggcd = m
End Function

関数にすると、最小公倍数の問題が自然に解けます。 第 8 章では、互除法が変数 K と Y を壊してしまうので もとの値を別に保存する必要がありました。 関数にすれば、書きかえられるのは関数の中のコピーByVal なので)だけなので、 呼び出した側の ab は無事です。 だから a * b / g がそのまま書けます ── 部品に切り出すと、変数を壊す心配が消えるのです。 これが関数の大きな利点です。

ByValByRef(または省略)にすると、 呼び出し元の a と b が 12 と 0 に書きかえられてしまいます。 上のプログラムで試してみてください ── 最小公倍数が正しく出なくなります。 第 9 章の「書きかえない引数には ByVal」が、ここで効いてきます。

2. エラトステネスの篩(元資料 7〜10 枚目)

エラトステネスの篩を用いて、1〜100 までの素数を求めよ。 素数とは、2 以上の整数で 1 とその数以外に約数を持たない数である。

第 8 章では「約数の個数を数える」方法で素数を判定しました。 篩(ふるい)は考え方がまったく違います ── 割り算をせずに、倍数を消していくだけです。

手順。
① 2 から 100 までを並べる
② いちばん小さい未確定の数を素数と決める(最初は 2)
③ その数の倍数をすべて消す(4, 6, 8, … を消す)
④ 次の未確定の数へ(3 → その倍数 6, 9, 12, … を消す)
⑤ 調べる数が √100 = 10 を超えたら終わり。残っているものが全部素数

動かす② エラトステネスの篩を目で見る 1 段ずつ
Sub Macro2()
    Dim keshita(101) As Boolean       ' 消したかどうかを覚える
    Dim i As Integer, j As Integer
    Dim n As Integer
    Dim kosuu As Integer

    n = 100

    ' ② 2 から順に、まだ消されていなければ素数
    For i = 2 To n
        If keshita(i) = False Then
            ' ③ その倍数を消す(i*i から始めれば十分)
            For j = i * i To n Step i
                keshita(j) = True
            Next j
        End If
    Next i

    ' 表に並べる(10 列)
    For i = 1 To n
        Dim gy As Integer, rt As Integer
        gy = Int((i - 1) / 10) + 1
        rt = ((i - 1) Mod 10) + 1
        Cells(gy, rt) = i
        If i >= 2 And keshita(i) = False Then
            Cells(gy, rt).Interior.Color = RGB(198, 239, 206)   ' 素数
            kosuu = kosuu + 1
        Else
            Cells(gy, rt).Font.Color = RGB(180, 180, 180)
        End If
    Next i

    Cells(12, 1) = "素数の個数"
    Cells(12, 2) = kosuu
End Sub

1〜100 の素数は 25 個です。 プログラムの要点は 2 つあります。

割り算を 1 回もしていないところが篩の値打ちです。 足し算(Step ii ずつ進む)だけで素数が求まります。

3. フィボナッチ数列(元資料 11・12 枚目)

fib(1) = 1、fib(2) = 1、 fib(n) = fib(n−1) + fib(n−2)
n = 24 までの値を求めよ。

「前の 2 つを足す」という定義です。1, 1, 2, 3, 5, 8, 13, 21, … と続きます。 定義そのものが「自分自身を使う」形(再帰的な定義)になっていますが、 繰り返しでも書けます。この章では繰り返しで書き、 第 14 章で再帰そのままの書き方と比べます。

Sub Macro3()
    Dim n As Integer

    Cells(1, 1) = "n": Cells(1, 2) = "fib(n)": Cells(1, 3) = "比 fib(n)/fib(n-1)"

    For n = 1 To 24
        Cells(n + 1, 1) = n
        Cells(n + 1, 2) = fib(n)
        If n >= 3 Then
            Cells(n + 1, 3) = Format(fib(n) / fib(n - 1), "#.########")
        End If
    Next n
End Sub

Function fib(ByVal n As Integer) As Long
    Dim i As Integer
    Dim a As Long, b As Long, t As Long

    If n <= 2 Then
        fib = 1
        Exit Function              ' ここで抜ける
    End If

    a = 1: b = 1                   ' fib(1), fib(2)
    For i = 3 To n
        t = a + b                  ' 次の値
        a = b                      ' ずらす
        b = t
    Next i

    fib = b
End Function

3 つの変数 abt でずらしていくのが要点です。 第 9 章の交換と同じで、a = b を先に書くと もとの a が失われるので、t に足した結果を退避しています。
fib(24) = 46368。 そして 3 列目の比を見てください ── 1.6180339… に近づいていきます。 これは黄金比((1+√5)/2)です。 定義には出てこない数が、計算していくと現れる ── 数列のおもしろいところです。

Exit Function の使い方。 n <= 2 のときは答えが決まっているので、 そこで関数を抜けています。 これがないと、下のループが 3 から n(=1 や 2)まで回ることになり、 1 回も実行されないので b の初期値がそのまま返ってしまいます (この場合は偶然正しいのですが、意図が読み取れません)。 「先に特別な場合を片づけて抜ける」のは読みやすい書き方で、 第 14 章の再帰では必須になります(終了条件)。

4. スコープ ── 変数が見える範囲

元資料は触れていませんが、手続きに分けると必ずぶつかる問題です。 第 9 章で swapRefswapVal の両方に Dim t As Integer と書きましたが、衝突しませんでした。 なぜでしょうか。

モジュール(ファイル全体)
Dim goukei As Long ' ← どの Sub からも見える
Sub Macro1()
Dim i As Integer ' ← この Sub の中だけ
Sub Macro2()
Dim i As Integer ' ← 別の箱。上の i とは無関係
どこに Dim を書くか見える範囲いつ消えるか
Sub / Function の中その手続きの中だけ(ローカル変数 手続きが終わると消える
いちばん上(Sub の外)同じファイルのすべての手続き(モジュール変数 ブックを閉じるまで残る
Dim zentai As Integer          ' モジュール変数(どこからも見える)

Sub Macro4()
    Dim i As Integer           ' Macro4 の i

    i = 100
    zentai = 5

    Cells(1, 1) = "Macro4 の i": Cells(1, 2) = i
    Cells(2, 1) = "zentai":      Cells(2, 2) = zentai

    Call betsuno

    ' betsuno の中で i を 999 にしたが……
    Cells(5, 1) = "呼んだあとの Macro4 の i"
    Cells(5, 2) = i
    Cells(6, 1) = "呼んだあとの zentai"
    Cells(6, 2) = zentai
End Sub

Sub betsuno()
    Dim i As Integer           ' こちらの i は別の箱

    i = 999                    ' Macro4 の i には影響しない
    zentai = zentai + 1        ' モジュール変数は共有されている

    Cells(3, 1) = "betsuno の i": Cells(3, 2) = i
End Sub

i は 100 のまま、zentai は 6 になります。 同じ名前でも、別の手続きの中なら別の箱です。 だからこそ、どの手続きでも安心して it を使えます。

モジュール変数は、便利ですが危険です。 どの手続きからでも書きかえられるので、 「いつ、どこで値が変わったのか分からない」という不具合を生みます。 第 5 章の GoTo と同じ理由です ── 追えなくなるのです。
原則は「必要な値は引数で渡し、結果は戻り値で返す」。 モジュール変数を使うのは、本当に全体で共有する必要があるとき (第 14 章のハノイの塔で手数を数えるときなど)に限ります。

5. よい部品の分け方

元資料は「機能毎に分割」と書いていますが、 どこで切るかは経験がいるところです。目安を 4 つ挙げます。

Sub Macro5()
    Dim i As Integer
    Dim a As Long, b As Long, g As Long

    Cells(1, 4) = "GCD": Cells(1, 5) = "LCM": Cells(1, 6) = "互いに素か"

    For i = 2 To 5
        a = Cells(i, 2).Value
        b = Cells(i, 3).Value

        g = ggcd(a, b)                  ' 部品①:最大公約数
        Cells(i, 4) = g
        Cells(i, 5) = a * b / g         ' 最小公倍数
        Cells(i, 6) = IIf(g = 1, "はい", "いいえ")

        If g = 1 Then Cells(i, 6).Interior.Color = RGB(255, 235, 156)
    Next i

    Cells(7, 1) = "関数が 1 つあるだけで、4 組ぶんが 1 つのループで片づく"
End Sub

Function ggcd(ByVal m As Long, ByVal n As Long) As Long
    Dim r As Long
    Do While n <> 0
        r = m Mod n
        m = n
        n = r
    Loop
    ggcd = m
End Function

6. まとめ

  1. まず動くものを書き、それから部品に切り出す(互除法 → ggcd
  2. 関数に切り出すと、ByVal のおかげで呼び出し元の変数が壊れない
  3. エラトステネスの篩は割り算をせず、倍数を消すだけi×i から消し始めれば十分
  4. フィボナッチは3 つの変数でずらして計算できる。比は黄金比に近づく
  5. ローカル変数は手続きの中だけ。同じ名前でも別の箱
  6. モジュール変数は追えなくなるので、原則は引数と戻り値でやりとりする
  7. よい部品は1 つの仕事・分かる名前・計算だけ・引数は少なく

章末問題

付録:元資料からの修正一覧

もとにしたのは「情報学入門(VBA)155-2019」全 24 枚です。

元資料この教材種別
5 枚目の関数の見出し ggcd(ByVal m, ByVal m) 引数の名前が両方 m で重複している。VBA では 「引数の名前が重複しています」というコンパイルエラーになる。 ggcd(ByVal m As Long, ByVal n As Long) のように別の名前が必要誤り
もくじが前の回(150-2019)とまったく同じ 実際の新しい内容は 4 枚目以降。この章はそこ(互除法の関数化・篩・フィボナッチ)に絞った重複
関数名が全角の ggcd半角の ggcd。全角英字は避ける表記
関数にすると何が良くなるのかが書かれていない ByVal なので呼び出し元の変数が壊れず、 第 8 章で必要だった「もとの値の保存」が要らなくなることを示した不足
篩のプログラムで、消し始めをどこにするかの説明がない i×i から始めれば十分な理由(小さい素数のときに既に消えている)を明示不足
篩と第 8 章の「約数を数える」方法の違いに触れていない 篩は割り算を 1 回も使わない(足し算だけ)ことを要点として示した不足
スコープ(変数が見える範囲)の説明がない §4 として追加。手続きに分けたら必ずぶつかる問題で、 モジュール変数の危険(追えなくなる)まで書いた不足
フィボナッチの値を求めるだけ 3 変数でずらす仕組み、Exit Function の使い方、 比が黄金比に近づくことを追加。第 14 章の再帰版への伏線にした不足
部品の分け方(どこで切るか)の指針がない§5 として 4 つの目安を追加不足

元資料で正しかったこと。 「繰り返しで扱ったプログラムを関数とせよ」という課題の立て方 (まず動くものを書いてから部品に切り出す、という順序)、 割り算を用いた互除法を採っている点、 フィボナッチ数列の定義(fib(1)=1、fib(2)=1、fib(n)=fib(n−1)+fib(n−2))、 エラトステネスの篩の課題設定と素数の定義、 返り値の型を「整数型」と明示している点 ── いずれも適切です。 fib(24) = 46368 になることも確認しました。