ALGO-9 擺動序列 (藍橋杯算法基礎訓練)

試題 算法訓練 擺動序列

資源限制

​ 時間限制：1.0s 記憶體限制：512.0MB

問題描述

如果一個序列滿足下面的性質，我們就将它稱為擺動序列：

　　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

方法一 ( 數學方法 )

基本思路::

​ 根據條件 我們能得到一些資訊(需要思考一下)

1. 隻要給出一個大于等于2的數組,都能形成擺動序列
2. 能夠形成的擺動序列中,又根據先增或先減分出2種情況(一種逐漸發散    一種逐漸收斂)
3. 長度為n的數組 能形成(無序)  C(n,1) 個長度為1子數組 形成 C(n,2) 個長度為 2的子數組......形成長度為 C(n,n)長度為n的數組 
4. 又因為長度為1的不算是擺動序列 是以無序的情況下 能排列出來的數組個數是 C(n,0) + C(n,1) + C(n,2) + C(n,3) + C(n,4) +C(n,5) + C(n,6) +C(n,7) + C(n,8) + ...... +C(n,n) - C(n,1) - C(n,0) = 2^n - n - 1
5. 由于擁有2中情況 那麼 最後 答案 就是 (2^n - n - 1) * 2
           

代碼實作::

import java.io.*;
import java.util.StringTokenizer;

class Main {
    ReadIn readIn = new ReadIn(System.in);
    PrintWriter printWriter = new PrintWriter(System.out,true);

    public void run() throws IOException {
        int n = readIn.nextInt();
        printWriter.println(((int)Math.pow(2,n) - n - 1) << 1);
    }


    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static class ReadIn {
        private StringTokenizer stringTokenizer;
        private BufferedReader bufferedReader;

        public ReadIn(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            stringTokenizer = new StringTokenizer("");
        }

        public String next() throws IOException {
            if (!stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            }
            return stringTokenizer.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

}
           

測試結果::

方法二 ( 動态規劃 )

基本思路::

1. 首先建立一個表 dp[i][j] = k 代表的意義 是 長度為 i的序列中 能形成長度 為j的 擺動序列個數 是 k
2. 進行推導 dp[i][j] 的資料 一部分來自 dp[i-1][j] 的繼承…原來就能長度為j的擺動序列 現在 也能組成(不含有j的序列)
3. dp[i][j] 還有一部分資料 來自 dp[i-1][j-1] 的序列 再 + 新的數字 i 組成的 長度為 j 的序列( 新的序列都是 含有 i的序列)
4. 是以dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
5. 序列總數是 dp[n][2] +…+dp[n][n] 但是有2種順序情況, 是以 最後 還要 * 2

代碼實作::

import java.io.*;
import java.util.StringTokenizer;

class Main {
    ReadIn readIn = new ReadIn(System.in);
    PrintWriter printWriter = new PrintWriter(System.out, true);

    public void run() throws IOException {
        int n = readIn.nextInt();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i < n + 1; i++) {     //初始化 dp[n][1] = n
            dp[i][1] = i;
        }
        for (int i = 2; i < n + 1; i++) {
            for (int j = 2; j <= i; j++) {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
        }
        int result = 0;
        for(int i=2;i<n+1;i++){
            result += dp[n][i];
        }
        printWriter.println(result * 2);
    }


    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static class ReadIn {
        private StringTokenizer stringTokenizer;
        private BufferedReader bufferedReader;

        public ReadIn(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            stringTokenizer = new StringTokenizer("");
        }

        public String next() throws IOException {
            if (!stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            }
            return stringTokenizer.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

}
           

測試結果::