篮子里有一些白球与黄球

篮子里有一些白球与黄球 IEEM 5109 – 2009f National Tsing Hua University Department of Industrial Engineering and Engineering Department The Design and Analysis of Computer Algorithms Assignment #3 ( Due date: Oct. 13 ) 1. Give a recursive definition for the sequence. n(1-1) a = 4n , 2 (1-2) a = n(n+1) (1-3) a = 1 + (,1) nnn 2. Solve the recurrence relation -1) T(n) = 8T(n-1) -15T(n-2) where T(1) = 1, T(2) = 2. (2 (2-2) T(n) = 8T(n-1) -15T(n-2) where T(1) = 2, T(2) = 6. (2-3) T(n) = 3T(n-1) -2T(n-2) where T(0) = 1, T(1) = 1. (2-4) T(n) = 3T(n-1) -2T(n-2) where T(0) = 2, T(1) = 4. (Hint: Solve the characteristic equations.) 3. Solve the following recurrence relation by using substitution method: 1n,1, (3-1). T(n),,3T(n,1)，2n,2, 1n,4,,T(n), (3-2) ,T(n)，cn,5,, 1n,4,,T(n), (3-3) ,2T(n)，lognn,5,, 1n,4,,T(n), *(3-4) logn,2T(n)，n,5,loglogn, 1n,4, ,T(n), * (3-5) , ,T(n,1)，T(n,2)，T(n,3)n,4, Extra problems for thinking: IEEM 5109 – 2009f A. 籃子裡有一些白球與黃球, 我們利用下列的規則來移動這些球: (i) 每一次由籃子內抓出二球。 (ii) 如二球是同一顏色, 則放一黃球回籃子(我們假設旁邊有足夠多的黃球可以 使用)。 (iii)如二球是不同顏色, 則放一白球回籃子(其中的黃球就不放回去)。 依此規則抓球, 直到籃子內只剩一球時, 遊戲結束。令 m = 開始時, 籃子內白球的個數。 n = 開始時, 籃子內黃球的個數。 f (m, n) = 結束時, 籃子內球的顏色。 對各種m, n, 求f (m, n)。 B. 有一年倫敦地鐵公司有一則廣告: "以下有五個數列, 假如您到站時能想出每一數列的下一個數目, 請駕臨本公司辦公室, 我們將提供您一個很好的工作機會。" 1, 2, 4, 8, 16, 32, 0, 1, 3, 6, 10, 15, 1, 1, 2, 3, 5, 8, 2, 9, 28, 65, 126, 2, 3, 5, 7, 11, 13, (a) 對以上數列儘量去找出合理的下一個數以及第 n 項。 (b) 您是否也可以想出一些數列考考別人。 IEEM 5109 – 2009f n,,C. 在一圓周上又有n個等距離的點可劃出條弦,令C(n)為這n條弦所切割出,,,,2,,區域的個數(如下圖),請推導C(n) 的公式。 C(3) = 4C(1) = 1C(2) = 2 C(5) = 16C(4) = 8