ビジュアルプログラミング(24)

たらい回し関数(1)

「たらい回し関数(1) - エレファント・コンピューティング調査報告」で取り扱った「たらい回し関数」も普通にプログラムを書くことができるので、これについても考えてみます。

「たらい回し関数」(TyprScript)は以下のようになります。

var count1: number = 0;
function tarai1(x: number, y: number, z: number): number {
    count1++;
    if (x <= y) {
        return y;
    }
    else {
        var a: number = tarai1(x - 1, y, z);
        var b: number = tarai1(y - 1, z, x);
        var c: number = tarai1(z - 1, x, y);
        return tarai1(a, b, c);
    }
}

これは以下のように書き換えることができます。

var count2: number = 0;
function tarai2(x: number, y: number, z: number): number {
    count2++;
    for (; ;) {
        if (x <= y) {
            return y;
        }
        var a: number = tarai2(x - 1, y, z);
        var b: number = tarai2(y - 1, z, x);
        var c: number = tarai2(z - 1, x, y);
        [x, y, z] = [a, b, c];
    }
}

これは以下のように書き換えることができます。

var count3: number = 0;
function tarai3(x: number, y: number, z: number): number {
    count3++;
    for (var i = 0; i < 2; i++) {
        if (x <= y) {
            return y;
        }
        var a: number = tarai3(x - 1, y, z);
        var b: number = tarai3(y - 1, z, x);
        var c: number = tarai3(z - 1, x, y);
        [x, y, z] = [a, b, c];
    }
    return y; // ここには来ない
}

これは以下のように書き換えることができます。

var count4: number = 0;
function tarai4(x: number, y: number, z: number): number {
    count4++;
    if (x <= y) {
        return y;
    } else if (y <= z) {
        return z;
    } else {
        return x;
    }
}

count1、count2、count3、count4 が有限で、tarai1、tarai2、tarai3、tarai4 の結果が同じになることを示すことができます。

代数系入門 (松坂和夫　数学入門シリーズ)

代数学入門---先につながる群，環，体の理論NBS 日評ベーシック・シリーズ

初等整数論入門 Math＆Science (ちくま学芸文庫)

可換環論の勘どころ (数学のかんどころ)