今更感はあるのですが，「既約分数クイズ」の C# 版を書いてみました。既約分数クイズは以下のような問題です。

問題：正の整数Nが与えられているとき、以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズムを示してください。条件は：

• p, qは整数(pは0以上で、qは1以上N以下).
• gcd(p, q) = 1 (pとqの最大公約数は1).
• 0 <= p/q <= 1.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
	static void Main(string[] args)
	{
		const int MaxDenominator = 10;
		foreach (var e in new IrreducibleFractionList(MaxDenominator))
		{
			Console.Write("{0} ", e);
		}
	}
}

public struct Fraction
{
	public static readonly Fraction Zero = new Fraction(0, 1);
	public static readonly Fraction One = new Fraction(1, 1);

	public int Numerator;
	public int Denominator;

	public Fraction(int numerator, int denominator)
	{
		Numerator = numerator;
		Denominator = denominator;
	}

	public override string ToString()
	{
		return string.Format("{0}/{1}", Numerator, Denominator);
	}
}

public static class FractionUtility
{
	public static Fraction Between(Fraction left, Fraction right)
	{
		return new Fraction(left.Numerator + right.Numerator, left.Denominator + right.Denominator);
	}
}

public class IrreducibleFractionList : IEnumerable<Fraction>
{
	private readonly int maxDenominator;
	private readonly LinkedList<Fraction> internalList;

	public IrreducibleFractionList(int maxDenominator)
	{
		this.maxDenominator = maxDenominator;
		internalList = new LinkedList<Fraction>();
	}

	private void Initialize()
	{
		internalList.Clear();
		internalList.AddFirst(Fraction.Zero);
		internalList.AddLast(Fraction.One);
	}

	public IEnumerator<Fraction> GetEnumerator()
	{
		Initialize();

		LinkedListNode<Fraction> left;
		while ((left = internalList.First) != null)
		{
			yield return left.Value;

			LinkedListNode<Fraction> right = left.Next;
			if (right != null)
			{
				while (left != right)
				{
					Fraction middle = FractionUtility.Between(left.Value, right.Value);
					if (middle.Denominator < maxDenominator)
					{
						internalList.AddAfter(left, middle);
					}
					right = right.Previous;
				}
			}

			internalList.RemoveFirst();
		}
	}

	System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
	{
		return GetEnumerator();
	}
}

0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1 

ちなみに他の言語による解答が同一サイトの「既約分数クイズに対する答え」にあります。内容はほぼ同一なのでアルゴリズムの説明は省略します。多少後ろの要素を先に生成して連結リストに保存するようなことは行いますが，全ての要素を最初に計算するということはありません。 IEnumerable<T> を実装しているので LINQ で用いることができます。例えば 1 より大きい分母ごとに既約分数を列挙するには次のようにします。

var group = from e in new IrreducibleFractionList(10)
		group e by e.Denominator into g
		where g.Key > 1
		orderby g.Key ascending
		select g;
foreach (var g in group)
{
	foreach (var e in g)
	{
		Console.Write("{0} ", e);
	}
	Console.WriteLine();
}

1/2 
1/3 2/3 
1/4 3/4 
1/5 2/5 3/5 4/5 
1/6 5/6 
1/7 2/7 3/7 4/7 5/7 6/7 
1/8 3/8 5/8 7/8 
1/9 2/9 4/9 5/9 7/9 8/9 

グループごとの要素数を数えれば，素数判定なんかもできますね。

var group = from e in new IrreducibleFractionList(100)
		group e by e.Denominator into g
		where g.Count() == g.Key - 1
		orderby g.Key ascending
		select g.Key;
foreach (var prime in group)
{
	Console.Write("{0} ", prime);
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

計算速度が遅いので実用性はありませんが，乗除演算が全くないのに素数が生成できるっていうのが不思議で面白いですね。

[note]

• [2010-07-10 00:10] コードの修正: left の宣言位置を変更。
• [2010-07-10 20:10] コードの修正: Fraction.Zero および Fraction.One を readonly に変更。
• [2010-07-10 20:10] コードの修正: 素数取得で Key のみを結果に入れるように変更。

[/note]