PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 面試再次遇到的問題

看板Prob_Solve (計算數學 Problem Solving)作者 (殘存亦陌路 兵敗如山倒)時間6年前 (2018/10/01 07:24), 6年前編輯推噓6(6推 0噓 4→)
留言10則, 5人參與, 6年前最新討論串1/1
最近寫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://www.ptt.cc/bbs/Prob_Solve/M.1538349886.A.326.html
→
10/01 07:55, 6年前 , 1F
變形費氏數列 矩陣乘法求解
10/01 07:55, 1F
我有想到這個, 可是要怎麽設定一開始的矩陣, 我就卡在這了, 一般的fib是2d matrix相乘, 可是這個我不知道從何下手
→
10/01 08:17, 6年前 , 2F
3*3 矩陣 列出連續三項的公式，線性變換？的矩陣就會
10/01 08:17, 2F
→
10/01 08:17, 6年前 , 3F
出來
10/01 08:17, 3F
再問個問題,為啥看得出來是Fib,是因為我們的取法只有1和3嗎？假如我們可以取1,3,5也可以用FIB計算嗎？
推
10/01 09:05, 6年前 , 4F
本家費氏數列是取 1 或 2 個, 可以比較一下公式
10/01 09:05, 4F
感謝 我再去研究看看 ※ 編輯: phoenixrace (129.219.21.3), 10/01/2018 10:52:11
推
10/01 23:06, 6年前 , 5F
取1，3，5公式就變成Fi=Fi-1+Fi-3+Fi-5
10/01 23:06, 5F
推
10/02 09:45, 6年前 , 6F
他的重點是有 10 億項，所以須要更快的方法
10/02 09:45, 6F
推
10/02 20:54, 6年前 , 7F
倒底是問幾種組合還是排列方式? 只要知道幾種還是要條列出來?
10/02 20:54, 7F
→
10/02 20:57, 6年前 , 8F
要條列的話, n=1e9 會不會光印結果就超時了?
10/02 20:57, 8F
推
10/03 01:21, 6年前 , 9F
F(n) = F(n-1) + F(n-3),求 F(1,000,000,000)
10/03 01:21, 9F
推
10/04 22:46, 6年前 , 10F
抱歉, 請忽略我前面腦殘. 原PO 需要引入矩陣快速冪算法.
10/04 22:46, 10F
已經知道怎麼解了, 感謝大家幫忙 ※ 編輯: phoenixrace (24.251.165.125), 10/17/2018 03:41:26
‣ 更多 phoenixrace 的文章
文章代碼(AID): #1RiLi-Cc (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 phoenixrace 的文章
文章代碼(AID): #1RiLi-Cc (Prob_Solve)