====== 青蛙換邊遊戲 ======
===== 規則 =====
  - 兩邊有相同數量的青蛙
  - 青蛙只能往前跳, 不能退後
  - 青蛙能跳到前方空格或跳躍另一隻青蛙到另一隻青蛙前的空格
  * 看不懂可以直接玩一下網路上的遊戲 
    * [[http://media.ebaumsworld.com/2006/07/frogleap.swf|{{:start:math:snap467.png?200|}}]]

===== 問題 =====
  * 當青蛙變成 80 隻時, 那總共需要跳幾步才可以完成換邊?
  * 當青蛙變成 91 隻時, 那總共需要跳幾步才可以完成換邊?


===== 解答 =====
  * 解這題的策略就是直接由 1 隻青蛙玩到 6 隻, 再來從其中找出規則..
  * 以下是玩過後的筆記 {{:start:math:imag1473.jpg?800|}}
==== 簡單整理結論 ====
  * <del>青蛙數奇數和偶數的規則不太相同</del>
  * 第一步驟往下與最後步驟往上, 會有鏡射排列對應的結果, Exp. 0:111-000 => 15:000-111 , 1:11-1000 => 14:0001-11
  * 青蛙數偶數時, 正中間步驟與其他步驟都無鏡射排列對應關係, 但本身數列前後會有鏡射狀況, Exp. 1010-0101
  * <del>所以觀測結果分成青蛙數奇數一組,偶數另一組.</del>

^  青蛙數  ^  需要步驟數  ^
^   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
  * 當不分奇數偶數組直接觀察, 發現差異數有規則性  --- //[[tryweb@ichiayi.com|蔡宗融]] 2012-11-27 01:02//

^  青蛙數  ^  需要步驟數  ^  差異數  ^
^   1     |    3   |   -  |
^   2     |    8   |   5  |
^   3     |   15   |   7  |
^   4     |   24   |   9  |
^   5     |   35   |  11  |
^   6     |   48   |  13  |

  * 在睡到一半突然發現這差異數竟然就是和正方形數有關..{{:start:math:imag1477.jpg?600|}}
  * 所以之前推論的奇數 (n+1)*(n+1)-1 與偶數 n*n(+2) 其實是可以透過正方形數來解釋為何長得這樣子的原因, 而且兩個推論公式都可直接使用, 並不需區分出奇數與偶數.

==== 給程式的原則 ====
  * 因為有一些看法和兒子不同, 需要增加一些青蛙數來確認推論結果是否正確, 但手工紀錄以及多增加一隻青蛙就多很多步驟, 非常花時間, 所以就考慮先歸納出人工的走法, 這樣就可以用來寫個程式幫忙走{{:start:math:imag1474.jpg?550|}}{{:start:math:imag1475.jpg?250|}} 
  * 所歸納給程式的原則如下:
    * 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
==== 產生的程式碼 ====
  * https://svn.ichiayi.com/opensvn/opentrysoft/math/math02.pl

==== 產生的結果 ====
{{tabinclude>start/math/20121124/4, start/math/20121124/5, start/math/20121124/8, start/math/20121124/9, start/math/20121124/10, start/math/20121124/11, start/math/20121124/12}} 

===== 結論 =====
  * 確定一開始的發現與推論是正確的, 所以需要的步驟數可以有兩種公式表示出來:
    * 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