algorithm - 不同的方式 int n 可以分成 1 或 2 组

Question

这是向我提出的作业问题:

A patient has n pills to take. In each day, he can take either one pill or two pills until all pills are gone. Let T(n) denote the number of different ways the patient can take all n pills. Give a closed form for T(n). (Note that – for example – the two sequences (1, 2, 2) and (2, 1, 2) are considered as two different ways of taking 5 pills.)

我已经尝试处理 n = 1 到 8 的集合，看看我是否能找到这样的模式:

n=1 {1} n=2 {{1,1},{2}} n=3 {{1,1,1},{1,2},{2,1}} n=4 {{1,1,1,1},{1,1,2},{1,2,1},{2,1,1},{2,2}} ...

但是一直做不到。 n=1-8的组合是1,2,3,5,8,12,18,25

有人有想法吗？

Answer 1

您的示例在 8 之后显示了错误的值(应该是 13...)。

考虑下一个方法:在最后一天，患者可以吃一颗或两颗药丸(n = (n-1) + 1 或 n = (n-2) + 2)。所以组成 T(n) 值的方法数是

T(n) = T(n-1) + T(n-2)

对 T(n-1) 和 T(n-2) 重复相同的过程，您将在 T(0) 或 T(1) 处完成 - 这些值显然等于 1。

因此构建递归序列并解决任何 n 的递归问题。

请注意，您可以从末尾展开递归(递归方法)并从 0/1 - 迭代方法开始。

当您找到正确的值时，您可能会发现它们形成著名的序列并阅读更多相关信息。