2012年03月03日
ナイト(騎士)巡回問題
ナイト巡回問題とは、チェスのナイトを、チェス盤の上を動かし、すべてのマスを通り、
最初の場所に戻ってくる経路を求めるというものです。
Gushwell's C# Programming Pageに掲載しました。
ナイト(騎士)巡回問題
C＃＋ Silverlightで解いています。
最初の場所に戻ってくる経路を求めるというものです。
Gushwell's C# Programming Pageに掲載しました。
ナイト(騎士)巡回問題
C＃＋ Silverlightで解いています。
2012年02月15日
素因数分解小町
WebサイトGushwell's C# Programming page に、「素因数分解した結果が小町になる数を求める」を掲載しました。
これは、ある整数 N を素因数分解したときに、因数が1-9をひとつずつ使っている Nを求める、
というものです。いくつかの制約を加えて、C#で解いています。
世の中に小町数マニアのような人がいるのかどうかわかりませんが、小町数に関するこの手の
数学パズル問題はいろいろあります。
このGushwell"s C# Programing Page のプログラム小品集でもこれまでに、この問題も含めて
７つ取り上げています。
こんな面白い小町数問題があるよ、という方がいれば、是非お教えください。
これは、ある整数 N を素因数分解したときに、因数が1-9をひとつずつ使っている Nを求める、
というものです。いくつかの制約を加えて、C#で解いています。
世の中に小町数マニアのような人がいるのかどうかわかりませんが、小町数に関するこの手の
数学パズル問題はいろいろあります。
このGushwell"s C# Programing Page のプログラム小品集でもこれまでに、この問題も含めて
７つ取り上げています。
こんな面白い小町数問題があるよ、という方がいれば、是非お教えください。
2011年11月13日
パズル Magic Star をC#で解く
WebSite に、
「パズル Magic Star を解く」
の記事を新たに追加しました。
MagicStar とは、下の図の12 個ある○に 1 から 12 までの数字をひとつずつ入れていき、
直線上の4個の数字の合計が、すべて 26 になるように、数字を配置するというパズルです。
これを C# で解いています。
Silverlight で作成しているので、実際に動かして答えを見ることができます。
「パズル Magic Star を解く」
の記事を新たに追加しました。
MagicStar とは、下の図の12 個ある○に 1 から 12 までの数字をひとつずつ入れていき、
直線上の4個の数字の合計が、すべて 26 になるように、数字を配置するというパズルです。
これを C# で解いています。
Silverlight で作成しているので、実際に動かして答えを見ることができます。
2011年09月13日
コッホ曲線をSilverlightで作成
コッホ曲線を描くプログラムをSilverlight で作成しました。
コッホ曲線とは、フラクタル図形の一種で、線分を3等分し、分割した真ん中の線分を底辺とする
正三角形を描く(ただし底辺は消す)ことを無限に繰り返すことによって得られる図形です。
実際に動くプログラムと、そのソースコードは、Gushwell's C# Programming Page - コッホ曲線 をご覧ください。
ある直線（線分）から、次の点(正三角形の頂点)を求めるロジックが意外と面倒でした。
角度の変換とか、２点間の長さを求めるとか、Sin, Cos関数を使うとかは 普段のプログラムではやっていないので...
コッホ曲線とは、フラクタル図形の一種で、線分を3等分し、分割した真ん中の線分を底辺とする
正三角形を描く(ただし底辺は消す)ことを無限に繰り返すことによって得られる図形です。
実際に動くプログラムと、そのソースコードは、Gushwell's C# Programming Page - コッホ曲線 をご覧ください。
ある直線（線分）から、次の点(正三角形の頂点)を求めるロジックが意外と面倒でした。
角度の変換とか、２点間の長さを求めるとか、Sin, Cos関数を使うとかは 普段のプログラムではやっていないので...
2011年08月22日
パズル:コイン150
久しぶりに、Gushwell's C# Programming Pageのプログラム小品集のページに、「コイン150」 というプログラムを追加しました。
Silverlightアプリとして作成しています。
問題は以下の通り。
解は一つではなく、たくさんあります。その中のいくつかを求めるだけならば、
プログラムを使わなくても、手動で解けるので、興味ある方は自力で解いてみてください。
「コイン150」という名前は、僕が勝手につけたものです。
Silverlightアプリとして作成しています。
問題は以下の通り。
縦6×横6の升目の中に、100円玉6個、50円玉6個を入れてください。
そのとき、縦 ６列、横６列、対角線2列の合計14列の、どこも合計が150円になるようにしてく ださい。
解は一つではなく、たくさんあります。その中のいくつかを求めるだけならば、
プログラムを使わなくても、手動で解けるので、興味ある方は自力で解いてみてください。
「コイン150」という名前は、僕が勝手につけたものです。
2011年07月18日
部分和問題を動的計画法で解く
部分和問題とは、
「与えられた n 個の整数(集合A)と 整数 X があった時に、集合Aから任意の数の整数を選び、
その数の和（部分和）が、X に等しくなるような、部分集合を求める」 というものです。
たとえば、 [3,7,8,12,13,18] の部分和が 27 になる部分集合は、[7,8,12] となります。
このような問題を解くには、バックトラックでも解くことは可能ですが、要素の数が多くなると
組合せの数が増えすぎて、対応できなくなることもあり得ます。
このような時に利用するのが、動的計画法です。
僕のWebサイト「Gushwell's C# Programming Page」に、この部分和問題を解くプログラムコードを掲載しました。
興味のある方はどうぞ。
「与えられた n 個の整数(集合A)と 整数 X があった時に、集合Aから任意の数の整数を選び、
その数の和（部分和）が、X に等しくなるような、部分集合を求める」 というものです。
たとえば、 [3,7,8,12,13,18] の部分和が 27 になる部分集合は、[7,8,12] となります。
このような問題を解くには、バックトラックでも解くことは可能ですが、要素の数が多くなると
組合せの数が増えすぎて、対応できなくなることもあり得ます。
このような時に利用するのが、動的計画法です。
僕のWebサイト「Gushwell's C# Programming Page」に、この部分和問題を解くプログラムコードを掲載しました。
興味のある方はどうぞ。
2011年05月29日
交通流のモデル (ASEPモデル) のプログラム
Webサイト「Gushwell's C# Programming Page」の「C#プログラム小品集」に、「交通流のモデル (ASEPモデル)」のプログラムを掲載しました。
一本道を多くの人が一列で歩く場合のシミュレーションをするというものです。
Silverlightで作成しています。
開始ボタンを押せば、プログラムが開始します。
ソースコードも掲載しています。
一本道を多くの人が一列で歩く場合のシミュレーションをするというものです。
Silverlightで作成しています。
開始ボタンを押せば、プログラムが開始します。
ソースコードも掲載しています。
2011年03月31日
N寄生数
Webサイト Gushwell's C# Programming Pageに『N寄生数』の記事を掲載しました。
C#のソースコードも載せています。
N寄生数とは、
ある整数をA 、Aの一桁目の数値を N としたときに、 A を N 倍すると、右へ一桁分ローテートシフトし、
Nが最上位桁に移る数 のなかで最小の数を言います。 ただし、2<=N<=9 とします。
例えば、N=4 の時は、102564 となります。
102564 * 4 = 410256
となり、右にローテートシフトします
興味のある方は、N=6の時の値を求めてみてください。
C#のソースコードも載せています。
N寄生数とは、
ある整数をA 、Aの一桁目の数値を N としたときに、 A を N 倍すると、右へ一桁分ローテートシフトし、
Nが最上位桁に移る数 のなかで最小の数を言います。 ただし、2<=N<=9 とします。
例えば、N=4 の時は、102564 となります。
102564 * 4 = 410256
となり、右にローテートシフトします
興味のある方は、N=6の時の値を求めてみてください。
2011年02月27日
カプレカ数
Gushwell's C# Programming Pageの「C#プログラム小品集」に、「カプレカ数」を求めるプログラムを掲載しました。
カプレカ数とは、
2乗した値を前の部分と後ろの部分に分けて、その和を取ったとき、元の値に等しくなる数
のことです。
カプレカ数とは、
2乗した値を前の部分と後ろの部分に分けて、その和を取ったとき、元の値に等しくなる数
のことです。
2010年11月03日
リングバッファー
「簡易tailコマンド」をGushwell's C# Programming Pageの「C#プログラム小品集」に掲載しました。
リングバッファークラスを作成し、それを使うことで、tailコマンドを実装しています。
このtailコマンドで使うことだけを考えて書いたRingBufferクラスなので、
突っ込みどころがいろいろとあるかと思いますが、興味のある方は、RingBufferの一つの実装例としてどうぞ。
リングバッファークラスを作成し、それを使うことで、tailコマンドを実装しています。
このtailコマンドで使うことだけを考えて書いたRingBufferクラスなので、
突っ込みどころがいろいろとあるかと思いますが、興味のある方は、RingBufferの一つの実装例としてどうぞ。
2010年07月25日
ナイト(騎士)の最適配置問題
チェスのナイト（騎士）を以下の規則に従って配置するパズルです。
1．すべての空きがどれかのナイトの効き筋になっていること。
複数のナイトから効いていてもかまわない。
2. ナイト同士は互いに効き筋にはない。
3. なるべく少ない数のナイトで配置する。
「プログラミング小品集」に掲載する中では、久しぶりに長めのプログラムでした。
そして実行時間も...
この手のパズルは解を求めるのに時間がかかるのは仕方がないとは思うけど、もう少し速くしたかったなー。
求まった解を見てみると、対称性をもったきれいな配置だなーって思います。
ところで、デバッグ中に、chromeで動かしてみたら、ブラウザがエラーを表示してしまいました。
どうも、長時間 Silverlightからの応答がないのが理由のようでした。
そのため、Backgroundworkerを使い、応答なしを回避しました。IEだと大丈夫なのにね。
ソースコードはこちらに掲載しています。
1．すべての空きがどれかのナイトの効き筋になっていること。
複数のナイトから効いていてもかまわない。
2. ナイト同士は互いに効き筋にはない。
3. なるべく少ない数のナイトで配置する。
「プログラミング小品集」に掲載する中では、久しぶりに長めのプログラムでした。
そして実行時間も...
この手のパズルは解を求めるのに時間がかかるのは仕方がないとは思うけど、もう少し速くしたかったなー。
求まった解を見てみると、対称性をもったきれいな配置だなーって思います。
ところで、デバッグ中に、chromeで動かしてみたら、ブラウザがエラーを表示してしまいました。
どうも、長時間 Silverlightからの応答がないのが理由のようでした。
そのため、Backgroundworkerを使い、応答なしを回避しました。IEだと大丈夫なのにね。
ソースコードはこちらに掲載しています。
2010年06月21日
ラングトンのアリ
「ラングトンのアリ」のプログラムは、多くのサイトで動くものが公開されていますが、
Silverlightで公開している方は、いないようなので、昔作ったものを Silverlightに移植してみました。
Silverlightで別スレッドから、BeginInvokeを呼び出し、UIスレッドで描画するサンプルとしてどうぞ。
ソースコードはこちらに掲載しています。
ランダムに動いているアリが、突然規則的に直線の道を作り出すのって不思議ですね。
2010年02月21日
番兵というテクニック
昨日、プログラム小品集に「最大面積の領域を求める」プログラムを載せましたが、
そこで、プログラミングテクニックの一つである番兵を使っています。
というか、以前このブログでも書いた、共通クラスであるBoardクラスで、 実際のボードの周りに番兵用のデータを置いています。
これのおかげで、
と書かなくてはいけないところで、
と書くことができます。
ちょっと違いが分かりにくいですが、Rangeメソッドの第２引数が違っています。
番兵が無いと、配列の範囲を超えないようにインデックスをインクリメント していく必要があります。
しかし、番兵があるおかげで、インデックスの範囲オーバーを気にせずに、 「黒石が続くあいだだけ繰り返す」という処理を書くことができます。
最近「番兵」という言葉を聞くこ/見ることがほとんどないので、ここにアップします。
というか、以前このブログでも書いた、共通クラスであるBoardクラスで、 実際のボードの周りに番兵用のデータを置いています。
これのおかげで、
と書かなくてはいけないところで、
と書くことができます。
ちょっと違いが分かりにくいですが、Rangeメソッドの第２引数が違っています。
番兵が無いと、配列の範囲を超えないようにインデックスをインクリメント していく必要があります。
しかし、番兵があるおかげで、インデックスの範囲オーバーを気にせずに、 「黒石が続くあいだだけ繰り返す」という処理を書くことができます。
最近「番兵」という言葉を聞くこ/見ることがほとんどないので、ここにアップします。
