首页 > 试题广场 >

牛牛学数列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 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)

C++

神秘吐司

#include<iostream>;
#include<iomanip>;
#include<cmath>;
using namespace std;
int main()
{
int n;
cin >> n;
int an[21] = { 0,0,1,1 };
for (int i = 4; i <= 20; i++)
{
an[i] = an[i - 3] + 2 * (an[i - 2]) + an[i - 1];
if (n == i)
{
cout << an[i];
return 0;
}
}
cout << an[n];
return 0;
}

发表于 2025-08-02 16:32:46 回复(0)

C++

来吾告汝

没用数组和递归，单纯算值

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a = 0, b = 1, c = 1;
    if(n == 1){
        cout << "0";
        return 0;
    }
    if( n == 2 || n == 3){
        cout << "1";
        return 0;
    }
    int sum = 0;
    for(int i = 4; i <= n; ++i){
        sum = a + 2*b + c;
        a = b;
        b = c;
        c = sum;
    }
    cout << sum << endl;
}
// 64 位输出请用 printf("%lld")

发表于 2025-12-11 13:03:51 回复(1)

喜欢copy的张三

n = int(input())

a = []

a1 = 0

for i in range(n):

if i == 0:

a.append(0)

elif i >0 and i <= 2:

a.append(1)

else:

a.append(a[a1]+2*a[a1+1]+a[a1+2])

a1+=1

print(a[-1])

发表于 2025-05-27 11:49:51 回复(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)

Python3

意若久时天然呆

n=int(input())
p=1<=n<=20
a=[0]*(n+1)
a[1],a[2],a[3]=0,1,1
if p:
    for i in range(4,n+1):a[i]=a[i-3]+2*a[i-2]+a[i-1]
print(a[n])

发表于 2025-11-03 15:01:55 回复(0)

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)

Python3

爱健身的牛油果很愤怒

n = int(input())

A = [0,0,1,1]

if 1<=n<=20:

for i in range(4,n+1):

nxt = A[i-3] +2*A[i-2] + A[i-1]

A.append(nxt)

print(A[n])

发表于今天 11:26:24 回复(0)

小二的酒

#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)

有担当的做题家在努力存钱

def select (n):

if n ==1 :

return 0

elif 1<n<4:

return 1

else:

return select(n-3)+2*select(n-2)+select(n-1)

n =int(input())

print(select(n))

发表于 2025-12-15 15:32:48 回复(0)

萱99

#include <stdio.h>

int xuan(int n){
 if (n==1) {
return 0;}
    else if (n==3||n==2) {
return 1;
    }
    else {
    return xuan(n-3)+2*xuan(n-2)+xuan(n-1);
    }
}
int main() {
        int n;
        scanf("%d",&n);
    printf("%d",xuan(n));
    return 0;
}

递归

发表于 2025-12-14 13:06:59 回复(0)

西王

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int *p =new int [n];

p[0] = 0;

p[1] = p[2] = 1;

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

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

}

cout << p[n-1];

}

发表于 2025-12-07 10:33:52 回复(0)

LiLvShai

#include <asm-generic/errno.h>
#include <iostream>
using namespace std;

int s(int a)
{
  if(a>3)
  {
    return s(a-3)+2*s(a-2)+s(a-1);
  }
  else
    if(a==1)
    {
      return 0;
    }
  else
  return 1;
}
int main() {
  int n;cin>>n;
  cout<<s(n);
}

发表于 2025-11-26 11:25:33 回复(0)

C++

TKFdz013

#include<iostream>

using namespace std;

int digui(int n){

if (n==1)

return 0;

if (n==2||n==3)

return 1;

else

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

}

int main(){

int n;

cin>>n;

int a[n];

a[1] = 0;

a[2] = 1;

a[3] = 1;

if(n>=4)

a[n] = digui(n);

cout<<a[n];

}

发表于 2025-11-16 00:07:58 回复(0)

北辰007

#include <stdio.h>

int print(int a){

if (a == 1) return 0;

else if(a == 2 || a == 3) return 1;

else return (print(a - 3) + 2 * print(a - 2) + print(a - 1));

}

int main() {

int a;

scanf("%d",&a);

int ret = print(a);

printf("%d",ret);

return 0;

}

发表于 2025-11-15 18:40:08 回复(0)

牛客685467045号

n = int(input())

lists = []

for i in range(1,n+1):

if i == 1:

lists.append(0)

elif i == 2 or i == 3:

lists.append(1)

else:

s = lists[i-4]+2*lists[i-3]+lists[i-2]

lists.append(s)

print(lists[n-1])

发表于 2025-11-12 16:37:17 回复(0)

JavaScript Node

牛客226490751号

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

void (async function () {

// Write your code here

while ((m = await readline())) {

const sumTarget = (line) => {

if (line < 1) return;

if (line == 1) {

return 0;

} else if (line <= 3) {

return 1;

} else {

return sumTarget(line-3) + 2 * sumTarget(line-2) + sumTarget(line-1);

}

};

console.log(sumTarget(m))

}

})();

发表于 2025-11-11 17:15:31 回复(0)

Java

英俊的比尔刷牛客

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(A(n));
    }
    public static int A(int m){
        if(m==1){
            return 0;
        }
        else if(m==2||m==3){
            return 1;
        }
        else{
            return A(m-3)+2*A(m-2)+A(m-1);}
    }
}

发表于 2025-11-11 12:45:36 回复(0)

先来刷题的

n = int(input())
a,b,c = 0,1,1
for i in range(n-3):
    a,b,c = b,c,c+2*b+a
print(a if n==1 else c)

发表于 2025-11-10 10:09:48 回复(0)

C++

牛客186712590号

#include <iostream>

using namespace std;

int A(int n){

if(n==1)return 0;

else if(n==2||n==3)return 1;

else return A(n-3)+2*A(n-2)+A(n-1);

}

int main() {

int n;

cin>>n;

cout<<A(n);

}

发表于 2025-11-06 23:41:50 回复(0)

提交观点

问题信息

语言题过关题目

上传者：牛客301599号

难度：

50条回答 117收藏 912浏览

牛牛学数列6

输入描述:

输出描述:

输入

输出

说明

递归写法-裸递归

递归写法-含有备忘录

非递归写法-迭代

问题信息

热门推荐

相关试题