Excel&VBA解説サイト「エクセルの神髄」様出題の問題集、
「VBA100本ノック」に対する私の回答と解説のページです。
100本ノックの出題リストはこちらから
excel-ubara.com
出題：トリボナッチ数列
#VBA100本ノック 50本目
記念すべき50本目は数学です。
直前の三項の和として各項が定まるトリボナッチ数列を出力してください。
0,0,1,1,2,4,7,13,24,44,81,149,274,…
最初の0,0,1は固定です。
※エクセルの限界まで出力してみましょう。
※出力先は任意
50本記念なので、密かな裏お題を2つほど
・再帰の練習にやってみるのもよいかも。
・VBAの整数の桁数の限界に挑戦、どこまでいけるのかな。
◇ 出題ページはこちら
ソースコード
Sub トリボナッチ数列を計算する_Long型() With ws出力シート Dim nー3項 As Long: nー3項 = 0: .Cells(1, 1) = 0 Dim nー2項 As Long: nー2項 = 0: .Cells(2, 1) = 0 Dim nー1項 As Long: nー1項 = 1: .Cells(3, 1) = 1 Dim n項 Dim n As Long: n = 4 On Error GoTo 計算限界 Do n項 = nー1項 + nー2項 + nー3項 .Cells(n, 1) = "'" & n項 nー3項 = nー2項 nー2項 = nー1項 nー1項 = n項 n = n + 1 Loop End With Exit Sub 計算限界: MsgBox "Long型の限界は" & n - 1 & "項で値は" & nー1項 & "です。" End Sub
解説
トリボナッチ数列を求める問題です。
普通に変数を使うだけなら上記のような単純なコードで行けますね。
変数名のーは日本語の伸ばし棒を使っています。
a n = a n-1 + a n-2 + a n-3
の式になるべく合わせた変数名にしたかったので苦肉の策です。
上記コードのLong型を変更することで、各型の限界を調べることができます。
- Long型なら第39項の2082876103
- LongLong型なら第75項の7015254043203144209
- Decimal型なら第112項の43458307810949238672214594009
Decimalを使えば相当な桁数を扱えますが、
実務ならLongLong型でも十分な値を扱えますね。
※ トリボナッチ数列は正確には第0項からスタートします。
今回は行番号と一致させるため、便宜上第1項スタートで解説しています。
ちなみにDecimal型は「As Decimal」という宣言ができないため、
Variant型変数にCDec関数を使って代入する必要があります。
Sub トリボナッチ数列を計算する_Decimal型() With ws出力シート Dim nー3項 As Variant: nー3項 = 0: .Cells(1, 1) = 0 Dim nー2項 As Variant: nー2項 = 0: .Cells(2, 1) = 0 Dim nー1項 As Variant: nー1項 = 1: .Cells(3, 1) = 1 Dim n項 Dim n As Long: n = 4 On Error GoTo 計算限界 Do n項 = CDec(nー1項 + nー2項 + nー3項) .Cells(n, 1) = "'" & n項 nー3項 = nー2項 nー2項 = nー1項 nー1項 = n項 n = n + 1 Loop End With Exit Sub 計算限界: MsgBox "Decimal型の限界は" & n - 1 & "項で値は" & nー1項 & "です。" End Sub
小数誤差を極限まで減らしたいときに使ったりしますので、
この仕様も頭の片隅に置いておいてください。
裏課題
裏課題についても解説しておきます。
まずは再帰処理がこちら。
再帰呼出を用いた処理
Sub トリボナッチ数列を計算する_再帰() ws出力シート.Cells(1, 1) = 0 ws出力シート.Cells(2, 1) = 0 ws出力シート.Cells(3, 1) = 1 Call トリボナッチ数列をセルに出力する(4, 0, 0, 1) End Sub Sub トリボナッチ数列をセルに出力する(n As Long, nー3項 As Long, nー2項 As Long, nー1項 As Long) On Error GoTo 計算限界 Dim n項 As Long n項 = nー1項 + nー2項 + nー3項 On Error GoTo 0 ws出力シート.Cells(n, 1) = "'" & n項 Call トリボナッチ数列をセルに出力する(n + 1, nー2項, nー1項, n項) Exit Sub 計算限界: MsgBox "Long型の限界は" & n - 1 & "項で値は" & nー1項 & "です。" End Sub
結構単純に書けてコード量も少ないため、
問題文の通り、再帰の練習にちょうど良い難易度に思います。
セルをひとつの数値とみなして足し算のひっ算処理
続いてExcelの限界挑戦です。
これには様々な方法があると思いますが、
「Excelの」ということでシートを活用してやってみました。
「各セルを1桁の数値」に見立てて足し算のひっ算を自作してみます。
' 1セルにつき1桁を扱い、最終列から始めて足し算のひっ算と同じ要領で計算 Sub トリボナッチ数列を計算する_1セル1桁版() With ws出力シート ws出力シート.UsedRange.Cells.Clear Application.ScreenUpdating = False ' 初期値3項を出力 Dim シート最終列 As Long: シート最終列 = .Columns.Count .Cells(1, シート最終列) = 0 .Cells(2, シート最終列) = 0 .Cells(3, シート最終列) = 1 ' ひとまず第1000項までを計算 Dim R As Long For R = 4 To 1000 ' 列を右からループ Dim C As Long For C = シート最終列 To 1 Step -1 ' 上のセルが空なら次の項へ If .Cells(R - 1, C) = "" Then Exit For ' 対象列の前3項の合計＋ひとつ右の列からの繰り上がり分を計算 Dim 上3セル合計 As Double: 上3セル合計 _ = .Cells(R - 1, C) _ + .Cells(R - 2, C) _ + .Cells(R - 3, C) _ + .Cells(R, C) ' ← ひとつ右列からの繰り上がり分 ' A列で繰り上がりが発生したら終了 If C = 1 And 上3セル合計 >= 10 Then Exit For ' 対象セルに合計の1の位、その左セルに10の位を出力 .Cells(R, C) = 上3セル合計 Mod 10 If 上3セル合計 >= 10 Then .Cells(R, C - 1) = 上3セル合計 \ 10 End If Next Next Application.ScreenUpdating = True End With End Sub
この手法を使えば理論値としてはXFD列、すなわち16384桁を計算できます。
およそ第62,200項までを計算できるようですが、
実際のところは計算時間とメモリの問題で結構大変になります。
どちらもO(n²)で増加していきますので、セル上でやると10時間かかりますし、
配列でやるとメモリが足りず、かなりの回数を分割実行する必要がでますからね。
ひとまず「セルをひとつの数値とみなす」手法ではこれが限界になります。
各セルに15桁ずつ数値を格納して足し算のひっ算処理
上記の手法ではわかりやすく「1セル1桁」で処理を書きましたが、
Excelは16桁までを扱えるため、繰り上がりを考慮し各セル15桁を分担できます。
画像のように16桁目になったらひとつ左の列を使うということですね。
ソースコードがこちらになります。
' 1行につき1項を計算する。 ' 各セルに15桁を出力し、16桁を超えるごとに次の列を使用する ' すなわち、第n項の値＝第n行のすべてのセルを&でつなげたものとなる Sub トリボナッチ数列を計算する() With ws出力シート ws出力シート.UsedRange.Rows.Delete Application.ScreenUpdating = False ' 初期値3項を出力 Dim シート最終列 As Long: シート最終列 = .Columns.Count .Cells(1, シート最終列) = 0 .Cells(2, シート最終列) = 0 .Cells(3, シート最終列) = 1 ' ひとまず第1000項までを計算 Dim R As Long For R = 4 To 1000 ' 列を右からループ Dim C As Long For C = シート最終列 To 1 Step -1 ' 前3項の合計＋ひとつ右の列からの繰り上がり分を Dim 上3セル合計 As Double: 上3セル合計 _ = .Cells(R - 1, C) _ + .Cells(R - 2, C) _ + .Cells(R - 3, C) _ + .Cells(R, C) ' ← ひとつ右列からの繰り上がり分 ' 値がなくなったら次の項へ If 上3セル合計 = 0 Then Exit For ' A列で繰り上がりが発生したら終了（実際はここまで行けない） If C = 1 And 上3セル合計 > 1E+15 Then Exit For ' 繰り上がりごとの分岐 ' セルを10^16で割った商で計算するのはオーバーフローで不可 ' 1000未満の3つの数値を足した値は3000未満であるため、 ' 発生する繰り上がりは2が上限である Select Case 上3セル合計 ' 繰り上がりなし Case 0 To 1E+15 - 1 .Cells(R, C) = 上3セル合計 ' 繰り上がりが1 Case 1E+15 To 2E+15 - 1 .Cells(R, C) = 上3セル合計 - 1E+15 .Cells(R, C - 1) = 1 ' 繰り上がりが2 Case 2E+15 To 3E+15 - 1 .Cells(R, C) = 上3セル合計 - 2E+15 .Cells(R, C - 1) = 2 End Select ' 繰り上がり発生時は0埋め If .Cells(R, C - 1) > 0 Then .Cells(R, C).NumberFormatLocal = String(15, "0") End If Next ' 今何列までを使用したかを表示 If R Mod 57 = 0 Then Debug.Print .Cells(1, C).Address(False, False) ' トリボナッチ数列は56または57項ごとに15桁を消費する Next Application.ScreenUpdating = True End With End Sub
この桁数で繰り上がりを商で求めるのは怖いので、
繰り上がり処理は場合分けで頑張っています。
999+999+999は3000を超えませんので、
繰り上がりのSelect Case は0,1,2の3つで済みますからね。
この手法を使えば理論値としてはXFD列まで15桁ずつ、
すなわち16384*15 = 245,760桁を計算できます。
およそ第934,000項までを計算できるようですが、
実際のところは計算時間とメモリの問題で困難そうです。
第30000項まで頑張ってみましたが、この時点でファイルサイズは100MB、
1回の実行で計算できる項数は10000を切ってしまいました。
このままいくとXFD列を使い切る頃にはファイルサイズは1GBを超えますし、
「実行→保存→Excelを閉じてメモリ開放」を200回以上やる必要があるようです。
処理時間より保存と開きなおしにかかる時間の方がつらそうですよね。
ギガバイトを超えるExcelファイルを作ってみたかったのですが断念しました笑
なお、30000項まで出す場合はシート上ではもう計算できるレベルでなくなるため、
以下の配列を使ったコードで分割実行を行っています。
メモリを節約するために4つの静的配列のみを使いまわしてみましたが、
この規模だと焼け石に水だったようですね。
悔しいですが、和風スパっぽい列に到達した項を記録しておきます。
あらためてXFD列がいかに遠いかを実感しました。
遠い未来のExcelでは一瞬で計算できることを夢見て、
このファイルを冷凍保存しておきたいと思います。
Sub トリボナッチ数列を計算する_配列による分割計算() With ws出力シート Dim R_開始行 As Long: R_開始行 = Get最終行(ws出力シート) - 2 ' 16384×行数分の配列は確保できないので、 ' 16834要素の一次元配列を4つ用意して使いまわす Dim Arr親配列(1 To 4) Dim Arr各行(1 To 16384) Arr親配列(4) = Arr各行 ' シート上の初期値3行分を配列へ格納 Dim R As Long, i As Long For i = 1 To 3 R = R_開始行 + i - 1 ' メモリを節約するために静的配列にループで格納 Dim シート最終列 As Long: シート最終列 = .Columns.Count Dim C As Long For C = シート最終列 To 1 Step -1 Arr各行(C) = ws出力シート.Cells(R, C) Next Arr親配列(i) = Arr各行 Next ' 1万行ずつ処理（これでも5万行を超えるとメモリ不足となった） For R = R_開始行 + 3 To R_開始行 + 10002 i = ((R - 1) Mod 4) + 1 Arr親配列(i)(シート最終列) = Empty ' 使いまわす4回前の配列の初期化 ' 列を右側からループ For C = シート最終列 To 1 Step -1 ' 前3項の合計＋一つ右の列からの繰り上がり分を計算 Dim 上3セル合計 As Double: 上3セル合計 _ = Arr親配列(1)(C) _ + Arr親配列(2)(C) _ + Arr親配列(3)(C) _ + Arr親配列(4)(C) ' ← ひとつ右列からの繰り上がり分 If 上3セル合計 = 0 Then Exit For ' A列で繰り上がりが発生したら終了（ここまではいかなかった） If C = 1 And 上3セル合計 > 1E+15 Then Exit For ' 繰り上がりごとの分岐 Select Case 上3セル合計 ' 繰り上がり0 Case 0 To 1E+15 - 1 Arr親配列(i)(C) = 上3セル合計 Arr親配列(i)(C - 1) = Empty ' ← 配列使いまわしの初期化を兼ねる ' 繰り上がり1 Case 1E+15 To 2E+15 - 1 Arr親配列(i)(C) = 上3セル合計 - 1E+15 Arr親配列(i)(C - 1) = 1 ' 繰り上がり2 Case 2E+15 To 3E+15 - 1 Arr親配列(i)(C) = 上3セル合計 - 2E+15 Arr親配列(i)(C - 1) = 2 End Select ' 繰り上がりが発生した場合は書式で0埋め If Arr親配列(i)(C - 1) > 0 Then .Cells(R, C).NumberFormatLocal = String(15, "0") End If Next ' この行の配列をセルへ出力 .Rows(R).Value = Arr親配列(i) Next End With End Sub
