2005各校歷屆試題(頁 1) - 高中的數學

bugmens 發表於 2008-12-20 21:18

2005各校歷屆試題

h ttp://forum.nta.org.tw/oldphpbb2/viewtopic.php?t=28829　連結已失效
四個美國人,四個日本人,四個德國人排成一列,只看國籍,求同國籍不相鄰之排法共幾種？
h ttp://forum.nta.org.tw/oldphpbb2/viewtopic.php?t=32221　連結已失效
藍藍天上一朵雲2005版第45題
　
當初在2006年的時候在ptt的數學版有人發表過答案，只是時間一久原始的文章已經刪除了
我當時只有將內文備份下來,文章標題和作者沒有備份到
　
正確答案是1092*4!*4!*4!=15095808

附上驗證的程式碼
[font=Fixedsys]#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int total=0;
char a[15]="aaaabbbbcccc";
do{
for(int i=1;i<12;i++)
if(a[i-1]==a[ i ])
goto HERE;
total++;
HERE:
}while (next_permutation(a,a+12));
printf("%d",total);
return 0;
}[/font]

bugmens 發表於 2008-12-20 21:23

[font=Fixedsys]可以用動態歸劃(dynamic programming)來做
先考慮4個A(美國), 4個B(台灣), 4個C(日本)排成一列且同字不相臨的問題
令 w[x,y,z,c] (x,y,z = 0 ~ 4, c = A or B or C)
為 x 個A, y個B, z個C 排成一列且最後一個字母為c 同字不相臨的方法數
例如 w[3,2,2,A] 就是3個A, 2個B, 2個C排成一列且最後一個字母為A 同字不相臨的方法數
我們的問題就是要求 w[4,4,4,A] + w[4,4,4,B] + w[4,4,4,C]. 但跟據對稱,
w[4,4,4,A] = w[4,4,4,B] = w[4,4,4,C]. 所以 3* w[4,4,4,A] 就是答案.
顯然的, 有關係式
   w[x,y,z,A] = w[x-1,y,z,B] + w[x-1,y,z,C]
   w[x,y,z,B] = w[x,y-1,z,C] + w[x,y-1,z,A]
  以及 w[x,y,z,C] = w[x,y,z-1,A] + w[x,y,z-1,B] 成立(為什麼?)
還有邊界條件 w[0,k+1,k,B] = w[0,k,k,B] = 1(為什麼? 還有哪些對稱的式子?)
有了這些工具以後, 就可以開始著手算w[4,4,4,A],
先算 w[1,1,1,A] w[1,1,2,A] w[1,1,2,B] w[1,1,3,A] .... w[1,1,4,B],
w[1,2,2,A] w[1,2,2,B] ......等等一路算上去過程中會發現算出的值稍後
立即會用到所以得保留下來不要立即擦掉
經過約一張A4大小的計算可以得到 w[4,4,4,A] = 364, 所以最後答案就是3 * 364 * 4!*4!*4![/font]

bugmens 發表於 2008-12-20 21:34

