Gushwell's C# Dev Notes

WebSite に、
「パズル Magic Star を解く」
の記事を新たに追加しました。

MagicStar とは、下の図の12 個ある○に 1 から 12 までの数字をひとつずつ入れていき、
直線上の4個の数字の合計が、すべて 26 になるように、数字を配置するというパズルです。




これを C# で解いています。
Silverlight で作成しているので、実際に動かして答えを見ることができます。
  

どう書く?orgの「文字列の均等分割」をF#で書いてみました。

一行の文字列を指定した数の行にできるだけ文字数が均等になるように分割してください．
ただし，除算や剰余算を使わないで書いてみてください．

sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく"

divid 4 sample =>
"ゆめよりもはかなき世のなかを"
"なげきわびつゝあかしくらすほ"
"どに四月十よひにもなりぬれ"
"ば木のしたくらがりもてゆく"

問題では、「除算や剰余算を使わないで」とありましたが、それは無視して書いています。
なので、1行の幅の文字数は、簡単に求められるので、
あとは、String.Substringメソッドで、文字列を分割して行くだけです。
気をつける点といえば、「できるだけ均等に」ということなので、１行の文字数は、
最初に求めるのではなく、再帰関数のなかでその都度求めている点でしょうか。

open System open System.Collections.Generic let rec divide (s:string) height = match height with | 1 -> [s] | _ -> let w = (double s.Length) / (double height) let width = int (Math.Ceiling(w)) s.Substring(0,width)::divide (s.Substring(width)) (height-1) let divideAndPrint str height = divide str height |> Seq.iter (printfn "%s") let Main() = let sample = "ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく" divideAndPrint sample 6 printfn "" divideAndPrint sample 5 printfn "" divideAndPrint sample 4 printfn "" divideAndPrint sample 3 printfn "" Console.ReadLine() |> ignore do Main()
問題での例では、divide関数内で、プリントもしていましたが、
ここでは、分割する関数ではプリントはせずに、分割した結果を返すようにしています。
このdivide関数は、string listを返す関数で、再帰呼び出しにより実現しています。
:: 演算子で、 左側の要素と右側のリストを連結しています。


C#のネーミング規則に慣れてしまっているので、ついつい、関数名を大文字で始めてしまいます。
規模の大きなプログラムでは、すべてが小文字で始まると、どれが関数でどれが変数なのかの
判断が付きにくいと思うのですが、他の人はそんなふうには感じないのかな...
まあ、慣れの問題なのでしょうが、そもそも２，３週間に一回程度、F#をいじるだけですから、
慣れようがないです。

  

コッホ曲線を描くプログラムをSilverlight で作成しました。
コッホ曲線とは、フラクタル図形の一種で、線分を3等分し、分割した真ん中の線分を底辺とする
正三角形を描く(ただし底辺は消す)ことを無限に繰り返すことによって得られる図形です。





実際に動くプログラムと、そのソースコードは、Gushwell's C# Programming Page - コッホ曲線 をご覧ください。


ある直線（線分）から、次の点(正三角形の頂点)を求めるロジックが意外と面倒でした。
角度の変換とか、２点間の長さを求めるとか、Sin, Cos関数を使うとかは 普段のプログラムではやっていないので...

  

いげ太さんの記事に触発されて僕も書いてみた。

岩波国語辞典には、再帰→回帰 とあり、回帰の意味を見てみると、

(2) 〔名〕処理手続きや規則の定義に､それ自身を繰り返し使うような仕方｡

とあります。
つまり、C#での再帰処理とは、ある処理をするのに、自分自身のメソッドを繰り返し呼び出す処理のことです。

なお、再帰は、処理だけではなく、構造においても使われます。コンピュータのフォルダ構造が
その身近な例ですね。

さて、それでは、1 から n までの整数の合計(これを sum(n)と表す)を求める処理
について考えてみます。

sum(n) = 1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n
と表せます。

1 から (n-1) までの合計は、というと、sum(n-1) であらわすことができます。

つまり、

