题目描述javascript
魔法世界的历史上曾经出现过一位赫赫有名的不败战神陈庆之,陈庆之以棋道悟兵法,一辈子身经数百战,没有一场败绩,并且没有一场不是在绝对的劣势中大胜敌军。java
受此影响,魔法世界开始流行一种叫棋子移动的游戏,即有2N个棋子(N≥4)排成一行,开始位置为白子所有在左边,黑子所有在右边,例如当N=4时,棋子排列状况为:web
〇〇〇〇●●●●svg
移动棋子的规则是:每次必须同时移动相邻两个棋子,颜色不限,能够左移也能够右移到空位上去,但不能调换两个棋子的左右位置.每次移动必须跳过若干个棋子(不能平移),要求最后能移成黑白相间的一行棋子。例如当N=4时,最终排列状况为:spa
〇●〇●〇●〇●code
试求出移动步骤。
输入
一个整数,即N。
输出
输出移动步骤,每一步操做占一行。
样例输入 Copy
4
样例输出 Copy
4,5–>9,10
8,9–>4,5
2,3–>8,9
7,8–>2,3
1,2–>7,8xml
解析:
找规律题
根据样例能够发现4,5(n,n+1).9,10(2n+1,2n+2); 第二行的右边第一行的左边。第二 行的 左边第一行右边都-1.递归
当n>4时咱们尽可能让n递归到4。token
每当n>4的时候就会多出来两行。游戏
n==5的状况 5 5,6-->11,12 9,10-->5,6 4,5-->9,10 8,9-->4,5 2,3-->8,9 7,8-->2,3 1,2-->7,8
#include<bits/stdc++.h> using namespace std; int n; int k; void mv(int j) { printf("%d,%d-->%d,%d\n",j,j+1,k,k+1); k=j; } void dfs(int n) { if(n==4) { mv(4);mv(8);mv(2);mv(7);mv(1); } else { mv(n);mv(2*n-1);dfs(n-1); } } int main() { cin>> n; k=2*n+1; dfs(n); }