首页 > 试题广场 >

牛牛学数列6

[编程题]牛牛学数列6

热度指数：18244 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 定义数列 $\{A_n\}$ 如下：

$\displaystyle A_n= \begin{cases} 0,& n\in\{1\};\\ 1,& n\in\{2,3\};\\ \displaystyle A_n = A_{n-3} + 2A_{n-2} + A_{n-1},& n \geqq 4. \end{cases}$

$\hspace{15pt}$ 给定正整数 $n$ ，求 $A_n$ 的值。

输入描述:

在一行中输入一个整数 ，满足 。

输出描述:

输出一个整数，表示  的值。

示例1

输入

输出

说明

。

算法知识视频讲解

小二的酒

#include<stdio.h>

int func(int n)

{

if(n==1)

return 0;

if(n<=3)

return 1;

if(n>=4)

return func(n-3)+2*func(n-2)+func(n-1);

}

int main()

{

int num;

scanf("%d",&num);

printf("%d",func(num));

return 0;

}

有没有大佬帮我看看哪里有问题，硬是显示存在问题

发表于 2025-12-16 13:14:30 回复(0)

Neoxx

常规用数组解法

#include <stdio.h>

int main() {
    int a[20],n,i;
    scanf("%d",&n);
    a[0]=0;
    a[1]=a[2]=1;
    for(i=3;i<20;i++){
        a[i]=a[i-3]+2*a[i-2]+a[i-1];
    }
    
    printf("%d",a[n-1]);
    return 0;
}

发表于 2025-11-16 22:51:44 回复(0)

he余杭

#include <stdio.h>
int An(int n);
int main() 
{
    int n;
    scanf("%d",&n);
    printf("%d",An(n));
    return 0;
}
int An(int n)
{
    if(n==1)
        return 0;
        else if(n==2||n==3)
        return 1;
        else
         return An(n-3)+2*An(n-2)+An(n-1);
}

这种使用递归效率很高

发表于 2025-08-21 19:40:18 回复(1)

Omnitrix_t

递归写法-裸递归

裸递归写法是纯粹的递归写法，这种写法的时间复杂度呈指数级增长。

#include <stdio.h> 
int solution(int n)
{
    if (n < 4)
    {
         return n == 1 ? 0 : 1;
    }
   
    return solution(n - 3) + 2 * solution(n - 2) + solution(n - 1);
}
int main() {
   
    int n = 0;
    scanf("%d", &n);
    printf("%d", solution(n));
    return 0;
}

递归写法-含有备忘录

含有备忘录（散列表）的递归。
用定长数组 memo[] 实现缓存数组，键就是 n，查找/插入均为 O(1)。

#include <stdio.h>
#include <stdint.h>

#define MAX 20
#define INVALID -1

uint32_t memo[MAX + 1];

uint32_t solution(uint32_t n)
{
    if (n < 4)
    {
         return n == 1 ? 0 : 1;
    }

    if (memo[n] != INVALID)
    {
        return memo[n];         // 已经计算过，直接返回
    }

    memo[n] = solution(n - 3) + 2 * solution(n - 2) + solution(n - 1);

    return memo[n];
}
int main() {
    
    uint32_t n = 0;

    // 初始化备忘录
    for (int i = 0; i <= MAX; i++)
    {
        memo[i] = INVALID;
    }

    scanf("%u", &n);

    printf("%u", solution(n));

    return 0;
}

非递归写法-迭代

题目已说明这是数列题，那么可以用指针移动的思想进行迭代。

#include <stdio.h>
#include <stdint.h>

uint32_t solution(uint32_t n)
{
    if (n < 4)
    {
        return n == 1 ? 0 : 1;
    }

    int cur = 0;    // 当前计算出的 An 值
    int a1 = 0, a2 = 1, a3 = 1; // a1 到 a3 类比于指针，初始分别指向数列的前 3 项

    for (uint32_t i = 4; i <= n; i++)
    {
        // 计算出当前 An 的值，即 Ai 的值（当 n = i 时，An 的值）
        // 此时的 cur 表示着 a4 指针
        cur = a1 + 2 * a2 + a3;

        // 指针移动
        a1 = a2;
        a2 = a3;
        a3 = cur;
    }

    return cur;
}
int main() {
    
    uint32_t n = 0;

    scanf("%u", &n);

    printf("%u", solution(n));

    return 0;
}

发表于 2025-08-12 01:21:20 回复(0)

练习时长两年半的鸽子很有趣

#include <stdio.h>

int main() {

int a[20]={0, 1, 1};

int n=0, i=0, result=0;

scanf("%d", &n);

if(n!=1&&n!=2&&n!=3)

{

for(i=3;i<=n;i++)

{

a[i]=a[i-3]+2*a[i-2]+a[i-1];

}

printf("%d", a[n-1]);

return 0;

}

发表于 2025-07-03 22:50:44 回复(1)

提交观点

问题信息

语言题过关题目

上传者：牛客301599号

难度：

8条回答 117收藏 906浏览

牛牛学数列6

输入描述:

输出描述:

输入

输出

说明

递归写法-裸递归

递归写法-含有备忘录

非递归写法-迭代

问题信息

热门推荐

相关试题