青蛙換邊遊戲
規則
- 兩邊有相同數量的青蛙
- 青蛙只能往前跳, 不能退後
- 青蛙能跳到前方空格或跳躍另一隻青蛙到另一隻青蛙前的空格
- 看不懂可以直接玩一下網路上的遊戲
問題
- 當青蛙變成 80 隻時, 那總共需要跳幾步才可以完成換邊?
- 當青蛙變成 91 隻時, 那總共需要跳幾步才可以完成換邊?
解答
- 解這題的策略就是直接由 1 隻青蛙玩到 6 隻, 再來從其中找出規則..
- 以下是玩過後的筆記
簡單整理結論
青蛙數奇數和偶數的規則不太相同- 第一步驟往下與最後步驟往上, 會有鏡射排列對應的結果, Exp. 0:111-000 ⇒ 15:000-111 , 1:11-1000 ⇒ 14:0001-11
- 青蛙數偶數時, 正中間步驟與其他步驟都無鏡射排列對應關係, 但本身數列前後會有鏡射狀況, Exp. 1010-0101
所以觀測結果分成青蛙數奇數一組,偶數另一組.
| 青蛙數 | 需要步驟數 |
|---|---|
| 1 | 3 |
| 2 | 8 |
| 3 | 15 |
| 4 | 24 |
| 5 | 35 |
| 6 | 48 |
發現與推論
- 在偶數組發現可以 2 * 4 ⇒ 8 , 4 * 6 ⇒ 24 , 6 * 8 ⇒ 48 所以推論
- 8 * 10 ⇒ 80
- 10 * 12 ⇒ 120
- 在奇數組兒子發現可以 (1+1)*(1+1)-1 ⇒ 3 , (3+1)*(3+1)-1 ⇒ 15 , (5+1)*(5+1)-1 ⇒ 35 所以推論
- (7+1)*(7+1)-1 ⇒ 63
- (9+1)*(9+1)-1 ⇒ 99
- 當不分奇數偶數組直接觀察, 發現差異數有規則性 — 蔡宗融 2012-11-27 01:02
| 青蛙數 | 需要步驟數 | 差異數 |
|---|---|---|
| 1 | 3 | - |
| 2 | 8 | 5 |
| 3 | 15 | 7 |
| 4 | 24 | 9 |
| 5 | 35 | 11 |
| 6 | 48 | 13 |
- 在睡到一半突然發現這差異數竟然就是和正方形數有關..
- 所以之前推論的奇數 (n+1)*(n+1)-1 與偶數 n*n(+2) 其實是可以透過正方形數來解釋為何長得這樣子的原因, 而且兩個推論公式都可直接使用, 並不需區分出奇數與偶數.
給程式的原則
- 因為有一些看法和兒子不同, 需要增加一些青蛙數來確認推論結果是否正確, 但手工紀錄以及多增加一隻青蛙就多很多步驟, 非常花時間, 所以就考慮先歸納出人工的走法, 這樣就可以用來寫個程式幫忙走
- 所歸納給程式的原則如下:
- Steps Rule :
- n 奇數 : Steps = (n+1)*(n+1)-1
- n 偶數 : Steps = n*(n+2)
- Move Rule :
- 出現 10- ⇒ -01
- 出現 -10 ⇒ 01-
- 出現 1-0 時, m:-的位置 if(m⇐n+1) then ⇒ -10 else ⇒ 10-
- Stop Rule :
- n 奇數 : 出現與上一個排列是 Mirror 就結束(pop stack 的 mirror 步驟)
- n 偶數 : 出現兩邊對稱 Exp. 1010-0101
產生的程式碼
產生的結果
- 4 隻青蛙
- 5 隻青蛙
- 8 隻青蛙
- 9 隻青蛙
- 10 隻青蛙
- 11 隻青蛙
- 12 隻青蛙
載入中 ...
4 隻青蛙
[jonathan@c2q-q9400 ~]$ perl math02.pl 4
It should move [24] steps!
0: [1111-0000]
1: [111-10000]
2: [11101-000]
3: [111010-00]
4: [1110-0100]
5: [11-010100]
6: [1-1010100]
7: [101-10100]
8: [10101-100]
9: [1010101-0]
10: [10101010-]
11: [101010-01]
12: [1010-0101]
13: [10-010101]
14: [-01010101]
15: [0-1010101]
16: [001-10101]
17: [00101-101]
18: [0010101-1]
19: [001010-11]
20: [0010-0111]
21: [00-010111]
22: [000-10111]
23: [00001-111]
24: [0000-1111]
結論
- 確定一開始的發現與推論是正確的, 所以需要的步驟數可以有兩種公式表示出來:
- Steps = (n+1)*(n+1)-1
- Steps = n*(n+2)
- 當青蛙變成 80 隻時, 那總共需要跳幾步才可以完成換邊?
- 答案是 (80+1)*(80+1)-1=81*81-1=6560
- 答案是 80*(80+2)=80*82=6560
- 當青蛙變成 91 隻時, 那總共需要跳幾步才可以完成換邊?
- 答案是 (91+1)*(91+1)-1=92*92-1=8463
- 答案是 91*(91+2)=91*93=8463