Re: [中學] 競賽遊戲

[diow1 ()]

※ 引述《diow1 ()》之銘言：
:   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
:   │  │2 │3 │4 │5 │6 │7 │8 │9 │
:   │  │  │  │  │  │  │  │  │  │
:   └─┴─┴─┴─┴─┴─┴─┴─┴─┘
:    規則: 1.可 移動一格  至 空格處
:          2.可 跳一格    至 空格處(如象棋跳山,舉例:3跳過2這座山就變成 32空456789
:   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
:   │  │9 │8 │7 │6 │5 │4 │3 │2 │
:   │  │  │  │  │  │  │  │  │  │
:   └─┴─┴─┴─┴─┴─┴─┴─┴─┘
:    最少幾個步驟完成 ?
:

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 163.19.242.182
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1397093337.A.888.html
推 ipost       :答案是36次嗎?
→ ipost       :對任一數對(i,j),如果它們的起始位置和完成位置是反
→ ipost       :向的,則 "錯位數"加一, 所以本題有28個錯位.一次跳山
→ ipost       :會減少一個錯位數,所以需要至少28次跳山.連續幾次跳
→ ipost       :山後要一次平移才能再跳.當空格在偶數位可連跳山四次
→ ipost       :當空格在位置0或8可連跳四次,在位置1或7可連跳三次,
→ ipost       :所以跳法就是 接連跳到不能跳,把空格平移一位,再連跳
→ ipost       :共28次跳山加上8次平移=36次