割手鍊
a.格羅莉亞是來自阿肯色的一位年輕女士,正在加利福尼亞走訪,她想在旅店租一間房間,準備住7天。
b.店員:房間20美元一天,必須付現金。
格羅莉亞:對不起,先生,我一點兒現金沒有,但我有一個金手鍊,七節中每節價值超過20美元。
c.店員:好吧,把手鍊給我。
格羅莉亞:不,現在不行,我找個手飾匠把手鍊割開,每天我給你一節,最後有錢時我再把手鍊贖回來。
d.店員最後同意了,現在該格羅莉亞決定怎樣割手鍊了,她反而為難了。
e.格羅莉亞:我一定得小心,手飾匠每多割一節,每多接一節都要手工錢。
f.想了一會,格羅莉亞發現她不必每節都割,因為地可以來回兌換。當她想出能割幾節時,她簡直難以相信。你算出割幾節了嗎?
g.只需割一節,它應是從一端數第三節,把手鍊分成三段,各為1、2、4節,這足夠通過來回兌換使店員每天收到一節。
難解的鏈
解決這個問題需要兩個重要的觀點。首先按不同方法形成1、2、3、4、5、6、7節的鏈中,最小集合的鏈是1、2、4節的鏈,即形成等比數列,正如我們在上一個問題中知道的這是作為二進制基礎的冪系列。
第二是認識到僅割一次就能把手鍊分成所需的三段。
這個問題也可推廣到較長的鏈中。比如假設格羅莉亞有一條63節的金鍊,她想像手鍊一樣割開使用,一天用一節。割三個環就能達到目的。你知道怎麼辦嗎?對於任意長度的鏈你能想出一般方法來解決問題嗎
這個問題的一個有趣的變化就是幾節鏈首尾相連作為一個封閉的環。例如,假設格羅莉亞有一條項鍊,是一條79節金環的封閉鏈,一環花一天,要割幾環就可以花79天。
a.格羅莉亞是來自阿肯色的一位年輕女士,正在加利福尼亞走訪,她想在旅店租一間房間,準備住7天。
b.店員:房間20美元一天,必須付現金。
格羅莉亞:對不起,先生,我一點兒現金沒有,但我有一個金手鍊,七節中每節價值超過20美元。
c.店員:好吧,把手鍊給我。
格羅莉亞:不,現在不行,我找個手飾匠把手鍊割開,每天我給你一節,最後有錢時我再把手鍊贖回來。
d.店員最後同意了,現在該格羅莉亞決定怎樣割手鍊了,她反而為難了。
e.格羅莉亞:我一定得小心,手飾匠每多割一節,每多接一節都要手工錢。
f.想了一會,格羅莉亞發現她不必每節都割,因為地可以來回兌換。當她想出能割幾節時,她簡直難以相信。你算出割幾節了嗎?
g.只需割一節,它應是從一端數第三節,把手鍊分成三段,各為1、2、4節,這足夠通過來回兌換使店員每天收到一節。
難解的鏈
解決這個問題需要兩個重要的觀點。首先按不同方法形成1、2、3、4、5、6、7節的鏈中,最小集合的鏈是1、2、4節的鏈,即形成等比數列,正如我們在上一個問題中知道的這是作為二進制基礎的冪系列。
第二是認識到僅割一次就能把手鍊分成所需的三段。
這個問題也可推廣到較長的鏈中。比如假設格羅莉亞有一條63節的金鍊,她想像手鍊一樣割開使用,一天用一節。割三個環就能達到目的。你知道怎麼辦嗎?對於任意長度的鏈你能想出一般方法來解決問題嗎
這個問題的一個有趣的變化就是幾節鏈首尾相連作為一個封閉的環。例如,假設格羅莉亞有一條項鍊,是一條79節金環的封閉鏈,一環花一天,要割幾環就可以花79天。
收藏