推 newline:2^2004 ? 05/16 19:02
推 minnycat:2^2003 05/16 22:12
> -------------------------------------------------------------------------- <
作者: doa2 (邁向高手之路) 看板: tutor
標題: Re: [解題] 基隆高中數學老師出的難題
時間: Tue May 16 15:25:41 2006
※ 引述《BARGARYARLOO (>.<" 便秘臉)》之銘言：
: 將2006個格子排成一列，以紅、黃、藍三色圖在格子內，每個格子塗一種顏色，規定相鄰
: 不能同色 且頭尾均塗紅色 ，試問有多少種塗色法?
: 謝謝~~
用遞迴解吧
假設n個格子頭尾都塗紅色的塗法有f(n)種
那f(n)=f(n-1)+2f(n-2)
分兩種討論 倒數第三格是紅色和倒數第三格不是紅色
如果倒數第三格不塗紅色 那方法就是f(4)(因為這種的一定可以在倒數第二格塗上紅色)
_ _ _ _ _
R X(R)
現在第四格不塗紅色改塗跟第三格不同的顏色(一定只有一種)
然後第五格塗上紅色 這樣就是其中一種可能(就是倒數第三格不是紅色)
_ _ _ _ _
R R
如果倒數第三格是紅色 那方法有f(n-2)種
那麼倒數第二格有兩種選擇 最後一格再塗上紅色
因此有2*f(n-2)種
因此得到f(n)=f(n-1)+2f(n-2)
然後從f(3)=2 f(4)=2開始解起..
答案似乎是(-2+2^2005)/3
遞迴過程應該可以自行解決吧??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.84.128.123
※ 編輯: doa2 來自: 219.84.128.123 (05/16 15:38)
推 huangtim:魔人你最近很少上MSN喔~ 05/16 16:08
推 BARGARYARLOO:是強者 XD 05/16 16:17
推 doa2:剛剛發現今年指考的研究用試卷囚犯那題跟這題很像喔~ 05/16 17:28
→ doa2:大家可以去算算看.. 05/16 17:29
> -------------------------------------------------------------------------- <
作者: jerrylau (站在巨人的肩上) 看板: tutor
標題: Re: [解題] 基隆高中數學老師出的難題
時間: Tue May 16 17:58:50 2006
※ 引述《doa2 (邁向高手之路)》之銘言：
: ※ 引述《BARGARYARLOO (>.<" 便秘臉)》之銘言：
: : 將2006個格子排成一列，以紅、黃、藍三色圖在格子內，每個格子塗一種顏色，規定相鄰
: : 不能同色 且頭尾均塗紅色 ，試問有多少種塗色法?
: : 謝謝~~
: 用遞迴解吧
: 假設n個格子頭尾都塗紅色的塗法有f(n)種
: 那f(n)=f(n-1)+2f(n-2)
: 分兩種討論 倒數第三格是紅色和倒數第三格不是紅色
: 如果倒數第三格不塗紅色 那方法就是f(4)(因為這種的一定可以在倒數第二格塗上紅色)
: _ _ _ _ _
: R X(R)
請問一下,這部分我覺得怪怪的,如果方法是f(4),那第五格最後一定要塗紅色
不就犯規了嗎....這樣會造成第四格與第五格皆為紅色
所以我的想法為 不可用f(n-1)來算 若使用f(n-1),則f(n)必定會犯規
我的式子為f(n)=2f(n-2)+2f(n-3)+2,其中n > = 6
~~2這部分為只有首末紅色,其餘皆不為紅色
f(3)=2,f(4)=2,f(5)=6開始解
不過接下來就不會解了
不知道我的想法是否有錯誤?????
: 現在第四格不塗紅色改塗跟第三格不同的顏色(一定只有一種)
: 然後第五格塗上紅色 這樣就是其中一種可能(就是倒數第三格不是紅色)
: _ _ _ _ _
: R R
: 如果倒數第三格是紅色 那方法有f(n-2)種
: 那麼倒數第二格有兩種選擇 最後一格再塗上紅色
: 因此有2*f(n-2)種
: 因此得到f(n)=f(n-1)+2f(n-2)
: 然後從f(3)=2 f(4)=2開始解起..
: 答案似乎是(-2+2^2005)/3
: 遞迴過程應該可以自行解決吧??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.149.67
> -------------------------------------------------------------------------- <
作者: doa2 (邁向高手之路) 看板: tutor
標題: Re: [解題] 基隆高中數學老師出的難題
時間: Tue May 16 18:08:04 2006
※ 引述《jerrylau (站在巨人的肩上)》之銘言：
: ※ 引述《doa2 (邁向高手之路)》之銘言：
: : 用遞迴解吧
: : 假設n個格子頭尾都塗紅色的塗法有f(n)種
: : 那f(n)=f(n-1)+2f(n-2)
: : 分兩種討論 倒數第三格是紅色和倒數第三格不是紅色
: : 如果倒數第三格不塗紅色 那方法就是f(4)(因為這種的一定可以在倒數第二格塗上紅色)
: : _ _ _ _ _
: : R X(R)
: 請問一下,這部分我覺得怪怪的,如果方法是f(4),那第五格最後一定要塗紅色
: 不就犯規了嗎....這樣會造成第四格與第五格皆為紅色
如果第三格不是紅色 那第四格一定"可以"塗上紅色(不是說他真的塗上紅色喔)
所以總共有f(4)種 現在我第四格不塗紅色而塗其他顏色(一定只有一種方法)
然後第五格塗上紅色 這就是第三格不是紅色而最後一格是紅色的方法
: 所以我的想法為 不可用f(n-1)來算 若使用f(n-1),則f(n)必定會犯規
: 我的式子為f(n)=2f(n-2)+2f(n-3)+2,其中n > = 6
: ~~2這部分為只有首末紅色,其餘皆不為紅色
: f(3)=2,f(4)=2,f(5)=6開始解
: 不過接下來就不會解了
: 不知道我的想法是否有錯誤?????
f(n-3)怎麼討論的..??
你這個式子f(6)=10 f(7)=18..但是f(7)=20 你可以驗算看看
: : 現在第四格不塗紅色改塗跟第三格不同的顏色(一定只有一種)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
: : 然後第五格塗上紅色 這樣就是其中一種可能(就是倒數第三格不是紅色)
: : _ _ _ _ _
: : R R
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.84.128.123
※ 編輯: doa2 來自: 219.84.128.123 (05/16 18:12)
> -------------------------------------------------------------------------- <
作者: jerrylau (站在巨人的肩上) 看板: tutor
標題: Re: [解題] 基隆高中數學老師出的難題
時間: Tue May 16 19:38:04 2006
※ 引述《doa2 (邁向高手之路)》之銘言：
: ※ 引述《jerrylau (站在巨人的肩上)》之銘言：
: : 請問一下,這部分我覺得怪怪的,如果方法是f(4),那第五格最後一定要塗紅色
: : 不就犯規了嗎....這樣會造成第四格與第五格皆為紅色
: 如果第三格不是紅色 那第四格一定"可以"塗上紅色(不是說他真的塗上紅色喔)
: 所以總共有f(4)種 現在我第四格不塗紅色而塗其他顏色(一定只有一種方法)
: 然後第五格塗上紅色 這就是第三格不是紅色而最後一格是紅色的方法
: : 所以我的想法為 不可用f(n-1)來算 若使用f(n-1),則f(n)必定會犯規
: : 我的式子為f(n)=2f(n-2)+2f(n-3)+2,其中n > = 6
: : ~~2這部分為只有首末紅色,其餘皆不為紅色
: : f(3)=2,f(4)=2,f(5)=6開始解
: : 不過接下來就不會解了
: : 不知道我的想法是否有錯誤?????
: f(n-3)怎麼討論的..??
: 你這個式子f(6)=10 f(7)=18..但是f(7)=20 你可以驗算看看
: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
我知道我問題在哪裡了
應該是f(n)=2f(n-2)+2f(n-3)+2f(n-4)+....+2f(3)+2
故f(n-1)=2f(n-3)+2f(n-4)+...+2f(3)+2
所以f(n)=2f(n-2)+[2f(n-3)+2f(n-4)+...+2f(3)+2]=2f(n-2)+f(n-1)
這樣式子就和d大的一樣了
不過d大可以馬上看出f(n)=f(n-1)+2f(n-2)真的很厲害...
我的想法是 舉例f(7)好了 R _ _ _ _ _ R
1 2 3 4 5 6 7
f(7)中第6格不可為紅色,要從第5格開始,即f(5),此時第6格有兩種選擇
所以方法數為2f(5)
同理,第4格,第3格都可為紅色,第2格就不可為紅色
故f(7)=2f(5)+2f(4)+2f(3)+2
~~最後加這個2為編號2~6的位置都不為紅色
可以類推f(8)=2f(6)+2f(5)+2f(4)+2f(3)+2
^^^^^^^^^^^^^^^^^^^
=2f(6)+f(7) 就是d大的式子了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.164.206
> -------------------------------------------------------------------------- <
作者: XII (MathKid) 看板: tutor
標題: Re: [解題] 基隆高中數學老師出的難題
時間: Wed May 17 12:23:04 2006
※ 引述《BARGARYARLOO (>.<" 便秘臉)》之銘言：
: 將2006個格子排成一列，以紅、黃、藍三色圖在格子內，每個格子塗一種顏色，規定相鄰
: 不能同色 且頭尾均塗紅色 ，試問有多少種塗色法?
: 謝謝~~
(1/3)((3-1)^2005+(3-1)(-1)^2005)=(2^2005-2)/3
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.147.21
> -------------------------------------------------------------------------- <
作者: Kim0716 (小金) 看板: tutor
標題: Re: [解題] 基隆高中數學老師出的難題
時間: Wed May 17 16:52:32 2006
※ 引述《XII (MathKid)》之銘言：
: ※ 引述《BARGARYARLOO (>.<" 便秘臉)》之銘言：
: : 將2006個格子排成一列，以紅、黃、藍三色圖在格子內，每個格子塗一種顏色，規定相鄰
: : 不能同色 且頭尾均塗紅色 ，試問有多少種塗色法?
: : 謝謝~~
: (1/3)((3-1)^2005+(3-1)(-1)^2005)=(2^2005-2)/3
可以問一下我的方法哪裡有錯嗎
還有想問一下上面那個式子每個數所代表的是什麼
第二格黃 倒數第二格黃時 方法數2^2002
第二格黃 倒數第二格藍時 方法數2^2002
第二格藍 倒數第二格黃時 方法數2^2002
第二格藍 倒數第二格藍時 方法數2^2002
所以總共 4*(2^2002)=2^2004
請高手們回答一下
感激不盡 <(_ _)>
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.94.49
> -------------------------------------------------------------------------- <
作者: doa2 (邁向高手之路) 看板: tutor
標題: Re: [解題] 基隆高中數學老師出的難題
時間: Wed May 17 17:38:09 2006
※ 引述《Kim0716 (小金)》之銘言：
: ※ 引述《XII (MathKid)》之銘言：
: : (1/3)((3-1)^2005+(3-1)(-1)^2005)=(2^2005-2)/3
: 可以問一下我的方法哪裡有錯嗎
: 還有想問一下上面那個式子每個數所代表的是什麼
: 第二格黃 倒數第二格黃時 方法數2^2002
很明顯的不是2^2002..
因為第四格如果不是黃色
那第三格就不會有兩種選擇..
同理倒數第四格如果不是黃色 那倒數第三格就不會有兩種選擇..
: 第二格黃 倒數第二格藍時 方法數2^2002
: 第二格藍 倒數第二格黃時 方法數2^2002
: 第二格藍 倒數第二格藍時 方法數2^2002
: 所以總共 4*(2^2002)=2^2004
: 請高手們回答一下
: 感激不盡 <(_ _)>
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.84.128.123
推 Kim0716:懂了 謝謝 05/17 18:53