開発環境
- macOS Sierra - Apple (OS)
- Emacs (Text Editor)
- JavaScript (プログラミング言語)
- Safari(Web browser)
- 参考書籍
- JavaScript 第6版 (David Flanagan(著)、村上 列(翻訳)、オライリージャパン)
- JavaScriptリファレンス 第6版(David Flanagan(著)、木下 哲也(翻訳)、オライリージャパン)
アルゴリズムパズル(Anany Levitin (著)、Maria Levitin (著)、黒川 洋 (翻訳)、松崎 公紀 (翻訳)、オライリージャパン)の中級パズル、99.(ソートされた列の反転 (Reversal of Sort))をJavaScriptで。
99.(上部交換ゲーム (The Game of Topswops))
n個の異なる数を1からnと考えても一般性は失われない。
nが奇数の時に可能。最小の交換回数は、奇数と偶数に分けて考えて合計。
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 コメント:
コメントを投稿