3の倍数ノード以下のサブツリーに含まれるノードの数

一段落したので,正則コラッツ木生成ツールを改造して3の倍数ノード以下のサブツリーに含まれるノードの数を数えておきたい.正則木で空白となった部分に含まれるノード数と正則木上のノード数の合計が完全正則木のノード総数と一致しなくてはならない.これらの数字が一致しない場合,論理のどこかに穴が空いている可能性がある.

▲キャンセルボタンの動作が少しおかしい.Goボタンを押して,ボタンラベルがContinueになっているとき,Cancelを押しても無視される.⇒デフォルトボタンがGoになっているためフォーカスがGoにあるのではないか?2度押しすると入るので,最初のクリックでフォーカスが移動し,次のクリックでイベントが発生しているように思われる.Goのクリックでウィンドウのフォーカスが変わっているようだ.コンソール出力しているので,コンソールにフォーカスが移っているのではないか?

リリースモードではコンソール出力しないようにしてみたが,変化なし.TopMostをTrueにしても同じ.しかし,Goボタンの場合は,Stopが表示されているときでも即反応する.⇒理由は分からないがこういう動作になっているとするしかないだろう.

Goボタンの表示はGo→Stop→Continue→Goのように変わる.Goが出ているときには,アプリ終了するように仕様変更することにしたが,Stopボタンのとき,Cancelでアプリ終了してしまう.⇒対処した.Goボタン表示しているときには,Cancelではなく,Quitと表示するようにしてみよう.⇒対処した.

▲コラッツ木生成機能の動作がおかしい.指定した樹高より1だけ高い木を生成している.⇒いや,木は生成されていないが,3の倍数としてレンジ外のノードがカウントされている.⇒これは,旧来仕様では不使用となったスロットを使って木を伸長させるような論理になっていたためだ.⇒高さが設定を超えた時点で打ち切るようにした.

不使用ノードは樹高が高くなると急速に増大してゆく.この辺りを数値化するために,充填率というのを導入して計算してみることにした.

充填率R=正則木上の有効ノード数N / 完全正則木ノード数M

ここで,完全k正則木とは最上位のノード以外はすべてのノードがk個の子ノードを持つようなものを言う.つまり,最上階以外には「葉」が存在しないような正則木であるとする.Mは設定された枝数と樹高から計算される完全正則木上のノード数,Nは実際に生成されたコラッツ木のノード数である.3-正則木を高さ1~12まで変化させて充填率を計算してみた.

H=1 MAX=4 valid=4 void=0 total=4 充填率=1
H=2 MAX=13 valid=10 void=3 total=13 充填率=0.769230769230769
H=3 MAX=40 valid=22 void=18 total=40 充填率=0.55
H=4 MAX=121 valid=46 void=75 total=121 充填率=0.380165289256198
H=5 MAX=364 valid=94 void=270 total=364 充填率=0.258241758241758
H=6 MAX=1093 valid=190 void=903 total=1093 充填率=0.173833485818847
H=7 MAX=3280 valid=382 void=2898 total=3280 充填率=0.116463414634146
H=8 MAX=9841 valid=766 void=9075 total=9841 充填率=0.077837618128239
H=9 MAX=29524 valid=1534 void=27990 total=29524 充填率=0.0519577293049722
H=10 MAX=88573 valid=3070 void=85503 total=88573 充填率=0.0346606753751143
H=11 MAX=265720 valid=6142 void=259578 total=265720 充填率=0.0231145566762005
H=12 MAX=797161 valid=12286 void=784875 total=797161 充填率=0.015412194023541

充填率は,1.00→ 0.769→ 0.55→ 0.38→ 0.258→ 0.174→ 0.116→ 0.078→ 0.052→ 0.035→ 0.023→ 0.0154 のように急速に小さくなっている.3正則木(三元木)の場合,3の倍数は全ノードの1/3を占めると思われるが,そのノードより下のノードが存在しないため,実質的には二元木に近いもの(二元木+3の倍数)になっている.この差は階数が大きくなるほど指数関数的に広がるため,充填率が急速に降下するという現象として現れていると見ることができる.コラッツ木は(3の倍数を除く)すべてのノードが無限個の子ノードを持ち,木の高さも無限大になるから,1から遠く隔たった高い梢ではノードの散らばりは相当希薄なものになっていると見ることができるだろう.このような希薄な空間を手探りで探索するというのはほとんど無謀に近いと言える.

この修正はデバッグ用に入れているものなので,リリース版の差し替えは不要だろう.ただし,キャンセルキーの仕様を少し変えている.これはユーザの使い勝手に多少影響するが,軽微な修正なので保留でよいのではないだろうか?そこまで使ってくれる人がいるのかどうか?それよりむしろ「ゼルコバの木」を使ってみたいという要望の方がありそうな気はする…現在の版はコラッツ木専用の作りになっているし,対象がコラッツ木のような単純な木である限りにおいては,それほどボロは出ないような気はするが…

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA