美文网首页
水题 | HDU 1021

水题 | HDU 1021

作者: 0与1的邂逅 | 来源:发表于2019-02-26 21:04 被阅读0次

Fibonacci Again

Problem Description
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).

Input
Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).

Output
Print the word "yes" if 3 divide evenly into F(n).
Print the word "no" if not.

Sample Input
0
1
2
3
4
5

Sample Output
no
no
yes
no
no
no

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1021

解题思路

首先,这是一道水题,直接根据递推式F(n) = F(n-1) + F(n-2) (n>=2),逐步递推算出各个F(n)的值,再判断即可。(因为n的值比较小,所以可以暴力过,但是当n的值更大时,极有可能TLE)

方法一:暴力递推
#include <stdio.h>
int f[1000010];

int main()
{
    int n;
    f[0]=1; f[1]=2;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=2;i<=n;i++)
        {
            f[i] = (f[i-1]+f[i-2])%3;
        }
        if(f[n]%3==0)printf("yes\n");
        else printf("no\n");
    }
    return 0;
}
方法二:矩阵快速幂

在学习了矩阵快速幂之后,当看到递推式F(n) = F(n-1) + F(n-2) (n>=2)时,我们就会自然联想到利用矩阵乘法,构造出矩阵幂次,利用矩阵快速幂进行计算。(没上注释,不懂的童鞋先学一下矩阵快速幂)

// 矩阵快速幂入门
// HDU 1021 
// 15MS 1384K 921B G++

#include<iostream>
#include<cstdio>
using namespace std;
long long mod=3;

struct Mat
{
    long long mat[2][2];
};

Mat multiply(Mat A,Mat B)
{
    Mat temp;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            temp.mat[i][j]=0;
            for(int k=0;k<2;k++)
            {
                temp.mat[i][j]=(temp.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
            }
        }
    }
    return temp;
}

Mat operator^(Mat A,int k)
{
    Mat base;
    base.mat[0][0]=base.mat[1][1]=1;
    base.mat[1][0]=base.mat[0][1]=0;
    while(k)
    {
        if(k&1)base=multiply(base,A);
        A=multiply(A,A);
        k=k>>1;
    }
    return base;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n<2)
        {
            printf("no\n");
        }
        else
        {
            Mat ans;
            ans.mat[1][1]=0;
            ans.mat[0][0]=ans.mat[0][1]=ans.mat[1][0]=1;
            ans=ans^(n-1);
            long long sum=ans.mat[0][0]*11+ans.mat[0][1]*7;
            if(sum%3==0)printf("yes\n");
            else printf("no\n");
        }
    }
}
方法三:找规律

这样我们就得到了如下规律:从第2个开始每隔4个循环一次,即(n%4)==2,输出yes。

// 找规律
// n%4==2 => yes 
//0MS 1376K 203B G++
#include <cstdio>
#include <iostream>
using namespace std;
int main() 
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n%4==2)puts("yes");
        else puts("no");
    }
    return 0;
}
方法四:找规律,循环节

在第三种方法的基础上,我又发现了另一种规律:

索引从 0~7 、 8~15 ……依次呈现“no、no、yes、no、no、no、yes、no”的结果,(索引即上图中的index,也就是n的值)而且我们发现当索引n mod 8的值等于2和6的时候,输出yes,其他输出no。

// 【循环节】【找规律】 
// 这个题的循环节是8,每8个循环一次
// n%8:0~7 
// 15MS 1376K 200B G++
#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    int n,ans;
    while(~scanf("%d",&n))
    {
        ans=n%8;
        if(ans==2 || ans==6)printf("yes\n");
        else printf("no\n");
    }
}

写在最后

参考资料:

虽然是水题,但是发散了思维,一题多解。

如有其他解法,欢迎指教。

相关文章

网友评论

      本文标题:水题 | HDU 1021

      本文链接:https://www.haomeiwen.com/subject/ilkbyqtx.html