交换数

Question

这是一个常见的难题，你们中的许多人已经手工解决了。现在是时候写一个算法来解决同样的问题了。

有等号的火柴条排列在两个不同的侧面，面对对方的方向。它们之间只有一个空空间。如下图所示(如果火柴棒总数为4)。

每根棍子可以向前滑动一步(如果前方空间是自由的)，或者可以跳过前面的一根棍子，然后降落到自由空间(如果空间是自由的)。向相反方向移动是不可能的(即使空间是自由的)。也不允许反向跳转。一步只允许一次移动。

现在，您需要编写一个算法来找到所需的最小步骤，其中所有左手边的火柴杆都会落在右手边，所有的右手边的火柴棒都会落在左手边。

对于示例:如果总共有2根火柴棒(两边各1根)，则步骤如下：

注意:在上面的图中，左边的棍子是先移动的。另一个解决方案是，当右边的棍子先移动时存在。但是对于这个问题，你只能给出一个解决方案，那就是假设左边的棍子先移动。

下图描述了4根火柴棒(两边各2根)的移动：

注意:在上面的图中，左边的棍子是先移动的。另一个解决方案是，当右边的棍子先移动时存在。但是对于这个问题，你只能给出一个解决方案，那就是假设左边的棍子先移动。

假设:输入可以是02到14之间的任意偶数(即每侧1到7根火柴棒)。对于超出此范围的输入，您不需要进行任何验证，也不需要提供任何错误消息。注意:在输出中，每一步都由一个管道字符分隔。COBOL程序员应该始终假设PIC 9(2)作为输入大小&也可以假定输出为固定的最大长度450个字符，并在右边填充空格.

样本输入：

02  

样本输出：

01To02|03To01|02To03|

样本输入：

04  

样本输出：

02To03|04To02|05To04|03To05|01To03|02To01|04To02|03To04|

样本输入：

06  

样本输出：

03To04|05To03|06To05|04To06|02To04|01To02|03To01|05To03|07To05|06To07|04To06|02To04|03To02|05To03|04To05|

Answer 1

APL 129

下面的代码以指定的格式接收屏幕输入并输出到屏幕：

n←n,n++\1↓z←(⌽z),((¯1*~2|n)×n⍴2),z←⌽∊(¯1*2|⍳n)ר1,((⍳(n←.5×⍎⍞)-1)⍴¨2),¨1⋄(∊(((¯2↑¨'0',¨⍕¨n),¨⊂'To'),¨(¯2↑¨'0',¨⍕¨n-z)),¨⊂'|')~' '

很好的三分之一的代码用于格式化输出。逻辑是通过代码中⋄符号的出现来完成的。

下面是作为检查输入08的结果：

04To05|06To04|07To06|05To07|03To05|02To03|04To02|06To04|08To06|09To08|07To09|05To07|03To05|01To03|02To01|04To02|06To04|08To06|07To08|05To07|03To05|04To03|06To04|05To06|

Answer 2

Mathematica

此方法构建移动大小和方向的Nested序列，格式为{fromPosition,toPosition}，从位置n开始，n引用匹配对的数量。然后，它把Folds的序列变成一个函数，从{n, n+1}移动开始。

z@n_:=(p=1;h@t_:=Append[{Table[2 (-1)^t,{t}]},{(-1)^(t+1)}];
k=Join[Reverse@Drop[#,n],#]&[Flatten@Nest[Prepend[#,h[p++]]&,{},n]];
Fold[Append[#,{#[[-1,1]]-#2,#[[-1,1]]}]&,{{n,n+k[[1]]}},Rest@k])

z[1]

{1，2}，{3，1}，{2，3}

z[4]

{4，5}，{6，4}，{7，6}，{5，7}，{3，5}，{2，3}，{4，2}，{4，2}，{6，4}，{8，6}，{9，8}，{7，9}，{5，7}，{3，5}，{1，3}，{2，1}，{4，2}，{6，4}，{8，6}，{7，8}，{5，7}，{3，5}，{4，3}，{6，4}，{5，6}}

z[7]

{7，8}，{9，7}，{10，9}，{8，10}，{6，8}，{5，6}，{7，5}，{9，7}，{11，9}，{12，11}，{10,12}，{8，10}，{6，8}，{4，6}，{3，4}，{5，3}，{7，5}，{9，7}，{11，9}{13，11}，{14，13}，{12，14}，{10，12}，{8，10}，{6，8}，{4，6}，{2，4}，{1，2}，{3，1}，{5，3}，{7，5}，{9，7}，{11，9}，{13，11}，{15，13}，{14，15}，{12，14}，{10，12}、{8、10}、{6、8}、{4、6}、{2、4}、{3、2}、{5、3}、{7、5}、{9、7}、{11、9}、{13、11}、{12、13}、{10、12}、{8、10}、{6、8}、{4、6}、{5、4}、{ 7 }、{9、7}、{11，9}，{10，11}，{8，10}，{6，8}，{7，6}，{9，7}，{8，9}}

可视化交换

r、b和o分别是图像或红色匹配、蓝色匹配和不匹配。

下面格式化来自z的输出，以显示匹配的交换。

swaps[n_]:=FoldList[Grid[{Permute[#[[1,1]],Cycles[{#2}]],Range[2n+1]}]&,
Grid[{Join[Table[r,{n}],{o},Table[b,{n}]],Range[2n+1]}],z[n]]

swapMatches[n_]:=Grid[Partition[swaps[n],2,2,1,""],Dividers->All]

swaps通过使用有序的z对作为命令来生成状态列表，以更改初始列表和后续列表。

swaps[1]

swapMatches在网格中显示状态。

swapMatches[2]

swapMatches[3]

Answer 3

Javascript 191

function f(N) {
    n=N>>=i=c=a='1';n++
    s=z='0'
    for(k=b='34';i<N;k=i%2?a+=z+z:b+='44',i++)c=k+c
    t=''
    i=N*(N+1)/2
    l=2*i+N
    for(;l;n+=(i>=1?r=c[i-1]:i<=-N?c[-i-N]:k[1])-2,t+=(s=n>9?'':z)+n+a+'|',--l,--i)a='To'+s+n
    return t
}

使用grep =|tr -d \ |wc -c计数字符