エンジョイC036回目ダイナミックループ（2020-12-13）

ほえほえ＠スプシマン @hoehoe1234

エンジョイC　36回目 2020-12-13（日） 今日は白本の多重度が変数のループを主に勉強しました。ダイナミックループというやつですね。再帰＋ループを使ってn重のループを実現します。nは例えば、組み合わせる要素の個数により決まります。 出典：Cデータ構造とプログラム pic.twitter.com/TsZqv8wVaC

拡大

ほえほえ＠スプシマン @hoehoe1234

このコードを解析します。main関数はドライバ関数ですね。実際のコードはloopfun関数でたった９行の関数です。しかし、再帰呼び出しがループの中であります。これは何をいみしているのでしょうか？解析します。

ほえほえ＠スプシマン @hoehoe1234

ソースの本体はたった９行です。しかし、ぱっとみただけではこれがどうして多重度がkの変数になっているのかわかりにくいですね。 pic.twitter.com/OPS9RJKnax

拡大

ほえほえ＠スプシマン @hoehoe1234

プログラミングのテクニックの話です。番兵はよく使うテクニックです。最後にどの要素とも違う値を入れておくことで「要素の最後」を別に管理する必要がなくなります。C言語でいえば文字列の終端の\0も番兵ですね。多くの文字列関数は文字の配列（すなわち文字列）の番兵までを文字列と認識します。

ほえほえ＠スプシマン @hoehoe1234

C言語では番兵に入れる値に苦労しますね。値型は含まれる要素と番兵を区別することが一般的には難しいからです。似たような事例ではgetchar関数int型を返すことで文字と終了を区別しています。しかし、VBAでは素晴らしい方法があります。最終要素にCVErrで作ったエラー値を番兵に使えばよいのです。

ほえほえ＠スプシマン @hoehoe1234

