作者jurian0101 (小維)
看板puzzle
標題[問題] 河內塔變形
時間Sun Feb 28 13:40:33 2010
其實一開始是開箱文－－
Knuth 《空固力數學》(Concrete Mathmatics: ) 入手，將鏘~~
中文版真的頗適合當作床頭書，其次功能就是練功與查找一些經典的題目。
附記: 每次去台電大樓
古今書坊都會讓我痛下殺手，五折起(或更低)的書價太誘人啦~~~
==============================================================================
然後就是正題：
大家都知道，N階河內塔最小次數的封閉式是 2^N - 1 次。下面的題目有的書裡面有，
有的...沒有(廢話!)
1. 正統規則，換成四柱+N盤
a.H(N) = ?
2. "鄰居"規則: 加上規則「柱子1、2、3，盤子只能搬移到隔壁。即禁止1-3」。
目標一樣──將N盤從1移到3。
a.H(5) = ?
b.H(N) = ?
3. "鄰居"規則 + 四柱
→忘了補，當然指的是
1搬到4的次數
a.求H(1~5)
*可以預見會有很多版本的答案出現^_^
b.封閉式H(N)
*似乎規則不單純。我還沒解出來，望各位指教
4. "鄰居" + 無限柱子
1, 2, 3, 4, ...,k ,...
a.求N盤，從第1柱搬到第M+1柱 (右移M的意思)
*其實這題最簡單，不要被騙
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.243.60
推 penguin7272:推水泥數學XD 02/28 13:48
→ jurian0101:拿1,5,10,20,50元銅板來排排看如何?? 02/28 13:49
推 flamerecca:第四非常不錯 02/28 14:42
→ penguin7272:第四是 (M+N)(N-1)+M ? 02/28 14:47
→ jurian0101:就是這樣(攤手) 02/28 16:14
→ jurian0101:不如寫成N^2 + M(N-1) 順便顯示出歸納過程 02/28 16:26
推 utomaya:Knuth是不是一個很有名的人? 為什麼我常看到這個人的名字? 02/28 19:04
→ utomaya:我是指在離散數學的領域中 02/28 19:04
→ fjufly:作者拼錯了，是Knuth才是，而數學的英文字少了一個e 02/28 23:01
推 joeyeh:他有很多貢獻喔我教授有提到你去史丹佛可以聽他講課 02/28 23:29
這麼說似乎joeyeh大聽過他的課的樣子
→ joeyeh:不過他講資料庫講得變純數學喔~~~呵呵 02/28 23:30
推 joeyeh:1974圖靈獎... 02/28 23:38
※ 編輯: jurian0101 來自: 140.112.243.60 (03/01 00:21)
推 joeyeh:我寫的是我教授有提到.....真是想太多 03/01 23:20