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

たらい回し関数(2)

前回の「たらい回し関数」で「ここには来ない」と書いたところは間違っていて、実際にはもう1回は来るので書き直します。

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

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

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

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

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

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

変数名を書き換えると以下のようになります。

var count4: number = 0;
var depth4: number = 0;
function tarai4(x: number, y: number, z: number, d: number): number {
    count4++;
    depth4 = Math.max(depth4, d);
    for (; ;) {
        if (x <= y) {
            return y;
        }
        var a: number = tarai4(x - 1, y, z, d + 1);
        var b: number = tarai4(y - 1, z, x, d + 1);
        var c: number = tarai4(z - 1, x, y, d + 1);
        if (a <= b) {
            return b;
        }
        var a2: number = tarai4(a - 1, b, c, d + 1);
        var b2: number = tarai4(b - 1, c, a, d + 1);
        var c2: number = tarai4(c - 1, a, b, d + 1);
        if (a2 <= b2) {
            return b2;
        }
        // ここには来ない
        var a3: number = tarai4(a2 - 1, b2, c2, d + 1);
        var b3: number = tarai4(b2 - 1, c2, a2, d + 1);
        var c3: number = tarai4(c2 - 1, a2, b2, d + 1);
        [x, y, z] = [a3, b3, c3];
    }
}

「ここには来ない」と書いたところには来ないことを証明することができます。よってこれは以下のように書き換えることができます。

var count5: number = 0;
var depth5: number = 0;
function tarai5(x: number, y: number, z: number, d: number): number {
    count5++;
    depth5 = Math.max(depth5, d);
    if (x <= y) {
        return y;
    }
    var a: number = tarai5(x - 1, y, z, d + 1);
    var b: number = tarai5(y - 1, z, x, d + 1);
    var c: number = tarai5(z - 1, x, y, d + 1);
    if (a <= b) {
        return b;
    }
    return tarai5(b - 1, c, a, d + 1);
}

これと以下の関数が同じ関数になることを証明できれば、たらい回し関数は以下の関数と同じ関数となります。

var count6: number = 0;
var depth6: number = 0;
function tarai6(x: number, y: number, z: number, d: number): number {
    count6++;
    depth6 = Math.max(depth6, d);
    if (x <= y) {
        return y;
    } else if (y <= z) {
        return z;
    } else {
        return x;
    }
}

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

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

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

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