エラー値としての-1は上位バイトが1、正しく読めた場合は上位バイトを0とすることで、-1と、文字コードの範囲(0～255）を区別しています。苦肉の策というか、以前はそういうことがあたりまえだったんでしょうね。 pic.twitter.com/1Xx4R1m5z4

拡大

ほえほえ＠スプシマン @hoehoe1234

トップダウン解析です。トップダウン解析では呼び出し元からどのように再帰の木が構築されるか、主要なメンバ（だいたい引数です）を付け加えて書きます。この場合はlf=loopfun、カッコ内は引数とループの範囲となります。 pic.twitter.com/RhG0yTjz3p

拡大

ほえほえ＠スプシマン @hoehoe1234

lf(0, 5～7)であれば、ループの階層が0、ループの範囲が5～7で有ることを表します。ですから、この関数からは3本の線が下に伸びています。それぞれr（階層データを保存する領域）にループのインデックスを保持します。すなわちr[0]=5、r[1]=6、r[2]=7という状態でそれぞれ再帰します。

ほえほえ＠スプシマン @hoehoe1234

左側のlf(1,2～2)が呼ばれたときにはr[0]には5が設定されています。この関数の興味のあるネストは1なので今度はr[1]を2～2のループで回します。このようにして再帰呼び出しを木でトップから順番に解析するのがトップダウン手法ということになります。

ほえほえ＠スプシマン @hoehoe1234

生徒さんからよい質問がでました。再帰についてはどこにデバックプリントを入れるか？という話しです。最大で４箇所に入れます。Aは関数の入り口で、今回で言えば引数kの値とr配列の値を表示します。 pic.twitter.com/Z2iCJpbZpi

拡大

ほえほえ＠スプシマン @hoehoe1234

次にループ中の再帰呼び出しの前、Bの位置にデバック文を入れます。ここではkの表示だけで十分ですね。また、AとBは意味的に同じなのでAの位置だけでよいかもしれません。逆に再帰で分かりにくいのがCの位置です。呼び出す前のA、Bの位置はコードからわかりますが、子供再帰から返ってきたときに

ほえほえ＠スプシマン @hoehoe1234

どこに返ってきたのか？が再帰のコードからは読み取りにくいです。再帰の木でも「戻るときにどうなるか？」が読み取りにくいです。ですからCの位置にデバック文を入れます。これはBと対になっているのでBの位置にもやはり入れたほうがわかりやすいかもしれません。

ほえほえ＠スプシマン @hoehoe1234

最後にリターン前のDの位置にいれます。これは呼び出し元からみるとCの位置の直前ですのでCとDをまとめてCだけでもよいかもしれません。戻り値が何らかの意味がある場合は入れたほうが良いでしょう。しかし、今回は特に必要ないと思います。

ほえほえ＠スプシマン @hoehoe1234

デバック文は必要に応じて入れれば良いのですが、第一候補はAとCの位置となります。このように再帰ではデバック文の位置にもそれぞれ意味があります。

ほえほえ＠スプシマン @hoehoe1234

コードとデータを追ってロジックを理解するのが「解析的手法」となります。この手法を使うことにより「コードが間違いなく動く」ことが確認できます。この図ではセットアップ状態からr配列の内容（左側）とアクション、ループ変数iの状態を右に書いてロジックをなぞって変数の変化を検証します。 pic.twitter.com/H1Mi5dg9zx

拡大

ほえほえ＠スプシマン @hoehoe1234

解析する場合はそれでよいのですが、説明する場合はこれではまだ不十分です。この解析した内容を元に「ロジックがどのような考えで動くのか」を、抽象的、モデル的に構築し直す必要があります。モデルとはすなわち、表とか図です。動作をより高度な表現である図・表・言葉で言い直すということです。

ほえほえ＠スプシマン @hoehoe1234

教科書のお手本の解析木は次の通りとなります。 pic.twitter.com/HIKrOoFlom

拡大

ほえほえ＠スプシマン @hoehoe1234

本日のメインとなった非再帰版のダイナミックループです。オプション課題だったのですが、結果的にこのコードの解析が一番面白かった。とうことになりました。解析できるでしょうか？ pic.twitter.com/n2HxFBXv71

拡大

ほえほえ＠スプシマン @hoehoe1234

実は、塾は勉強であるので理解できるかどうかよりも、何を、どのように考えて工夫したのか？なにがわからなかったのか？またそれをどのように発表するのかが重要です。それがたのしですからね。左がloopfun1関数を解析した結果の発表項目、右が生徒さんの発表内容となります。 pic.twitter.com/XB3ivgnhSg

拡大

ほえほえ＠スプシマン @hoehoe1234

このコードは、ループは２重になっていますが従属変数はiだけです。ですから実質、1重ループです。外側のループは内側が条件を満たしたときのgoto先となっています。それを外側の永久ループにすることにより表示(action関数）したあとにまた内側のループに戻る制御構造になっています。

ほえほえ＠スプシマン @hoehoe1234

言い換えると、内側のループでr配列の内容が1でも変化するとbrekされるので外側ループで①action関数の呼び出しと②iの初期が行われ、かつ、③内側ループの先頭に戻ります。これはbreakの代わりに①②③をbreakのところで行っても同様です。ですから外側ループはgotoとして働くということになります。

ほえほえ＠スプシマン @hoehoe1234

工事士（たぶん）合格おめでとうございます！疲れた体に鞭打って？塾にきたいただきました。実は○んぎ○さん、ものすごい成長をしているといううわさもあります。 pic.twitter.com/0LXJ5GXnVz

拡大

ほえほえ＠スプシマン @hoehoe1234

解析的手法のステップを解説しました。黄色の部分が疑問点です。「解析をしたくてもどうやっていいのかわからない？」というよい質問がでましたので下の水色の通り説明しました。このように一つ一つの手法を覚えて理解することが大切ですね。 pic.twitter.com/vN7TwQESRm

拡大

ほえほえ＠スプシマン @hoehoe1234

C言語では簡潔な記法ができるかわりに分かりにくさを生んでしまいがちです。単項演算子などが該当しますね。演算子の結合順位は後ろ（後置演算子）が先ですが、式の値(e)と副作用が起きるタイミング別なので混乱しがちです。 pic.twitter.com/l3T0HvFPHM

拡大

ほえほえ＠スプシマン @hoehoe1234

これはまた他の生徒さんの解析です。データに注目して解析しています。解析手法には大きく２つあり、１つ目がコードにデータを追記する手法、もう一つがデータをメインに行われるコードを追記する手法です。下は私が追記したものですがiとr配列の変化を追っていっています。