解决递归关系，其中偶数和奇数存在单独的关系
Solve recurrence relation in which there is a separate relation for even and odd values
有人可以帮我解决这类问题吗？我应该遵循什么样的方法？
查看问题，因为你会被要求
- 多次评估复发
- 对于非常大的输入，
您可能需要
- 找到一个closed-form解决复发的方法，或者
- 找到一种方法来评估亚线性时间内递归的第 n 项。
现在的问题是如何做到这一点。我们来看看递归，它被定义为
- f(1) = f(2) = 1,
- f(n+2) = 3f(n) 如果 n 是奇数，并且
- f(n+2) = 2f(n+1) - f(n) + 2 如果 n 是偶数。
让我们从探索循环开始，看看是否出现任何模式。这里有一点很突出——这个循环的奇数项只依赖于循环中的其他奇数项。这意味着我们可以想象尝试将这种递归拆分为两个较小的递归：一个纯粹处理奇数项，一个纯粹处理偶数项。让 D(n) 是奇数项的序列，E(n) 是偶数项的序列。那么我们有
- D(1) = 1
- D(n+2) = 3D(n)
我们只需要在奇数上评估 D，所以我们可以尝试一下，看看是否出现了一种模式：
- D(2·0 + 1) = 1 = 30
- D(2·1 + 1) = 3 = 31
- D(2·2 + 1) = 9 = 32
- D(2·3 + 1) = 27 = 33
这里的模式是D(2n+1) = 3n。嘿，这是个好消息！这意味着我们有一种直接计算 D(2n+1) 的方法。
考虑到这一点，请注意 E(n) 定义为
- E(2) = 1 = D(1)
- E(n+2) = 2D(n+1) - E(n) + 2
请记住，我们知道 D(n+1) 的确切值，这将使我们的生活变得更加轻松。让我们看看如果我们对这个重复进行一点迭代会发生什么。例如，请注意
E(8)
= 2D(7) - E(6) + 2
= 2D(7) + 2 - (2D(5) - E(4) + 2)
= 2D(7) - 2D(5) + E(4)
= 2D(7) - 2D(5) + (2D(3) - E(2) + 2)
= 2D(7) - 2D(5) + 2D(3) + 2 - D(1)
= 2D(7) - 2D(5) + 2D(3) - D(1) + 2
好吧...这真的非常有趣。似乎我们得到了 D 递归的交替求和，其中我们在包含和排除 2 之间交替。在这一点上，如果我不得不猜测，我会说解决这个递归的方法是考虑将偶数情况进一步细分为输入为 2n 表示偶数 n 和 2n 表示奇数 n 的情况。事实上，请注意，如果输入为 2n 对应偶数 n，则末尾不会有 +2 项（所有 +2 都被 -2 平衡），而如果输入为奇数，则会有最后是+2项（所有+2都被-2平衡）。
现在，让我们转向问题的另一个方面。您没有被要求查询重复的个别条款。您被要求查询在一系列输入中评估的重复总和。事实上，我们在这里得到 D 项的交替和和差，这真的非常有趣。例如，f(10) + f(11) + f(12) 是多少？嗯，我们知道 f(11) = D(11)，我们可以直接计算。我们也知道 f(10) 和 f(12) 是 E(10) 和 E(12)。看看如果我们计算 E(10) + E(12):
会发生什么
E(10) + E(12)
= (D(9) - D(7) + D(5) - D(3) + D(1) + 2) + (D(11) - D(9) + D(7) - D(5) + D(3) - D(1))
= D(11) + (D(9) - D(9)) + (D(7) - D(7)) + (D(5) - D(5)) + (D(3) - D(3)) + (D(1) - D(1)) + 2
= D(11) + 2.
现在这很有趣。请注意，除 D(11) 项和 +2 项外，所有项都已取消！更一般地说，这可能会让我们猜测存在一些关于如何简化 E(n+2) + E(n) 的规则。事实上，有。具体来说：
E(2n) + E(2n+2) = D(2n+1) + 2
这意味着如果我们对一个范围内的许多连续值求和，每对相邻的偶数项将立即简化为 D(2n+1) + 2 的形式。
这里还有一些工作要做。例如，您需要能够对大量 D(n) 项求和，并且需要考虑所有 +2 项的影响。我会把这些留给你去解决。
一个提示：要求您 return 的所有值都是 modulo 某个数字 P。这意味着值序列 0、D(1)、D(1) + D(3), D(1) + D(3) + D(5), D(1) + D(3) + D(5) + D(7), 等等最终必须再次达到 0 ( modP)。您既可以计算在这种情况发生之前必须发生多少项，也可以通过显式计算这些值来记下执行此操作时遇到的所有值。这将使您能够对连续的大量连续 D 项求和 - 您可以 mod 按周期长度计算项数，然后在 table 中查找残差和。 =13=]
希望对您有所帮助！
有人可以帮我解决这类问题吗？我应该遵循什么样的方法？
查看问题，因为你会被要求
- 多次评估复发
- 对于非常大的输入，
您可能需要
- 找到一个closed-form解决复发的方法，或者
- 找到一种方法来评估亚线性时间内递归的第 n 项。
现在的问题是如何做到这一点。我们来看看递归，它被定义为
- f(1) = f(2) = 1,
- f(n+2) = 3f(n) 如果 n 是奇数，并且
- f(n+2) = 2f(n+1) - f(n) + 2 如果 n 是偶数。
让我们从探索循环开始，看看是否出现任何模式。这里有一点很突出——这个循环的奇数项只依赖于循环中的其他奇数项。这意味着我们可以想象尝试将这种递归拆分为两个较小的递归：一个纯粹处理奇数项，一个纯粹处理偶数项。让 D(n) 是奇数项的序列，E(n) 是偶数项的序列。那么我们有
- D(1) = 1
- D(n+2) = 3D(n)
我们只需要在奇数上评估 D，所以我们可以尝试一下，看看是否出现了一种模式：
- D(2·0 + 1) = 1 = 30
- D(2·1 + 1) = 3 = 31
- D(2·2 + 1) = 9 = 32
- D(2·3 + 1) = 27 = 33
这里的模式是D(2n+1) = 3n。嘿，这是个好消息！这意味着我们有一种直接计算 D(2n+1) 的方法。
考虑到这一点，请注意 E(n) 定义为
- E(2) = 1 = D(1)
- E(n+2) = 2D(n+1) - E(n) + 2
请记住，我们知道 D(n+1) 的确切值，这将使我们的生活变得更加轻松。让我们看看如果我们对这个重复进行一点迭代会发生什么。例如，请注意
E(8)
= 2D(7) - E(6) + 2
= 2D(7) + 2 - (2D(5) - E(4) + 2)
= 2D(7) - 2D(5) + E(4)
= 2D(7) - 2D(5) + (2D(3) - E(2) + 2)
= 2D(7) - 2D(5) + 2D(3) + 2 - D(1)
= 2D(7) - 2D(5) + 2D(3) - D(1) + 2
好吧...这真的非常有趣。似乎我们得到了 D 递归的交替求和，其中我们在包含和排除 2 之间交替。在这一点上，如果我不得不猜测，我会说解决这个递归的方法是考虑将偶数情况进一步细分为输入为 2n 表示偶数 n 和 2n 表示奇数 n 的情况。事实上，请注意，如果输入为 2n 对应偶数 n，则末尾不会有 +2 项（所有 +2 都被 -2 平衡），而如果输入为奇数，则会有最后是+2项（所有+2都被-2平衡）。
现在，让我们转向问题的另一个方面。您没有被要求查询重复的个别条款。您被要求查询在一系列输入中评估的重复总和。事实上，我们在这里得到 D 项的交替和和差，这真的非常有趣。例如，f(10) + f(11) + f(12) 是多少？嗯，我们知道 f(11) = D(11)，我们可以直接计算。我们也知道 f(10) 和 f(12) 是 E(10) 和 E(12)。看看如果我们计算 E(10) + E(12):
会发生什么E(10) + E(12)
= (D(9) - D(7) + D(5) - D(3) + D(1) + 2) + (D(11) - D(9) + D(7) - D(5) + D(3) - D(1))
= D(11) + (D(9) - D(9)) + (D(7) - D(7)) + (D(5) - D(5)) + (D(3) - D(3)) + (D(1) - D(1)) + 2
= D(11) + 2.
现在这很有趣。请注意，除 D(11) 项和 +2 项外，所有项都已取消！更一般地说，这可能会让我们猜测存在一些关于如何简化 E(n+2) + E(n) 的规则。事实上，有。具体来说：
E(2n) + E(2n+2) = D(2n+1) + 2
这意味着如果我们对一个范围内的许多连续值求和，每对相邻的偶数项将立即简化为 D(2n+1) + 2 的形式。
这里还有一些工作要做。例如，您需要能够对大量 D(n) 项求和，并且需要考虑所有 +2 项的影响。我会把这些留给你去解决。
一个提示：要求您 return 的所有值都是 modulo 某个数字 P。这意味着值序列 0、D(1)、D(1) + D(3), D(1) + D(3) + D(5), D(1) + D(3) + D(5) + D(7), 等等最终必须再次达到 0 ( modP)。您既可以计算在这种情况发生之前必须发生多少项，也可以通过显式计算这些值来记下执行此操作时遇到的所有值。这将使您能够对连续的大量连续 D 项求和 - 您可以 mod 按周期长度计算项数，然后在 table 中查找残差和。 =13=]
希望对您有所帮助！