sum(n) = sum(n-1) + n
と定義できるわけです。
これが、分かれば、再帰コードを書くことが出来ます。

次のようなコードを書いてみました。

int Sum(int n) { int result = Sum(n-1) + n; return result; }
何をやっているかと言えば、
Sum(n) を求めるには、Sum(n-1) で自分自身のメソッドを呼び出し、1から n-1 の
合計を求め、その結果に n を加えた値を結果として、返しています。

しかし、これには、大きな欠陥があります。
実際に、動かしてもらえば、分かると思いますが、スタックオーバーフローの例外が発生してしまいます。

なぜならば、Sumメソッドが呼ばれたら、その中で、Sumメソッドを呼び出し、さらに、
その中で、Sumメソッドを呼び出し.... を繰り返すわけですから、無限に、Sum を呼び
続けてしまうわけです。

さて、ここで、While 文を使った、同様のコードを見てみましょう。

static int WhileSum(int n) { int result = 0; int i = 0; while (i < n) { result = result + i; i++; } return result; }
このコードでは、無限ループにならないように、i < n でループの終了判定を行っていますね。

再帰のコードも同様に、再帰の終了判定を行わないと、無限にメソッドを呼び続ける
ことになるのです。

ためしに、

class Program { static void Main(string[] args) { Console.WriteLine(Sum(5)); } static int Sum(int n) { Console.Write("{0} ", n); System.Threading.Thread.Sleep(100); int result = Sum(n - 1) + n; return result; } }
とし、実行してみましょう。Sum メソッドに渡ってきた 引数 n をConsole.WriteLineで
表示するコードと、Sleepメソッドを追加しています。

※ 途中で、Ctrl+Cを押して、プログラムを終了させてください。

5 4 3 2 1 0 - 1 - 2 -3 ...
と表示され、Sumの引数に 0 以下の値が渡ってきていることが確認できます。
これを見れば、1 がきたところで、再帰呼び出しをストップすれば良いことがわかります。

それでは、再帰版のSumメソッドに終了判定を入れたいと思います。

