創作內容

1 GP

ZeroJudge - e895: 好多正方形 解題心得

作者:Not In My Back Yard│2020-03-01 00:43:42│贊助:2│人氣:85
題目連結:


題目大意:
給定若干列輸入(≦ 100000 列),給定一正整數 L (L ≦ 100000),代表一條長度為 L 的通道。要在該通道上放置正方形的貨物。正方形之邊長不超過 L 單位,最小可為 1 單位長。

請問用長度 1 ~ L 的正方形貨物堆滿長度 L 的通道有多少方法?請將該數取除以 10007 的餘數後輸出。



範例輸入:
123


範例輸出:
5859


解題思維:
可以看到 L = 1 時,方法數顯而易見的是 1 。

當 L > 1 時,可以觀察到 L 的方法數是由:
L - 1 的所有方法數後頭接一個 1 單位長的正方形;
L - 2 的所有方法數後頭接一個 2 單位長的正方形;
……
1 的所有方法數後頭接一個 L - 1 單位長的正方形;
再加上只有一個 L 單位長的正方形之方法。
也就是 L - 1 ~ 1 全部的方法數總和 + 1。

而多試幾個 L 值,可以發現方法數似乎為 2 ^ (L - 1) 。

L = 1 符合命題。並假設 L < k 的值都符合該公式,且 L = k 的方法是由 L ~ 1 而來。
因此 L = k 的方法數為

2 ^ (1 - 1)  + 2 ^ (2 - 1)  + 2 ^ (3 - 1)  + …… + 2 ^ ((L - 1) - 1) + 1 =
[2 ^ (L - 1) - 1] + 1 = 2 ^ (L - 1) 。

也符合命題。所以根據數學歸納法,命題為真。

所以 2 ^ (L - 1) 即是所求。但是請記得在求解的過程需要取 10007 的餘數。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4702315
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

1喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

hsiaotong
看更多我要大聲說14小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】