問題描述 如果一個序列滿足下面的性質，我們就将它稱為擺動序列：
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);
}
}