static int Sum(int n) { if (n == 1) ; // ここに何を書く？ else return Sum(n - 1) + n; }
※ 一時変数の resultは取り除いています。

問題は、コメントにも書いたように、n が 1の時に何を書くかです。

具体的に、Sum(1) の結果が何かを考えてみると、1 が返ればよいわけですから、
最終的なコードは、次のようになります。

static int Sum(int n) { if (n == 1) return 1; else return Sum(n - 1) + n; } なお、最初に、Sum(n)は、

sum(n) = sum(n-1) + n
と定義できると書きましたが、これはより正確には、

n == 1 の時 Sum(n) = 1 n > 1 の時 Sum(n) = Sum(n-1) + n
となります。
この定義をそのまま、C#のコードに書き下したものが、上記Sumメソッドとなります。
これは、メソッドの定義が、手続き的な「処理の記述」から、問題の構造そのものを表す
「問題の定義」に近くなっていることを示しています。（言い換えると、HowからWhatですね）
コード自体も、とてもすっきりしていますね。whileをつかったコードのごちゃごちゃ感が
こちらにはありません。

ただ、手続きを書くことに慣れているプログラマーには、これでは、どう動くのかが
良くわからないという方も多いと思います。実際に、僕が若いころに再帰を学んだ時はそうでした。

ということで、どう動いているのかを確認してみましょう。
以下のようにデバッグ行を追加してみます。

static void Main(string[] args) { Console.WriteLine(Sum(5)); Console.ReadLine(); } static int Sum(int n) { Console.WriteLine("Sum({0}) called", n); if (n == 1) { return 1; } else { int a = Sum(n - 1); Console.WriteLine("Sum({0}) -> {1}", n - 1, a); return a + n; } }
この結果は、
Sum(5) called Sum(4) called Sum(3) called Sum(2) called Sum(1) called Sum(1) return 1 Sum(2) return 3 Sum(3) return 6 Sum(4) return 10 Sum(5) return 15 15 となります。
これを言葉で言い換えると、次のようになるかと思います。


1. Sum(5)を求めるには、そのひとつ前のSum(4)を知らなければならない、だからSum(4)を呼ぶ。
2. Sum(4)を求めるには、そのひとつ前のSum(3)を知らなければならない、だからSum(3)を呼ぶ。
3. Sum(3)を求めるには、そのひとつ前のSum(2)を知らなければならない、だからSum(2)を呼ぶ。
4. Sum(2)を求めるには、そのひとつ前のSum(1)を知らなければならない、だからSum(1)を呼ぶ。
5. Sum(1) は、1だから、1 を返す。
6. Sum(1)が求まったから、Sum(2) は、Sum(1) + 2 で 1 + 2 になるので、3を返す。
7. Sum(2)が求まったから、Sum(3) は、Sum(2) + 3 で 3 + 3 になるので、6を返す。
8. Sum(3)が求まったから、Sum(4) は、Sum(3) + 4 で 6 + 4 になるので、10を返す。
9. Sum(4)が求まったから、Sum(5) は、Sum(4) + 5 で 10 + 5 になるので、15を返す。


これからわかるように、C#における再帰呼び出しは、メソッドをどんどん深く呼び出し続けるため、
スタックを消費することになります。
大抵の場合は、これでも問題はありませんが、解くべき問題によっては、スタックオーバーが
起こりえます。この点は注意が必要です。

しかし、その欠点を補ってあまりあるパワーが再帰にはあります。
それは、再帰的な構造のデータを処理する際に、発揮されます。
先ほどあげた、フォルダ構造を扱ったり、家系図のような階層構造(Tree構造）のデータを扱う際には、
再帰はとても有効な手段となります。

ボードゲームのような先読みを処理を行うにも、再帰は有効（というか必須）です。
また、リンクリストを扱ったり、今回のような通常の繰り返し処理や、リトライ処理などでも
再帰が使えますね。

なお、いげ太さんの記事では、末尾再帰によるコードが示されていますが、
C#のコンパイラには、末尾再帰の最適化が組み込まれていません。 そのために、ここでは、末尾再帰のコードは示していません。
末尾再帰について知りたければ、こことかここを見てください。



ちなみに、僕のWebサイト「Gushwell"s C# Programming Page」の「C# プログラム小品集」
に掲載したプログラムでも、再帰を使っているプログラムがたくさんあります。
例えば、

階乗の計算
http://gushwell.ifdef.jp/etude/Factorial.html

すべての順列を求める
http://gushwell.ifdef.jp/etude/Permutation.html

ヒルベルト曲線
http://gushwell.ifdef.jp/etude/HirbertCurve.html

8-Queenパズル
http://gushwell.ifdef.jp/etude/nQueen.html

最大面積の領域を求める
http://gushwell.ifdef.jp/etude/MaxArea.html

などです。興味がありましたら、読んでみてください。

  

元ネタ：ホワイトボードプログラミング

僕も再帰を使ったReverseを書いてみた。
題意とちょっと違うかもしれないけど、許してもらおう。
ちゃんとテストしてないけど、だぶん動くと思う。

T[] Reverse<T>(IEnumerable<T> array) { if (array.Count() == 1) return new T[] { array.First() }; return Reverse(array.Skip(1)).Concat(new T[] { array.First()}).ToArray(); }
最後の行のところが、ちょっとぐちゃぐちゃした感じだけど、もうちょっとすっきり書けないのかなー。

追記：ちょと書きなおしてみた。
T[] Reverse<T>(IEnumerable<T> array) { if (array.Count() == 1) return array.ToArray(); return Reverse(array.Skip(1)).Concat(array.Take(1)).ToArray(); }   

再帰メソッドの戻り値を IEnumerable<T>にする場合についてまとめてみました。
順列を列挙するプログラムを例に説明します。
まず、以下のコードを見てください。

class Program { static void Main(string[] args) { Permutation permutation = new Permutation(); permutation.Enumerate(new[] { 1, 2, 3 }); Console.ReadLine(); } } class Permutation { private void Print<T>(IEnumerable<T> nums) { foreach (var x in nums) Console.Write("{0} ", x); Console.WriteLine(); } public void Enumerate<T>(IEnumerable<T> nums) { _GetPermutations<T>(new List<T>(), nums.ToList()); } private void _GetPermutations<T>(IEnumerable<T> perm, IEnumerable<T> nums) { if (nums.Count() == 0) { Print(perm); return; } else { foreach (var n in nums) { _GetPermutations<T>(perm.Concat(new T[] { n }), nums.Where(x => x.Equals(n) == false) ); } } } }
このコードの問題点は、_GetPermutations というメソッドの中で、Printメソッドを 呼び出している点です。
これだと、順列を求めるコードと、求めた順列を使って処理をするコードを明確に 分離することができません。
Permutationクラスは、いろんな場面で使える構造になっていないわけです。 問題が異なれば、Printメソッドの部分を書き直さなくてはなりません。

これを解決する方法のひとつが、イベントやdelegateを使う方法です。
順列が求まるたびに、イベントを発行すれば、Permutationクラスの利用者が Permutationクラスに手を入れることなく、自由に独自の処理を書くことができます。

ただ、この方法にも欠点があります。
例えば、GUIのあるプログラムで、次へボタンを押すたびに、順列をひとつずつ表示する ことを考えて見ましょう。こういった要求には、イベント発行する方法は上手く対応する ことができません。

Permutationクラスの利用する側で、Next メソッドなどを使い、ひとつずつ取り出せれば 良いですよね。
それには、Enumerate メソッドの戻り値を、IEnumerable<T>にするのが良さそうです。

以下に、戻り値を、IEnumerable<T> にしたPermutationクラスを示します。

class Permutation { public IEnumerable<T[]> Enumerate<T>(IEnumerable<T> nums) { return _GetPermutations<T>(new List<T>(), nums.ToList()); } private IEnumerable<T[]> _GetPermutations<T>(IEnumerable<T> perm, IEnumerable<T> nums) { if (nums.Count() == 0) { yield return perm.ToArray(); } else { foreach (var n in nums) { var result = _GetPermutations<T>(perm.Concat(new T[] { n }), // ★ nums.Where(x => x.Equals(n) == false) ); foreach (var xs in result) yield return xs.ToArray(); } } } }
注目すべき点は、再帰メソッドを呼び出して、返ってきた戻り値の扱いです（★印）。
return result とは書けません。
foreachで、一つ一つ要素を取り出し、yield return しています。こうすることで、再帰メソッドで、戻り値をIEnumerable<T>にすることができます。

全ての結果を Listなどに溜め込む方法でも、Enumerateメソッドの戻り値をIEnumerable<T>に出来ますが （この場合は、下請けメソッドの_GetPermutationsの戻り値は、IEnumerable<T>にはなりません）、 全てを列挙し終わらないと、Enumerateメソッドから制御を戻せませんので、 順列の元となる要素数が多い場合には、最初のひとつを取り出すのにも多くの時間を 要してしまい好ましくありません。

では、これを使う側のコードを示します。
まずはforeachで取り出すコード

Permutation permutation = new Permutation(); var items = permutation.Enumerate(new[] { 1, 2, 3, 4 }); foreach (var nums in items) { string s = string.Join(", ", nums.Select(n => n.ToString()).ToArray()); Console.WriteLine(s); }
次に、IEnumerator<T>.MoveNext, IEnumerator<T>.Currentを使うコード

private IEnumerator<int[]> ite = null; private void button1_Click(object sender, EventArgs e) { if (ite == null) { Permutation permutation = new Permutation(); ite = permutation.Enumerate(new int[] { 1, 2, 3, 4 }).GetEnumerator(); } if (ite.MoveNext()) { label1.Text = string.Join(", ", ite.Current.Select(n => n.ToString()).ToArray()); } else { label1.Text = "終了"; } }
ボタンをクリックするごとに、次の順列を取り出し、labelに表示しています。