[ツリー表示へ] [ワード検索] [Home]
タイトル ： Re^2: サンプル 投稿日 ： 2023/02/18(Sat) 12:21 投稿者 ： 魔界の仮面弁士
| > 私の知るプログラムはコールしたファンクションで答えを求めて > 戻った値について、加算していくなどです。 ファンクションの戻り値で返しても良いのですが、それだと下図に相当する枝分かれを 表現しにくいので、今回は戻り値以外の変数に分岐を加えていく方法を採りました。 https://blog-imgs-67-origin.fc2.com/h/a/t/hatenachips/VBASearchSumAlgos.png > 自分が作成したプログラムに > サンプルを組み込むとエラーになる要因想定できますでしょうか？ まずはエラーメッセージを読みましょう。 そして、エラー発生時にそれぞれの変数の値が何であったのかを確認しましょう。 > また、デバック方法がわからないのと デバックではなく デバッグ(debug)です。 プログラムの不具合のことを bug(バグ) と呼びます。 そのバグを取り除く作業なので、debug(デバッグ) です。 Visual Studio のデバッグ機能について紹介されている記事を貼っておきます。 時間のある時にでも読んでみてください。 https://learn.microsoft.com/ja-jp/visualstudio/debugger/debugging-absolute-beginners?WT.mc_id=DT-MVP-8907&view=vs-2022&tabs=visualbasic 先のコードをデバッグするのであれば、Sub(index, parent) 内の先頭にある 「If Not edge Is Nothing Then」の行にブレークポイントを貼って一時停止してみてください。 その場所からステップ実行を行っていくと、追跡しやすいと思います。 VB のバージョンが古くて、Sub(index, parent) ラムダ式の追跡が難しい場合は、 ラムダ式を使用しない No.12111 のバージョンを試してみるのも良いでしょう。 ついでに、ステップ実行時に分岐内容を見やすくするため、Node クラスに 下記のような DebuggerDisplay 属性を付与しておくと良いでしょう。 一時停止中に、Node 型の変数にマウスカーソルをホバーさせた時や ローカル ウィンドウやウォッチ ウィンドウなどに表示される変数一覧において、 その Node がどこまでの分岐情報を保持しているのか、目視しやくすなります。 https://vb-user.net/junk/replySamples/2023.02.18.11.21/DebuggerDisplay.png <DebuggerDisplay("{ToString}")> Public Class Node Inherits List(Of Node) Public ReadOnly Value As Integer '選択された[値] Public ReadOnly Parent As Node 'ひとつ前に選択した[値] Public ReadOnly Total As Integer '祖先からここまでの[値]の合計 Public Sub New(Parent As Node, Value As Integer) Me.Value = Value Me.Parent = Parent Total = Value + If(Parent Is Nothing, 0, Parent.Total) End Sub Public Overrides Function ToString() As String If Value = 0 Then Return "root, (分岐数=" & Count & ")" Dim sb As New System.Text.StringBuilder(Value.ToString()) Dim n = Parent Do Until n Is Nothing OrElse n.Value = 0 sb.Insert(0, n.Value & "+") n = n.Parent Loop Return String.Format("{0}={1}, 分岐数={2}", sb.ToString(), Total, Count) End Function End Class > Search(i + 1, nextNode) から > Search(0, root)に移って > 再びSearch(i + 1, nextNode) に戻る（？）のでしょうか？ 元の値リストが { ａ, ｂ, ｃ } の 3 パターンだった場合で考えてみましょうか。 ここでは、{ 2, 5, 7 } の組み合わせで、目標値「12」を探すものとします。 すなわち Dim result = FindCombination(12, 2, 5, 7) の処理です。 サンプルコードでいうと、 目標値 = targetValue …… 12 ａ = ordered(0) …… 2 ｂ = ordered(1) …… 5 ｃ = ordered(2) …… 7 にあたります。ここまでは良いでしょうか。 ａ, ｂ, ｃ のすべての組み合わせを考える場合、その分岐はこうなります。 root ┣ａ 終端候補1 … 位置0 ┃┣ｂ 終端候補2 … 位置0,1 ┃┗ｃ 終端候補3 … 位置0,2 ┣ｂ 終端候補4 … 位置1 ┃┗ｃ 終端候補5 … 位置1,2 ┗ｃ 終端候補6 … 位置2 ただし 6 パターンすべてを試すわけではありません。 合計値が目標値を超えるなら、それ以上探索する意味はありませんし、 目標値に合致する組み合わせを見つけたなら、以降の組み合わせをスキップできるためです。 処理の最初は、ルート階層の呼び出しから始まります。 ①【Search(0, root)】を実行します。 ② 位置 0 からの探索なので、For i = 0 To 2 のループに入り、root に続く組み合わせを探します。 ③ ａ は 2。これは 12 に満たないので、さらに【Search(1, root/ａ)】を実行。 ④ 位置 1 からの探索なので、For i = 1 To 2 のループに入り、root/ａ に続く組み合わせを探します。 ⑤ ａ+ｂ は 7。これは 12 に満たないので、さらに【Search(2, root/ａ/ｂ)】を実行。 ⑥ 位置 2 からの探索なので、For i = 2 To 2 のループに入り、root/ａ/ｂ に続く組み合わせを探します。 ⑦ ａ+ｂ+ｃ は 14。これは 12 を超えるので打ち切られます。root/ａ/ｂ/ｃ な組み合わせは生成しません。 ⑧ For ループが終了して End Sub に到達し、【Search(2, root/ａ/ｂ)】の処理が終わります。 ⑨ ａ+ｃ は 9。これは 12 に満たないので、さらに【Search(3, root/ａ/ｃ)】を実行。 ⑩ 位置 3 からの探索なので、For i = 3 To 2 のループに入ります。実際は 0 回ループですね。 ⑪ For ループが終了して End Sub に到達し、【Search(3, root/ａ/ｃ)】の処理を終わります。 ⑫ For ループが終了して End Sub に到達し、【Search(1, root/ａ)】の処理を終わります。 ⑬ ｂ は 5。これは 12 に満たないので、さらに【Search(2, root/ｂ)】を実行。 ⑭ 位置 2 からの探索なので、For i = 2 To 2 のループに入り、root/ｂ に続く組み合わせを探します。 ⑮ ｂ+ｃ は 12。★12 と合致する値を発見★ 終端変数 edge に root/ｂ/ｃ を割り当てて Return します。 ⑯ Return によって終了し、【Search(2, root/ｂ)】の処理を終わります。 ⑰ ｃ は 7。これは 12 に満たないので、さらに【Search(3, root/ｃ)】を実行。 ⑱ 手順⑮の時点で edge が確定済みなので、【Search(3, root/ｃ)】が即時終了します。 ⑲ For ループが終了して End Sub に到達し、【Search(0, root)】が終了します。 ⑳探索終了。変数 edge に 5+12 な組み合わせが入っているので、それを結果として返します。 |
をクリックするとツリー全体を一括表示します） - 組み合わせ合計探索 - たけし 23/02/07-20:51No.12091