Algorithm - JavaScript - 残る数字 (Remaining Number)

アルゴリズムパズル
原著

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• JavaScript Library
  • kjs-array
• Safari(Web browser)
• 参考書籍
  • JavaScript 第6版 (David Flanagan(著)、村上 列(翻訳)、オライリージャパン)
  • JavaScriptリファレンス 第6版(David Flanagan(著)、木下 哲也(翻訳)、オライリージャパン)

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

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

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

総和、部分和を考える。

$\begin{array}{l}S={\displaystyle \sum _{n=1}^{50}n=\frac{50\left(50+1\right)}{2}}=1275\\ S_{n-1}=S_n-a-b+\left|a-b\right|\\ =S_n-a-b+a-b\\ =S_n-2b\\ \left(a\ge b,n=2,3,···,50\right)\end{array}$

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

$\begin{array}{l}m=1,3,···,49\\ a=m+1,b=1,\left|a-b\right|=m\\ a=50,b=49,\left|a-b\right|=1\\ a=48,b=47,\left|a-b\right|=1\\ ···\\ a=m+3,b=m+2,\left|a-b\right|=1\\ a=m,b=m-1,\left|a-b\right|=1\\ a=m-2,b=m-3,\left|a-b\right|=1\\ ···\\ a=3,b=2,\left|a-b\right|=1\\ \\ 1+24=25回操作\\ 残り\text{24}個の\text{1}と、\text{1}個のm。\\ 1-1=0\\ ···\\ 1-1=0\\ 25+12=37回操作\\ 残り\text{12}個の\text{0}と、\text{1`}個のm。\\ m-0=m\\ ···\\ m-0=m\\ 37+12=49回の操作\\ 残りm。\end{array}$

よって、黒板上に残り得る数字は、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;
}