結城浩
2004年1月7日
既約分数クイズに対して、 たくさんの人から解説求むというメールが来てしまったので、 Java版とPerl版を解答します。
ポイントは、makeBetweenメソッドです。
import java.util.*;
class Fraction {
int up;
int down;
public Fraction(int up, int down) {
this.up = up;
this.down = down;
}
public Fraction makeBetween(Fraction right) {
return new Fraction(this.up + right.up, this.down + right.down);
}
public String toString() {
return up + "/" + down;
}
}
class FractionList {
Vector vector = new Vector();
public void append(Fraction f) {
vector.add(f);
}
public Fraction get(int index) {
return (Fraction)vector.get(index);
}
public int size() {
return vector.size();
}
public String toString() {
String s = "";
for (int i = 0; i < vector.size(); i++) {
s = s + vector.get(i) + ", ";
}
return s;
}
}
class MainApp {
public static void main(String[] args) throws Exception {
for (int N = 1; N < 10; N++) {
System.out.println("N = " + N);
FractionList list = new FractionList();
list.append(new Fraction(0, 1));
list.append(new Fraction(1, 1));
boolean stable = false;
while (!stable) {
FractionList next = new FractionList();
stable = true;
for (int i = 0; i < list.size(); i++) {
Fraction left = list.get(i);
next.append(left);
if (i + 1 < list.size()) {
Fraction right = list.get(i + 1);
Fraction middle = left.makeBetween(right);
if (middle.down <= N) {
next.append(middle);
stable = false;
}
}
}
list = next;
}
System.out.println(list);
}
}
}
実行結果。 各列が、値の小さい順になっていることにもご注目。
N = 1 0/1, 1/1, N = 2 0/1, 1/2, 1/1, N = 3 0/1, 1/3, 1/2, 2/3, 1/1, N = 4 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1, N = 5 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1, N = 6 0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1, N = 7 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1, N = 8 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1, N = 9 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,
実行結果は上と同じ。
use strict;
for my $N (1..9) {
print "N = $N\n";
my $stable = 0;
my @list = ("0/1", "1/1");
while (not $stable) {
$stable = 1;
my @newlist;
my $left = shift @list;
while (@list) {
push(@newlist, $left);
my $right = shift @list;
my ($upL, $downL) = split(m|/|, $left);
my ($upR, $downR) = split(m|/|, $right);
my ($upM, $downM) = ($upL + $upR, $downL + $downR);
if ($downM <= $N) {
push(@newlist, "$upM/$downM");
$stable = 0;
}
$left = $right;
}
push(@newlist, $left);
@list = @newlist;
}
print join(", ", @list), ", \n";
}
既約分数クイズの解答として結城が示したのは、 スターン・ブロコット木の一部を使ってファレイ(Farey)数列を構成する方法です。 スターン・ブロコット木(Stern-Brocot Tree)というのは以下に示すような、 分子と分母を加算して作り出す木です。 不思議な美しさがありますね。
（参考： 『コンピュータの数学』p.116, p.118)
いつも素晴らしいテキストを公開・翻訳してくださる Shiro Kawaiさんからの解答をいただきましたので、ご紹介します。
nobsunさんのHaskellによる解答も知りました。
前原さんのC言語版です。
既約分数クイズに対する解答として、 sumimさんからSmalltalk/Squeak版が到着しました！ ご紹介します。
向井さんのページで、 既約分数の列挙問題という解答。OCaml 版。
Python版です。 ご連絡感謝します。
アフタヌーン・ティールームの頭文字を見ていると、 コンピュータに関係しているようだ。 そんなことを考えながら、今日もまたパスタランチを食べていた。
あの女の子からもらった 既約分数の問題を日記に書いたところ、 いろんな人から解答をもらって、とても楽しかった。 さまざまなプログラミング言語で、同じ問題を解くのは楽しい。
パスタを食べながら、 プログラミング言語について考えるというのはちょっと変な気分だ。 制御が入り組んでいるプログラムのことを「スパゲティ・プログラム」と俗に呼ぶからだが、 gotoがないJavaのようなプログラミング言語でも「スパゲティ・プログラム」は作れるだろうか。 などとつまらないことを考えて一人でくすくす笑っていたので、 誰かが後ろから肩をぽんと叩いたときには心底驚いてしまった。
手にフォークを持ったまま振り向くと、 そこにはあの「既約分数」の問題を出した女の子が立っていた。
「こんにちは」と女の子は明るい声で言い、にこっと笑った。 「日記、読みましたよ。ShiroさんがFarey数列の解答を作ってらっしゃいましたね」 彼女はそう言うと、ぐるっとテーブルを回って私の向かいの席に座った。 先日はピンクのセーターだったが、今日はセーラー服を着ている。
「そうですね。他にもいろんな解答が寄せられて楽しかったですよ。 面白い問題をありがとうございます」 私は彼女にお礼をいった。うん、楽しかった。
「フォーク」と彼女が言った。
「え？ あ、失礼」 私はフォークを振り上げたまま話をしていたのだった。 ちょっときまりの悪い思いをしながら、私はフォークを皿に戻した。
「ああいう問題、お好きですか。 よく日記にもお子さんとの対話が出てきますよね。数学対話」
「そうですね。私は数学っぽい話は好きですし、 ゲームやパズルも小さいころから好きですね。 うちの長男も、私が問題を出すと、よろこんで考えるみたいです」
彼女は、言葉を選びながらゆっくりと話す。 「日記を読んでいて、 単に問題を出して子供さんに答えさせているのではないように見えます。 適切な手がかりを適切な順序で提示して、自然と何かを学んでいくような「流れ」を感じます。 宝物が隠されている美しい島がある。 島を歩きながら、隠し場所が書かれている地図の切れ端を少しずつ見つけていくような…」
「そんな大げさなものではありません。 ただ、自分が思いついた「面白そうなこと」を子供と一緒に考えているだけだと思いますよ」 私はそう答えながらも、ちょっとうれしくなった。
ふと、私は思い出した。 「そういえば、先日、あの既約分数の問題のとき、 帰り際に『時計を作る方に尋ねるとよいですよ』っておっしゃいましたよね。 あれはどういう意味ですか。日記の読者さんからも問い合わせが来ているのですが」
「あらら？ だって、Stern-Brocot Treeを使ってらっしゃったじゃないですか」
「え？ それが時計と何か関係があるんですか」
「ええ、Brocotさんは時計工なんです」 彼女はそう言って、人差し指を立ててにっこりした。
Where is the truth?
Dan Kogaiさんの解答です。 Hashを使ったPerlishな解答！