青蛙換邊遊戲

  1. 兩邊有相同數量的青蛙
  2. 青蛙只能往前跳, 不能退後
  3. 青蛙能跳到前方空格或跳躍另一隻青蛙到另一隻青蛙前的空格
  • 看不懂可以直接玩一下網路上的遊戲
  • 當青蛙變成 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 :
      1. 出現 10- ⇒ -01
      2. 出現 -10 ⇒ 01-
      3. 出現 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
  • start/math/20121124.txt
  • 上一次變更: 2021/03/05 23:35
  • jonathan