作者phoenixrace (殘存亦陌路 兵敗如山倒)
看板Prob_Solve
標題[問題] 面試再次遇到的問題
時間Mon Oct 1 07:24:43 2018
最近寫Visa OA遇到的問題
問題:
假如有一個數字n, 你每次可以拿1個或3個請問有幾種不同組合?
範例1:
n = 7
所有的組合有9種, 回傳9:
[1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 3]
[1, 1, 1, 3, 1]
[1, 1, 3, 1, 1]
[1, 3, 1, 1, 1]
[3, 1, 1, 1, 1]
[1, 3, 3]
[3, 1, 3]
[3, 3, 1]
我用背包問題的解法, time complexity 是O(n), 可是會timeout, 因為 1 <= n <= 1e9,想請問一下有沒有log(N)的解法？
感謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.219.21.1
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1538349886.A.326.html
1F：→ Morris1028: 變形費氏數列 矩陣乘法求解 10/01 07:55
我有想到這個, 可是要怎麽設定一開始的矩陣, 我就卡在這了, 一般的fib是2d matrix相乘, 可是這個我不知道從何下手
2F：→ Morris1028: 3*3 矩陣 列出連續三項的公式，線性變換？的矩陣就會 10/01 08:17
3F：→ Morris1028: 出來 10/01 08:17
再問個問題,為啥看得出來是Fib,是因為我們的取法只有1和3嗎？假如我們可以取1,3,5也可以用FIB計算嗎？
4F：推 LPH66: 本家費氏數列是取 1 或 2 個, 可以比較一下公式 10/01 09:05
感謝 我再去研究看看
※ 編輯: phoenixrace (129.219.21.3), 10/01/2018 10:52:11
5F：推 JameC: 取1，3，5公式就變成Fi=Fi-1+Fi-3+Fi-5 10/01 23:06
6F：推 cutekid: 他的重點是有 10 億項，所以須要更快的方法 10/02 09:45
7F：推 yvb: 倒底是問幾種組合還是排列方式? 只要知道幾種還是要條列出來? 10/02 20:54
8F：→ yvb: 要條列的話, n=1e9 會不會光印結果就超時了? 10/02 20:57
9F：推 cutekid: F(n) = F(n-1) + F(n-3),求 F(1,000,000,000) 10/03 01:21
10F：推 yvb: 抱歉, 請忽略我前面腦殘. 原PO 需要引入矩陣快速冪算法. 10/04 22:46
已經知道怎麼解了, 感謝大家幫忙
※ 編輯: phoenixrace (24.251.165.125), 10/17/2018 03:41:26