[font=Fixedsys]這個討論法要討論 A A A A 五個空格中
　　　　　　　　4 1 2 3 5
中間三個空格到底用B填了幾個以及外面那兩個空格
1.分成三個一個
(i)如果BBB,B插在中間三個位置的其中兩個  那就有3*2種方法
例如AB B BABA A
　　　　 C C　　C
　此時C一定要插入BBB中間的兩個空位  以及剩下的兩個A中間那個空位
　最後一個C有六個位置可選  故有3*2*6=36種
(ii)如果BBB,B只有插入中間三個位置的其中一個  那有3*2*2!種方法
　例如 B B BABA A A
　　　　 C C　　C C
　那C一定得插入上面四個地方只有一種方法  因此有3*2*2=12種
2.分成兩個,兩個
(i)如果BB,BB插入中間的三個空位中的兩個那就有C(3,2)種方法
　例如AB BAB BA A
　　　　 C　 C　C
　這樣C一定要插入上面三個地方  剩下一個C有六個位置可以選故有3*6=18種
(ii)如果BB,BB只插入中間三個位置的其中兩個  那就有C(3,1)C(2,1)種方法
　例如 B BAB BA A A
　　　　 C　 C　C C
　這樣C一定要插入上面四個地方  只有一種方法  因此有3*2*1=6種
3.分成兩個一個一個  BB,B,B
(i)如果這三個將中間三個空格填滿  例如AB BABABA
那C只一定要插入一個地方  其他三個C有八個選擇因此是C(3,1)*C(8,3)=168
(ii)如果這三個只插入中間兩個空格  一個在外面空格  例如 AB BABA AB
　　　　　　　　　　　　　　　　　　　　　　　　　　　　 C C
那C一定要插入上面兩個地方  其他兩個C有七個選擇
因此是C(3,2)C(2,1)*C(3,1)*C(7,2)=378
(iii)如果這三個空格只插入中間一個空格  兩個在外面空格  例如 BAB BA A AB
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 C  C C
那C一定要插入上面三個地方  剩下一個C有六個選擇
C(3,1)*C(3,1)*C(6,1)=54
4.分成B,B,B,B
(i)如果填滿中間三個  剩下一個放外面  有兩種可能剩下四個C有九個位置可以選因此是2*C(9,4)=252
(ii)如果中間三格只填兩格  剩下兩個放外面  例如 BABA ABAB
　　　　　　　　　　　　　　　　　　　　　　　　　 C
那有一個位置一定要填C  剩下三個C有八個位置可以選因此是C(3,2)C(8,3)=168
一共是36+12+18+6+168+378+54+252+168=1092最後再乘上4!4!4![/font]

bugmens 發表於 2008-12-20 21:37

[font=Fixedsys]4個美國人，4個台灣人，4個日本人排成一列，且同一國的人不得相鄰請問有幾種排法？
這問題麻煩在數字有點大.討論起來比較麻煩..........
假設三種人分別為 A B C
其中 (A,B,C) = (美,台,日)、(美,日,台)、(台,美,日)、
      (台,日,美)、(日,台,美)、(日,美,台) 這六種情形..............(一)
先固定A => 1  A  2  A  3  A  4  A  5    (有1.2.3.4.5這五個空位)
討論B去插入這五個位置.以及C的插入方法數...................................(二)
(1) 四個B排在一起
不可能.因為會變成 A B B B B A A A
至少需要五個C來插入才符合題意 ( A B C B C B C B A C A C A )
所以有0種排列
(2) 三個B排在一起
變成 B B B A B A A A (有5*4種方法=20種)
此時C要去插入
必定得先插入3個B中之間的2個位置 => B C B C B A B A A A
然後再插入3個A中之間的2個位置 => B C B C B A B A C A C A
因此C只有1種方法
所以共有20種排列
?
(3) 兩個B.兩個B
變成  B B A B B A A A (有C5取2種方法=10種)
此時C要去插入
必定得先插入兩組2個B中之間的2個位置  => B C B A B C B A A A
然後再插入3個A中之間的2個位置       => B C B A B C B A C A C A
因此C只有1種方法
所以共有10種排列
(4) 兩個B.一個B.一個B
變成  B B A B A B A A (有5*C4取2種方法=30種)
此時C要去插入
必定得先插入2個B及2個A中之間的位置 =>  B C B A B A B A C A
然後再從剩下允許的7個位置選兩個下去放 => 1B C B2A3B4A5B6A C A7
因此C有C7取2種 = 21種方法
所以共有30*21=630種排列
BY (一)及(二)
共有 6*(20+10+630) = 6*660 = 3960 種排列
另外.4個美國人.4個台灣人.四個日本人不會都是複製人
所以要再乘上 4!*4!*4! = 13824

所以答案是 3960*13824 = 54743040 種排列方式[/font]

bugmens 發表於 2011-9-4 09:23