首页 > ACM题库 > HDU-杭电 > HDU 1021 Fibonacci Again-数论-[解题报告] C++
2013
11-26

HDU 1021 Fibonacci Again-数论-[解题报告] C++

Fibonacci Again

问题描述 :

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

输入:

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

输出:

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

Print the word "no" if not.

样例输入:

0
1
2
3
4
5

样例输出:

no
no
yes
no
no
no

 

 

解决本题的关键:通过公式条件:F(0)= 7, F(1) = 11,F(n) = F(n-1) + F(n-2) (n>=2). 找到规律。
由同余式的基本性质:
(1)自反性:a = a( mod m)。
以及同余式的四则运算法则:
(1)如果 a =b( mod m)且 c = d( mod m),则 a +c = (b + d)( mod m)。
可知,F(n) = F(n) ( mod m) = ( F(n-1) +F(n-2) )( mod m)。
 
根据题目已知条件:
Print the word”yes” if 3 divide evenly into F(n);Print the word”no” if not.
这里m取值为3,则可将公式条件演变为:
综上所述,可得到以下对应关系:F(0)= 1, F(1) = 2, F(n) = ( F(n-1) + F(n-2)  )( mod 3) (n>=2).
index  0  1  2  3  4  5  6  7  8  9  10  11  12  13
value  1  2  0  2  2  1  0  1  1  2   0   2   2  1
print  no no yes no  no no yes  no  no  no  yes  no  no  no
这样我们就得到了如下规律:从第2个开始每隔4个循环一次。

#include <stdio.h>

void main()
{
    int n;
    while(scanf("%d", &n) !=EOF)
    {
        if((n - 2) % 4) // 根据上述规律
           printf("no\n");
        else
           printf("yes\n");
    }
}

 

 

 

 

#include<stdio.h> 
#include<string.h> 
long long f[1000009]; 
int main() 
{ 
int n; 
int i=2; 
memset(f,0,sizeof(f)); 
f[0]=1; 
f[1]=2; 
for(i=2;i<=1000005;i++) 
{ 
f[i]=(f[i-1]+f[i-2])%3; 
} 
while(scanf("%d",&n)==1) 
{ 
if(f[n]==0) 
{ 
printf("yes\n"); 
} 
else printf("no\n"); 
} 
return 0; 
}

 

 

 

 

 


  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?