2009年06月07日

[パズル](n*2+1)多角形の一筆書き

  
問題
自然数 n を入力した時に、ノード数 n * 2 + 1 の完全グラフを一筆書きするようなプログラムを書いてください。スタートは画面上の一番上胃に位置する頂点とします。 完全グラフとはどの二つの頂点も一本の線で結ばれているグラフのことです。

------
この問題は、本当に一筆書きができているのかを目で確かめたかったのと、動きがあったほうが面白いので、WPFのアニメーションを使ってみました。

OneStroke01 OneStroke02


まずは、問題の本質部分である一筆書きを求めるクラス OneStrokeを作成します。
このコンストラクタで n を受け取り、そこから 正多角形になるように(n*2+1)個の座標を配列にセットします。コメントにも書きましたが、本当は、OneStrokeで扱う座標は、仮の座標であって、表示するときにこの座標から本来の表示座標に変換したいところですが、面倒なので、実際に表示する実座標を扱っています。

GetPointsメソッドが、一筆書きになるような座標のシーケンスを返す部分で、このプログラムの中心になる部分です。実際に動かしてから、このコードを読んでいただいたほうが、理解が早いと思います。
簡単に書くと、まずは左隣の点まで線を順に引いてゆきます。左隣の点までの線が引き終わっていたら、ひとつ置きの点まで線を引き、これを繰り返し、次に2つ置き... と続けてゆきます。
実際には、ここでは点のシーケンスを求めているだけです。

で、実際にWPFで描画しているのが、Window1クラスのほうです。XAML側ではアニメーションの指定は特にしていません。
すべてC#のコードでアニメーションを行っています。WPFについては素人なので、よくわからないんですが、点の数も入力値で決まるので、事前にXAMLで指定しておくことはできないのかな思います。
単に僕がXAMLの書き方を知らないってだけのような気もしますが... どなたかわかる方教えてください。

DrawAnimatedLineメソッドが一つの直線を引くアニメーションを担当しています。で、線が引き終わると、myStoryboard_Completed イベントハンドラが呼び出されるので、ここで、次の線を引くために、再度、DrawAnimatedLineを呼び出し、これを繰り返しています。
そういうことで、Storyboard と DoubleAnimation を使ったC#のサンプルコードとしても面白いものになったかなと思います。

以下、今回のプログラムコードです。



※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51834275