题解 | #小红的数列#

题目链接

小红的数列

题目描述

给定一个数列 $a$ ，其定义如下：

$a_1 = 1$
$a_2 = 2$
对于 $i \ge 3$ ，数列满足递推关系： $a_i = a_{\lfloor i/3 \rfloor} + a_{\lfloor i \cdot 2/3 \rfloor}$

其中 $\lfloor x \rfloor$ 表示对 $x$ 向下取整。

现在给定一个正整数 $n$ ，要求输出该数列的前 $n$ 项。

解题思路

这是一个典型的动态规划（Dynamic Programming）或递推问题。我们需要计算数列的前 $n$ 项，而每一项的计算都依赖于数列中索引更小的项。

具体来说，要计算第 $i$ 项 $a_i$ ，我们需要知道 $a_{\lfloor i/3 \rfloor}$ 和 $a_{\lfloor i \cdot 2/3 \rfloor}$ 的值。

因为对于任何 $i \ge 3$ ，都有 $\lfloor i/3 \rfloor < i$ 和 $\lfloor i \cdot 2/3 \rfloor < i$ ，这意味着计算当前项所依赖的项都已经被计算出来了。

因此，我们可以采用自底向上的方法，顺序计算数列的每一项：

创建一个数组（例如 dp 或 a），大小为 $n+1$ ，用来存储数列的每一项。
根据题目定义，初始化前两项： $a[1] = 1$ 和 $a[2] = 2$ 。
从 $i = 3$ 开始，循环直到 $n$ 。在循环的每一步，我们都根据递推公式计算 $a[i]$ :

$a[i] = a[\lfloor i/3 \rfloor] + a[\lfloor i \cdot 2/3 \rfloor]$

在大多数编程语言中，正整数的除法 i / 3 和 i * 2 / 3 会自动执行向下取整的操作，所以我们可以直接使用 a[i/3] + a[i * 2 / 3]。
计算完所有项后，将数组中的 $a[1]$ 到 $a[n]$ 依次输出即可。

由于数列中的数值可能会增长，为了防止整数溢出，建议使用 64 位整型（如 C++ 中的 long long 或 Java 中的 long）来存储数列的值。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n <= 0) {
        return 0;
    }

    vector<long long> a(n + 1);

    if (n >= 1) {
        a[1] = 1;
    }
    if (n >= 2) {
        a[2] = 2;
    }

    for (int i = 3; i <= n; ++i) {
        a[i] = a[i / 3] + a[i * 2 / 3];
    }

    for (int i = 1; i <= n; ++i) {
        cout << a[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n <= 0) {
            return;
        }

        long[] a = new long[n + 1];

        if (n >= 1) {
            a[1] = 1;
        }
        if (n >= 2) {
            a[2] = 2;
        }

        for (int i = 3; i <= n; i++) {
            a[i] = a[i / 3] + a[(i * 2) / 3];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(a[i]);
            if (i < n) {
                sb.append(" ");
            }
        }
        System.out.println(sb.toString());
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline().strip()
        if not n_str:
            return
        n = int(n_str)
    except (IOError, ValueError):
        return

    if n <= 0:
        return

    a = [0] * (n + 1)

    if n >= 1:
        a[1] = 1
    if n >= 2:
        a[2] = 2

    for i in range(3, n + 1):
        a[i] = a[i // 3] + a[i * 2 // 3]

    print(*a[1:])

solve()

算法及复杂度

算法：动态规划 (递推)
时间复杂度： $O(N)$ 。我们需要一个循环来计算从 $a_3$ 到 $a_n$ 的所有项，循环次数为 $N-2$ 次，每次计算是常数时间。
空间复杂度： $O(N)$ 。我们需要一个大小为 $N+1$ 的数组来存储数列的项。