パソコン・メモメモ備忘録

気の向くままパソコン関係等で気になることを書き記す。毎日更新を目指す!

可変階層の多重ループ

プログラミングを始めてからかれこれ 30 年以上経った今でも、割と基本的な事で悩む場合がある。今回は、これ、多重ループで、多重度が場合によって変わるもの。具体的には、平面上(まぁ空間上でも同じだが)に多数の点が散らばっていて、それらの中に、ある個数の点からなる図形が潜んでいるので、それを見つける問題。今回は、回転も拡大縮小も無いので(180度回転はあるのだが)、全解探索すればいいかな、と。その場合に、一番シンプルな実装は、という話。多少の誤差はあったり、は余り本質的じゃないかな。

この潜んでいる図形というのが、いくつかあって、それぞれ構成する点の数が違う。図形からと多数の点から一つずつ点を選んで、図形の平行移動量を仮定し、残りの点(図形を構成する)に対応する点(多数の点の一つ)があるかを、ひとつずつ探していく感じか。残りの点の個数だけループ(多数の点を一つずつチェックする)を重ねれば良いわけではある。

一番シンプルに書けるのが、再帰呼出しを使う方法。再帰呼出しの深さが、ループの多重度になるようにすれば、割とシンプルにコードが書ける。まぁ、これが一番かな。再帰の階層ごとに、結構スタックに色々積まないといけなくて、階層もそこそこ深くなるようだとちょっとまずい場合もあるかもしれない。意外にスタックに容量を振ってないこともあるそうな。

理論的には、再帰呼出しは、全て普通のループに変換できる。自分でスタックを実装すれば良いだけ。このスタックはヒープ上に確保すれば、スタックの容量を気にする必要もない。再帰呼出しでも、特別な場合(後再帰とか)は、超簡単にループに変換できるが、今回のようなのは無理かな。

回転、拡大縮小がある場合も、二つ目の点を対応付けた際に、回転角度や拡大率を仮定して、更に先の点を対応付けていけばいいだけか。まぁ、今回はいらないけど。