对于一个栈,给出输入项A,B,C,D,如果输入项序列为A,B,C,D,试给出全部可能的输出序列。
ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA CBDA CBAD CDBA DCBA
A,B,C,D A,C,D,B A,C,B,D B,A,D,C B,A,C,D B,C,A,D B,D,C,A B,C,D,A C,B,A,D D,C,B,A C,D,B,A
1/5 * C8,4 = 14
14
ABCD ABDC ACBD ACDB ADBC
BACD BADC BCAD BCDA BDCA
CBAD CBDA CDBA
DCBA
卡特兰数
14种 ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CDBA CBDA DCBA
ABCD
BDCA
CDBA
BADC
BACD
CBAD
CBDA
ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA
CBDA CBAD CDBA DCBA
abcd
bacd
cbad
dcba
答案漏了一个BDCA
1
ABCD;ABDC;ACDB;ACBD;ADCB;BACD;BCDA;BDCA;BCAD;CBAD;CDBA;CBDA;DCBA;
hh
ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CDBA,CBDA,DCBA,
abcd,abdc,acbd,acdb,adcb,bacd,badc,bcad,bcda,bdca,cbad,cbda,cdba,dcba (14)
数列数量 用卡特兰数计算 是 14 种
abcd,acbd,abdc,acdb,adcb,badc,bacd,bcad,bcda,bdca,cdba,cbad,cbda,dcba
ABCD,ABDC,ACDB,ACBD,,ADCB,BACD,BADC,BCDA,BCAD,CBDA,CBAD,,\CDBA,DCBA,
abcd,acbd,abdc,acdb,adcb,badc,bacd,bcad,bcda,bdca,cdba,cbad,cbda,dcba14种(答案少一种)
ABCD ABDC ACBD ACDB ADCB
CBAD CDBA CBDA
BDCA可以把应该 AB进 B出 CD进 D出 C出 A出
不应该是15种吗?
看到好多人都是写的都是14种,有的要么没有BDCA,有的要么没有BCDA,答案里面是这两种都没有,但是这两种都可以呀。
BDCA:进栈AB->出栈B->进栈CD(此时栈内是ACD)->剩余的出栈得到序列BDCA
BCDA :进栈AB->出栈B->进栈C->出栈C->进栈D(此时栈内是AD)->剩余的出栈得到序列BCDA
全部可能的输出序列如下:
BACD BADC BCDA BDCA BCAD BCDA
CDBA CBAD CBDA
Djiangxu 回复 Djiangxu: 哦哦是14种,没注意有一个重复了BCDA。
n个不同元素进栈,出栈元素不同排序的个数为C(2n,n) / (n+1)种。
ABCD ABDC ACBD ACDB ADCB BACD BADC BCDA BCAD BDCA CBDA CBAD CDBA DCBA
14种
abcd,abdc,acbd,adcb,acdb bacd,badc,bcad,bdca,bcda cbad,cbda,cdba dcba,
CDBA CBDA CBAD
BDCA BCDA BCAD BADC BACD
ADCB ACDB ACBD ABDC ABCD
A B C D
A B D C
A C B D
A D C B
B A C D
B A D C
B C A D
B C D A
C B A D
C B D A
C D B A
D C B A
BCDA BCAD BADC BACD
一共14种情况:
ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA BDCA CBDA CBAD CDBA DCBA
abcd acbd adcb bacd bcad bdca cbad cdba dcba
c(2n,n)/n+1
ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD
BCDA CBDA CBAD CDBA DCBA
BACD BADC BCDA BCAD BDCA
abdc
acbd
acdb
adcb
badc
bcda
bcad
bdca
cbda
cdba
答案少了个BDCA?
BCAD BCDA BDCA BADC BACD
abcd//abdc//acbd//acdb//adcb bacd//badc//bcad//bcda//bdca cbad//cdba dcba
(1/5)*(10*9*8*7*6)/(5*4*3*2)种
ABDC
ACBD
ACDB
ADCB
BCAD
BCDA
有什么规律吗,折磨
A,B,C,D A,B,D,C A,C,B,D A,C,D,B A,D,C,B
B,A,C,D B,A,D,C B,C,A,D B,C,D,A B,D,C,A
C,B,A,D C,B,D,A C,D,B,A
D,C,B,A
CBDA CBAD CDBA
ABCD,ADCB,ACBD,ACDB,ABDC
BACD,BCAD,BDCA,BADC,BCDA
CBAD,CDBA,CBDA
(1/5)*(8*7*6*5/4*3*2*1)=14
ABCD ABDC ADCB ACBD ACDB BCDA BDCA
BACD BADC BCAD CBAD CDBA CBDA DCBA
abcd acbd adcb acdb abdc
bacd badc bcad bcda bdca
cbad cbda cdba
asdfg 回复 asdfg: 答案少了一个bdca??
BACD BADC BCAD BCDA BDAC
CBAD CDBA CBAD CBDA DCBA
答案:出栈的可能序列:
&n...
用户登录可进行刷题及查看答案
登录后提交答案