切換
舊版
前往
大廳
主題

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

Not In My Back Yard | 2020-03-01 00:43:42 | 巴幣 2 | 人氣 254
題目連結：
題目大意：
給定若干列輸入（≦ 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 的餘數。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

讓自己信心滿滿！！

看更多

更多創作

追蹤 創作集
其他創作
作品資料夾