2016年11月13日日曜日

開発環境

アルゴリズムパズル(Anany Levitin (著)、Maria Levitin (著)、黒川 洋 (翻訳)、松崎 公紀 (翻訳)、オライリージャパン)の中級パズル、99.(ソートされた列の反転 (Reversal of Sort))をJavaScriptで。

99.(上部交換ゲーム (The Game of Topswops))

n個の異なる数を1からnと考えても一般性は失われない。

nが奇数の時に可能。最小の交換回数は、奇数と偶数に分けて考えて合計。

n1( mod2 ) 1+2+···+( n+1 2 1 )= 1 2 · n1 2 · n+1 2 1+2+···+( n1 2 1 )= 1 2 · n3 2 · n1 2 1 2 · n1 2 · n+1 2 + 1 2 · n3 2 · n1 2 = ( n1 )( 2n2 ) 2 3 = ( n1 ) 2 4

JavaScriptで確認。

コード(Emacs)

HTML5

<div id="output0"></div>
<label for="n0">n = </label>
<input id="n0" type="number" min="1" step="2" value="5">

<script src="sample99.js"></script>

JavaScript

{
    'use strict';
    let range = (start=0, end=0, step=1) => {
        let result = [];
        for (let i = start; i < end; i += step) {
            result.push(i);
        }
        return result;
    }

    let div_output = document.querySelector('#output0'),
        input_n = document.querySelector('#n0');

    let f = (n) => {
        return Math.pow(n - 1, 2) / 4;
    };
    let output = () => {
        let n = parseInt(input_n.value, 10),
            nums = range(1, n + 1),
            count = 0;

        nums.sort((x, y) => y - x);

        div_output.innerHTML = `${count}: ${nums.join(' ')}<br>`;

        
        for (let len = nums.length; len > 0 ; len -= 2) {
            for (let i = 0; i < len - 2; i += 2) {
                let t = nums[i];
                nums[i] = nums[i + 2];
                nums[i + 2] = t;
                count += 1;
                div_output.innerHTML += `${count}: ${nums.join(' ')}<br>`;
            }
        }
        for (let len = nums.length - 1; len > 0 ; len -= 2) {
            for (let i = 1; i < len - 2; i += 2) {
                let t = nums[i];
                nums[i] = nums[i + 2];
                nums[i + 2] = t;
                count += 1;
                div_output.innerHTML += `${count}: ${nums.join(' ')}<br>`;
            }
        }
        div_output.innerHTML += `(${n} - 1)^2 / 4 = ${f(n)}`;
    }

    input_n.onchange = output;

    output();
}

0 コメント:

コメントを投稿