首页 > ACM题库 > HDU-杭电 > HDU 1005 Number Sequence-递归和分治-[解题报告] C++
2013
11-26

HDU 1005 Number Sequence-递归和分治-[解题报告] C++

Number Sequence

问题描述 :

A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n – 1) + B * f(n – 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

输入:

The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

输出:

For each test case, print the value of f(n) on a single line.

样例输入:

1 1 3
1 2 10
0 0 0

样例输出:

2
5

注意此题直接递归会由于数据量很大TLE。

所以,这样的题目能优化的,存在循环,要找出循环的点。

f[i]=f[i-1]=0;

#include <stdio.h>
#include <string.h>
int s[50];
int main()
{
    int a,b,n,i;
    while(scanf("%d%d%d",&a,&b,&n),a || b || n)
    {
       int i;
       s[0]=s[1]=1;
       for(i = 2; i<50;i++)
       {
             s[i] = (a*s[i-1]+b*s[i-2])%7;
             if(s[i] ==1 && s[i-1] == 1)
             {break;}
                   
       }  
       n = n%(i-1);
       if(n == 0)
        printf("%d/n",s[i-2]);
        else
        printf("%d/n",s[n-1]);
                                        
    }    
    return 0;
}

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.