推 mvpnashmvp :這想法好棒 感謝!!! 03/16 00:41
推 shenasu := =把她想成 n人排一列 兩高中間不得排矮 即可 03/16 00:49
→ shenasu :最高的先排1 下一個選左右 即1*2*2*2...=2^n-1 03/16 00:50
→ doa2 :樓上確定可以這樣轉換? 4旁邊沒有非得排3 03/16 01:01
※ 引述《yclinpa (薇楷的爹)》之銘言：
: ※ 引述《mixxim (米克斯)》之銘言：
: : n=1: 1
: : n=2: 12 21
: : n=3: 123 213 231 321
: : n=4: 1234 2134 2314 2341 3214 3241 3421 4321
: : n=5: 12345 ... 等16個
: : 經過觀察看起來真的是 2^(n-1)，試著歸納看看
: 可以直接證。以下以 n=9 為例，作為一般性證明的提示：
: 考慮字串「大小小大大大小大」，此字串對應到 4-53267819.
: 觀察重點：(a) 第一位數字如何決定？
: (b) 「小」數排列的規則為何？「大」數排列的規則為何？
: 這些提示應該就夠了。
提供一個想法
每一位數字都 大於他左邊的每一個數字 或 小於他左邊的每一個數字
這樣保證左邊會有跟他差1的數字
因此最右邊是1或n，接著每位數字均可選"剩下的數中，最大的或最小的數字"
得2*2*2*....2*1=2^(n-1)種
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.33.49.226