http://img1.picsplace.to/img1/5/1432/p39.jpg 連結中的問題不會解 一個STACK的STATUS可以用CATALAN NUMBER算 但兩個的不會解 我的想法是因為所有情況都可以經過兩個堆疊的相互調整出來 所以我覺得所有的STATUS應該都可以ㄝ 不知道對不對....可是這樣考就沒意義啦....orz 請各位高人指點迷津

charse你好： 如果你知道Finite State Machine，就可以用State graph解n=3的問題。之後再歸納求一般解。

對不起~ 小弟不知道對於不同的INPUT要怎麼用Finite State Machine解...orz.. 可是如果針對N=3時 我可以推出全部的STATUS的 因為題目僅限制不能在BC相互PUSH POP 但是事實上BC可藉由A來達成BC間的PUSH POP 所以我覺得很奇怪 不知道是不是我誤解題意了呢?

#Status = Sigma(P(n, k)), k from 0 to n, where P(n, k) = n!/(n-k)!.    1. n = 1 #status = P(1, 0) + P(1, 1) = 2 Stack A: (Empty), (1)    2. n = 2 #status = P(2, 0) + P(2, 1) + P(2, 2) = 1 + 2 + 2 = 5  Stack A: (Empty), (1), (2), (1, 2), (2, 1)    3. n = 3 #status = P(3, 0) + ... + P(3, 3) = 1 + 3 + 6 + 6 = 14

Stack A: 
  (Empty), 
  (1), (2), (3), 
  (1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (3, 2)
  (1, 2, 3), (1, 3, 2), ...

4. 从1到n中随意挑选i个数字得到一个排列: K1, K2, ..., Ki, 通过下面的算法可以让这个排列出现在 Stack A中(Bottom(K1) -> Top(Ki)).

   For p = i downto 1 do
   begin
     a. 将在Kp之上的数字从A->B.
     b. 将Kp从A->C.
     c. 将B中的数字全部推回A, B->A.
   end;
   至此, 排列Ki, ..., K2, k1出现在C中.
   将A中剩余的数字, 如果有的话, 全部推入B中.
   将C中的数字全部推回A中, 得到排列 K1, K2, ..., Kn.

上面的算法可以使由1到n数字组成的任意排列出现在Stack A中, 所有排列的总数, 即Stack A所有可能的status数是

 i     #排列(即, #Status)
 0     P(n, 0) = 1 (ie. empty)
 1     P(n, 1) = n
 2     P(n, 2) = n!/(n-2)!
 ...
 n     P(n, n) = n!/(n-n)! = n!    加起来总和是 .... (见上).

. _________________________ Programming is a passion 發表人 - yyu10 於 2005/04/01 10:01:12