首页 > 试题广场 >

NowCoder数列

[编程题]NowCoder数列

热度指数：13482 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

NowCoder最近在研究一个数列：
* F(0) = 7
* F(1) = 11
* F(n) = F(n-1) + F(n-2) (n≥2)
他称之为NowCoder数列。请你帮忙确认一下数列中第n个数是否是3的倍数。

输入描述:

输入包含多组数据。
每组数据包含一个整数n，(0≤n≤1000000)。

输出描述:

对应每一组输入有一行输出。
如果F(n)是3的倍数，则输出“Yes”；否则输出“No”。

示例1

输入

0<br/>1<br/>2<br/>3<br/>4<br/>5

输出

No<br/>No<br/>Yes<br/>No<br/>No<br/>No

算法知识视频讲解

推荐

菜鸟葫芦娃

题目中的公式为F(n)=F(n-1)+F(n-2)

模拟规律得:F(2)=F(1)+F(0)=11+7=18 可以整除

F(3)=F(2)+F(1)=18*1+11*1 不可以被整除

F(4)=F(3)+F(2)=18*2+11*1 不可以被整除

F(5)=F(4)+F(3)=18*3+11*2 不可以被整除

F(6)=F(5)+F(4)=18*5+11*3 可以整除

以此类推可以发现数列最终是求11出现的个数即只要11出现3倍的时候才能被整除，正好n=2,6,10,14......能被3整除即n%4==2的即可被3整除。

发现这样一个规律便之和n有关系了，代码如下：

