与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - JavaScript
匿名
#4974()
[
JavaScript
]
ブラウザで起動できるように書いてあります。 amida関数自体はブラウザ非依存です。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | window.onload = function()
{
var a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var b = [3, 9, 4, 1, 5, 0, 2, 6, 8, 7];
var pre = document.createElement("pre");
var text = document.createTextNode(a.join(" ") + "\r" + amida(a, b) + b.join(" "));
pre.appendChild(text);
document.body.appendChild(pre);
}
function amida(startArray, endArray) {
//配列のコピー
var copyArray = startArray.concat();
var ixStart = 0;
var ixEnd = copyArray.length - 1;
var amidaText = "";
var amidas = [];
for(var ix = 0; ix < ixEnd; ix++)
amidas[ix] = " ";
//交換開始
while(ixStart < ixEnd) {
var head = endArray[ixStart];
var tail = endArray[ixEnd];
for(var ix = ixStart; ix <= ixEnd; ix++) {
if(head == copyArray[ix]) {
if(ix == ixStart)
ixStart++;
else
changeArray(ix - 1, ix);
}
if(tail == copyArray[ix]) {
if(ix == ixEnd)
ixEnd--;
else
changeArray(ix, ix + 1);
}
}
}
return amidaText;
//要素交換関数
function changeArray(x, y) {
var refuge = copyArray[x];
copyArray[x] = copyArray[y];
copyArray[y] = refuge;
amidas[x] = "-";
amidaText += "|" + amidas.join("|") + "|\r";
amidas[x] = " ";
}
}
|
shiro
#4704()
Rating15/15=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]