2016年10月7日金曜日

開発環境

アルゴリズムパズル(Anany Levitin (著)、Maria Levitin (著)、黒川 洋 (翻訳)、松崎 公紀 (翻訳)、オライリージャパン)の中級パズル、66.(残る数字 (Remaining Number))をJavaScriptで。

66.(残る数字 (Remaining Number))

一回の操作で1つの数字が消えるから、49回の操作後に残る数字は1つ。

総和、部分和を考える。

S= n=1 50 n= 50( 50+1 ) 2 =1275 S n1 = S n ab+| ab | = S n ab+ab = S n 2b ( ab,n=2,3,···,50 )

偶奇性(パリティ)は一定で、Sは奇数なことから、最後に残り得る数字は奇数

m=1,3,···,49 a=m+1,b=1,| ab |=m a=50,b=49,| ab |=1 a=48,b=47,| ab |=1 ··· a=m+3,b=m+2,| ab |=1 a=m,b=m1,| ab |=1 a=m2,b=m3,| ab |=1 ··· a=3,b=2,| ab |=1 1+24=25 2411m 11=0 ··· 11=0 25+12=37 1201`m m0=m ··· m0=m 37+12=49 m

よって、黒板上に残り得る数字は、1以上49以下の奇数。

コード(Emacs)

HTML5

<div id="output0"></div>
<button id="display0">開始</button>

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

JavaScript

{
    'use strict';
    Array.range = function (start, end, step) {
        var nums = [],
            i;

        if (step === 0) {
            throw {
                name: 'ValueError',
                message: 'range() arg 3 must not be zero',
            };
        }
        if (step === undefined) {
            step = 1;
        }
        if (end === undefined) {
            end = start;
            start = 0;
        }
        if (step > 0) {
            for (i = start; i < end; i += step) {
                nums.push(i);
            }
        } else {
            for (i = start; i > end; i += step) {
                nums.push(i);
            }
        }
        return nums;
    };
    let div_output = document.querySelector('#output0'),
        button_display = document.querySelector('#display0');

    let getIndexes = (n) => {
        let i = Math.floor(Math.random() * n),
            j = Math.floor(Math.random() * n);

        for (; i === j; ) {
            j = Math.floor(Math.random() * n);
        }
        return [i, j];
    };
    let display = () => {
        let nums = Array.range(1, 51),
            output = '';

        output += `黒板: ${nums.join(' ')}<br>`;
        for (let i = 50; i >= 2; i -= 1) {        
            let [ai, bi] = getIndexes(i);
            let a = nums[ai];
            let b = nums[bi];
            nums.push(Math.abs(a - b));
            output += `記入: ${nums.join(' ')}<br>`;
            if (ai > bi) {
                nums.splice(ai, 1);
                nums.splice(bi, 1);        
            } else {
                nums.splice(bi, 1);
                nums.splice(ai, 1);
            }
            output += `削除: ${nums.join(' ')}<br>`;
        }
        div_output.innerHTML = output;
    };
    display();

    button_display.onclick = display;
}

0 コメント:

コメントを投稿