import java.util.Scanner;
public class Main{
    /**
     * 通过上面的公式发现数列最终是求11出现的个数即只要11出现3倍的时候才能被整除，正好n=2,6,10,14......能被3整除
     * 即n%4==2的即可被3整除
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            System.out.printf("%s\n",( n % 4 == 2)?"Yes":"No");
        }
        in.close();
    }

编辑于 2016-03-04 11:45:07 回复(10)

我要过pat

F(0) : 7 即 : 3*2 +1

F(1) : 11 即: 3*3 +2

F(2): 18 即: 3*6 +0

F(3): 即: 3*9 +2

F(4): .........2

F(5): 1

F(6); 0

F(7): 1

F(8): 1

F(9): 2

F(10): 0

F(11); 2

....

由此得到的规律就是: F(n)是否能被3整除就是:F(n-1)和F(n-2) 对3取余后,即F(N-1)%3+F(N-2)%

同时: F(n)%3是周期函数,周期是8,同时在每个周期内,第一个(如:2,10....18,26),第四个(如:6,14,22,30...)F(n)%3为0

综上:(N-2)%4==0 的时候F(n)能被3整除;

发表于 2018-02-12 09:39:57 回复(0)

风月无涯

#include <iostream>
#include <stdio.h>
using namespace std;
int main() 
{
	int n;int a[8];
    a[0]=1;
    a[1]=2;
    for(int i=2;i<8;i++)
    {
        a[i]=(a[i-1]+a[i-2])%3;
    }
    while(scanf("%d",&n)!=EOF){
    	n=n%8;
    	if (a[n]==0) printf("Yes\n");
    	else printf("No\n");
	}
	return 0;
}

注意输入不要用Cin，否则无法结束，被判断超时。

发表于 2016-10-27 18:31:08 回复(1)

蓝天白云~

新人不懂就问，这种题是要全部读完数据再输出结果😣😣😣还是边读入边输出判断结果？

发表于 2019-04-08 17:04:08 回复(1)

flyfarmer

这道题在求解哪些F(n)包含3的倍数个11时，要用到斐波那契数列的性质，也就是f(4n)是3的倍数，我们在分析nowcoder的时候要发现nowcoder(3)开始包含11的个数符合斐波那契数列数列，故要求的是等于4n+2形式的序号

发表于 2017-05-15 23:49:04 回复(0)

C/C++

追风少年123

想问一问这个代码哪里错了，提示运行超时 ...超新手..不懂。。

#include <stdio.h>

int f(int x){

if(x==0||x==1){

return 7%3;

}

else{

int c;

int a,b;

a = 7;

b = 11;

while(x>=2){

c = a+b;

a=b;

b=c;

x--;

}

return (c%3);

}

int main(){

int input;

while (scanf("%d",&input)!=EOF){

if(f(input)==0){

printf("Yes\n");

}

else {

printf("No\n");

}

return 0;

}

想问一问这个代码哪里错了，提示运行超时 ...超新手..不懂。。

发表于 2017-04-19 13:36:27 回复(0)

书生牛犊

楼上诸君发现了以八为循环节的规律，我只好出奇招，观察上图可得if((n-2)%4==0)printf("Yes")

发表于 2016-01-03 17:01:19 回复(0)

ahac

#include <stdio.h>
#define MAXSIZE 1000000+1

int Arr[MAXSIZE];
int main()
{
    int f0=1;
    int f1=2;
    Arr[0]=0;
    Arr[1]=0;
    int i,n;
    for(i=2;i<=1000000;i++){
        int t=(f0+f1)%3;
        if(!t)
            Arr[i]=1;
        else
            Arr[i]=0;
        f0=f1;
        f1=t;
    }
    while(scanf("%d",&n)!=EOF){
        if(Arr[n])
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

发表于 2015-12-30 23:14:42 回复(2)

linjiexin

暴力解超市，需要找规律，题解楼上答组已经提供很多了，比如@葫芦娃之水娃 @啥这些同学的，我就贴下我自己的代码吧：

#include<stdio.h>

int main(void){

int input;

while(~scanf("%d", &input)) {

if(2 == input % 4){

printf("Yes\n");

}

else{

printf("No\n");

}

return 0;

}

编辑于 2016-05-02 11:45:11 回复(3)

C/C++

已注销

观察数列，不难发现规律，即：当n=i*4+2 （i=0,1,2,......）时，F(n)为3的倍数。

#include<iostream>
#include<stdio.h>
using namespace std;

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        if((n-2)%4==0)  
            cout<<"Yes"<<endl;
        else 
            cout<<"No"<<endl;
    }
    return 0;
}

发表于 2021-01-19 17:29:11 回复(0)

牛客792251278号

周期为8，暴力求解

#include<iostream>
(720)#include<cstdio>

using namespace std;

int nc[8]={0};

int main()
{
	int n;
	nc[0] = 1;
	nc[1] = 2;
	nc[3] = 2;
	nc[4] = 2;
	nc[5] = 1;
	nc[7] = 1; 
	while(scanf("%d", &n) != EOF)
	{
		n %= 8;
		if(nc[n] == 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}

发表于 2020-05-06 11:14:26 回复(0)

kestars

import java.util.*;

public class Main{

    public static void main(String[] args){
        int[] array=new int[10000002];
        array[0]=7;
        array[1]=11;
        for(int i=2;i<array.length;i++){
            array[i]=array[i-1]%3+array[i-2]%3;
        }

        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            if(array[n]%3==0){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
    }
}

发表于 2018-09-29 13:07:06 回复(0)

LuxSun


	为什么还说我内存超限？！什么鬼？ 



	importjava.util.Scanner;



	 



	publicclassMain {



	    publicstaticvoidmain(String[] args) {



	        Scanner in = newScanner(System.in);



	        while(in.hasNext()){



	            System.out.printf("%s\n",in.nextInt()%4==2?"Yes":"No");



	        }



	    }



	}

编辑于 2017-06-25 07:49:08 回复(0)

逆境重生

这些题也太难了

编辑于 2023-12-28 07:34:24 回复(0)

牛客330083250号

#include<stdio.h>
int main()
{
int i,n,a[1000000]={7,11};

for(i=2;i<=1000000;i++)
a[i]=a[i-1]+a[i-2];

while(scanf("%d",&n)!=EOF)
if((a[n]%3)==0)
printf("Yes\n");
else
printf("No\n");
return 0;

}

这样做为什么不行?

发表于 2021-08-19 17:01:29 回复(0)

C/C++

白白胖胖的白胖胖

#include <iostream>
using std::cout;
using std::endl;
 
int main()
{
    int n{};
    while (scanf("%d",&n)!=EOF)
    {
 
        if (n % 8 == 2 || n % 8 == 6)
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

后边的数都是前边的数相加得到的，最后要判断是不是3的倍数，那么每当数大于3的时候，把3减去就完了，那么整个序列就成了0 1 2的序列，那这中间很容易找出个循环1 2 0 2 2 1 0 1，实际上只有第三个和第七个是3的倍数了，直接n%8 == 2或6就完了。

发表于 2021-01-17 00:06:37 回复(1)

C/C++

阿Q想offer

如果采用递归的话，会超时

最终发现，只要是n%4==2就输出Yes，其他时候输出No

代码如下：

#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n%4==2)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

发表于 2020-08-13 10:58:54 回复(0)

kathria

#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
if(n<2){
printf("No\n");
}else{
if((n-2)%4==0){
printf("Yes\n");
}else{
printf("No\n");
}
}

}
return 0;
}

发表于 2020-03-10 09:33:51 回复(0)

Slashyouth

#include<iostream>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        //规律：0 1 2 3 4 5 6 7 8 9 10 数值n
        //规律：1 2 0 2 2 1 0 1 1 2 0 对3取余数后，8个一个规律组
        int m=n%8;
        if(m==2 || m==6 ) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        
    }
        return 0;
}

编辑于 2020-03-08 22:50:35 回复(0)

hestyle

i = 0 7 NO

i = 1 11 NO

i = 2 18 YES

i = 3 29 NO

i = 4 47 NO

i = 5 76 NO

i = 6 123 YES

i = 7 199 NO

i = 8 322 NO

i = 9 521 NO

i = 10 843 YES

i = 11 1364 NO

i = 12 2207 NO

i = 13 3571 NO

i = 14 5778 YES

i = 15 9349 NO

i = 16 15127 NO

i = 17 24476 NO

i = 18 39603 YES

i = 19 64079 NO

首先得出的结论是i是偶数(i % 2 == 0)，接着把i / 2，发现是1、3、5、7、9...，因此可得出i / 2的结果是奇数，最终优化为i % 4 == 2

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    int number = 0;
    //scanf返回值为正确输出数据的变量个数，当一个变量都没有
    //获取到数据时，此时返回-1
    while (scanf("%d", &number) != - 1) {
        //判断%4的结果==2
        if (number % 4 == 2) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

发表于 2020-03-02 08:49:13 回复(0)

C/C++

不偷不抢安度因_

#include <stdio.h>
#include <stdlib.h>
/*
#define MAX 100000

void NowCoder(int*, int);//大数相加

void reverse(int*);

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int data[MAX] = {0};
        NowCoder(data, n);
        int i = 0;
        int sum = 0;
        while(i < MAX)
        {
            sum += data[i];
            i++;
        }
        if(sum % 3)
            printf("No\n");
        else
            printf("Yes\n");
    }
}

void NowCoder(int digit[], int n)
{
    int temp[MAX] = {0};
    int count = 0;//进位
    int i, j;
    for(i = 0; i <= n; i++)
    {
        if(i == 0)
            digit[0] = 7;
        else if(i == 1)
        {
            temp[0] = 7;
            digit[0] = 1;
            digit[1] = 1;
        }
        else
        {
            for(j = 0; j < MAX; j++)
            {
                int t = digit[j];
                digit[j] = temp[j] + digit[j] + count;
                temp[j] = t;
                count = digit[j]/10;
                digit[j] = digit[j]%10;
            }
            if(count)
                digit[MAX-1] += count;
        }
    }
    reverse(digit);
}

void reverse(int digit[])
{
    int temp;
    for(int j = 0; j < MAX/2; j++)
    {
        temp = digit[MAX - 1 - j];
        digit[MAX - 1 - j] = digit[j];
        digit[j] = temp;
    }
}
*/
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        printf("%s\n", ((n-2)%4 ? "No" : "Yes"));
    }
}

因为它的n可以到1000000，我在codeblocks里调试的时候设置在1000000以内的数都可以输出正确的结果，但是只要在100000~1000000里的数都不能用大数相加的方法，因为设置的数组过大导致codeblocks卡死然后停止工作。而且即使用大数相加的方法只要输入大于10000的值也得等很长时间才能出来结果。所以估计这个题的本意就是找规律。

编辑于 2020-03-01 15:01:18 回复(0)