问题描述 如果一个序列满足下面的性质，我们就将它称为摆动序列：
1. 序列中的所有数都是不大于
k的正整数；
2. 序列中至少有两个数。
3. 序列中的数两两不相等；
4. 如果第
i – 1个数比第
i – 2个数大，则第
i个数比第
i – 2个数小；如果第
i – 1个数比第
i – 2个数小，则第
i个数比第
i – 2个数大。
比如，当
k = 3时，有下面几个这样的序列：
1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2
一共有8种，给定
k，请求出满足上面要求的序列的个数。 输入格式 输入包含了一个整数
k。(
k<=20) 输出格式 输出一个整数，表示满足要求的序列个数。 样例输入 3 样例输出
8
package com.xjj.lanqiao;
import java.util.Scanner;
public class Lq3_9 {
public static int k;
public static int sum = 0;
public int[] a = new int[k];//保存类全排列数
public int[] book = new int[k+1];//标记数组
//深度优先搜索
public void dfs(int start, int end){
//当序列差为3
if (end - start == 3) {
//如果满足条件，数目加1，且开头跳到下一位，继续3排列
if ((a[start] < a[start+1] && a[start] > a[end-1]) ||
(a[start] > a[start+1] && a[start] < a[end-1])) {
sum++;
start++;
}
else return;
}
//枚举法，遍历每一位
for(int i = 1; i <= k; i++){
//如果纸牌还在手中
if (book[i] == 0) {
a[end] = i; //入盒子
if (a[start] == 1 || a[start] == k) //如果以 1 或 k 开头则退出
continue;
book[i] = 1; //标记纸牌入盒子
dfs(start, end + 1);
book[i] = 0; //拿出纸牌
}
}
}
public static void main(String[] args) {
System.out.println();
Scanner scanner = new Scanner(System.in);
k = scanner.nextInt();
//排两位的单独考虑，个数:
int n = (k-1) * k;
Lq3_9 lq = new Lq3_9();
lq.dfs(0, 0);
System.out.println(n + sum);
}
}