C++ 中的 Geek-onacci 数

Geek-onacci 数 是斐波那契数列的一个变体，通常作为一个编程挑战引入。在这个数列中，前三项是给定的，后续的每一项都是由前三项之和计算得出的。它允许探索递归、迭代和动态规划的概念。

说明

初始项： Geek-onacci 数列的前三个数字是明确给出的，通常作为输入。我们称它们为 G1、G2 和 G3。

递推关系： 对于数列中任何一个大于 3 的数 Gn，它的计算方法是：

• G(n)=G(n−1)+G(n−2)+G(n−3)

这意味着每一项都是其前面三项的总和。

示例： 假设前三项是

• G1=1
• G2=2
• G3=3

那么数列将是：

• G4=G3+G2+G1=3+2+1=6
• G5=G4+G3+G2=6+3+2=11
• G6=G5+G4+G3=11+6+3=20

方法 1：简单方法

程序

输出

Enter G1, G2, G3: 1 2 3 
Enter the value of N: 5
The 5th Geek-onacci number is: 11   

说明

1. 代码目的

• 代码的目的是计算数列中特定位置 N 的 Geek-onacci 数。Geek-onacci 数列是斐波那契数列的一个变体，其中每个数字都是前三个数字的总和。

2. 输入说明

程序接受四个输入：

• 数列的前三项：G1、G2 和 G3。
• 我们想找到 Geek-onacci 数的位置 N。

3. 先处理简单情况

程序检查 N 是否为 1、2 或 3。

• 如果 N=1，则结果是 G1（第一项）。
• 如果 N=2，则结果是 G2（第二项）。
• 如果 N=3，则结果是 G3（第三项）。

这是因为这些项已经作为输入提供，无需计算。

4. N>3 的迭代计算

如果 N 大于 3，程序将使用一个循环来计算从第 4 位到 N 位的所有项。

循环中的步骤：

初始化前三项

• 程序使用变量 term1、term2 和 term3 来跟踪最后三项，它们最初设置为 G1、G2 和 G3。

计算下一项

• 对于每个位置 i（从 4 开始），数列中的下一项计算如下：
• current=term1+term2+term3
• 这会将最后三项相加得到下一项。

移位项

计算出新项后，程序会更新最后三项的值：

• term1 被 term2 替换。
• term2 被 term3 替换。
• term3 被 current（新计算出的项）替换。
• 这确保程序始终拥有最新三项以供下次计算。

重复直到 N

• 循环将继续，直到计算出位置 N 的项。

输出结果

循环结束后，term3 的值将包含位置 N 的 Geek-onacci 数。然后程序将打印此结果。

6. 示例演练

让我们举一个例子：G1=1、G2=2、G3=3，N=6。

初始项：term1 = 1, term2 = 2, term3 = 3。

从 i=4 开始循环。

步骤 1： current=1+2+3=6

• 更新：term1 = 2, term2 = 3, term3 = 6。

步骤 2： current=2+3+6=11

• 更新：term1 = 3, term2 = 6, term3 = 11。

步骤 3： current=3+6+11=20

• 更新：term1 = 6, term2 = 11, term3 = 20。

循环结束后，term3 = 20 是位置 N=6 的 Geek-onacci 数。

复杂度分析

时间复杂度

该程序的时间复杂度为 O(N)。

• 该程序从位置 4 迭代到 N，一次计算一个项。
• 每次迭代都涉及恒定的工作量（简单的三个数字相加和变量更新）。
• 因此，操作次数与 N 成正比。

空间复杂度

该程序的空间复杂度为 O(1)。

• 该程序仅使用固定数量的变量（term1、term2、term3 和 current）来计算 Geek-onacci 数。
• 它不需要像数组或递归栈那样的额外空间。
• 无论 N 的值是多少，空间使用量都保持不变。

方法 2：使用滑动窗口技术的动态规划

此方法将最后三项存储在一个数组中，并进行迭代更新。虽然与前一种方法类似，但它以不同的方式构建计算，以提高清晰度和模块化。

程序

输出

Enter G1, G2, G3: 1 2 3
Enter the value of N: 6
The 6th Geek-onacci number is: 20   

说明

1. 代码目的

该程序计算位置 N 的 Geek-onacci 数。Geek-onacci 数列类似于斐波那契数列，但它使用最后三个数字的总和来计算下一个数字。

2. 程序输入

程序会询问四个输入：

• G1：数列的第一项。
• G2：数列的第二项。
• G3：数列的第三项。
• N：需要 Geek-onacci 数的位置。

3. 先处理简单情况

如果 N 是 1、2 或 3，则答案直接是初始项之一。

• 如果 N=1，结果是 G1。
• 如果 N=2，结果是 G2。
• 如果 N=3，结果是 G3。

程序会直接返回这些值，而无需进行任何进一步计算，因为这些项已提供。

4. 使用数组存储项

对于大于 3 的位置，程序使用一个名为 terms 的大小为 3 的数组。

• 此数组存储数列的最后三项。
• 初始时，它设置为：
• terms[0] = G1
• terms[1] = G2
• terms[2] = G3

5. 循环计算项

程序使用循环计算从 4 到 N 的所有项。

1. 计算下一项
   • 数列中的下一项是数组中三个数字的总和：current=terms[0]+terms[1]+terms[2]
2. 移动数组值
   • 数组会更新以包含新项。
   • terms[0]（最旧的项）被 terms[1] 替换。
   • terms[1]（中间项）被 terms[2] 替换。
   • terms[2]（最新的项）被 current 替换。
   • 此过程确保数组始终包含最新三项。
3. 重复直到 N
   • 循环将继续，直到程序计算出位置 N 的 Geek-onacci 数。

6. 返回结果

• 循环结束后，terms[2] 的值将包含位置 N 的 Geek-onacci 数。然后将此值作为结果打印出来。

7. 示例演练

让我们举一个例子：

• G1=1、G2=2、G3=3，N=6。

初始状态

terms = [1, 2, 3]。

循环计算：

• 对于 i=4
• current=1+2+3=6。
• 更新 terms：[2, 3, 6]。
• 对于 i=5
• current=2+3+6=11。
• 更新 terms：[3, 6, 11]。
• 对于 i=6
• current=3+6+11=20。
• 更新 terms：[6, 11, 20]。

最终结果

• 循环结束后，terms[2] = 20，这是第 6 个 Geek-onacci 数。

复杂度分析

时间复杂度

• 该程序使用单个循环从第 4 位计算到第 N 位来计算 Geek-onacci 数。
• 每次迭代执行的常量工作量（相加三个数字和更新数组）。
• 因此，总操作次数与 N 成正比，时间复杂度为 O(N)。

空间复杂度

• 该程序使用固定大小（3 个元素）的数组来存储数列的最后三项。
• 无论 N 的大小如何，都不会使用额外的内存。
• 由于数组大小保持不变，空间复杂度为 O(1)，表示空间使用量恒定。