作者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/cn.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