SequenceTime Limit:1 Sec Memory Limit:128 MBSubmissions:254 Solved:52DescriptionConsider the special sequence of numbers,which satisfies the following requirements:a[0] = 0; a[1] = 1; for every i = 1,2,3,...a[2*i] = a[i]; a[2*i+1] = a[i] + a[i+1]; Yo
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 14:11:19
SequenceTime Limit:1 Sec Memory Limit:128 MBSubmissions:254 Solved:52DescriptionConsider the special sequence of numbers,which satisfies the following requirements:a[0] = 0; a[1] = 1; for every i = 1,2,3,...a[2*i] = a[i]; a[2*i+1] = a[i] + a[i+1]; Yo
Sequence
Time Limit:1 Sec Memory Limit:128
MB
Submissions:254 Solved:52
Description
Consider the special sequence of numbers,which satisfies the following
requirements:
a[0] = 0;
a[1] = 1;
for every i = 1,2,3,...
a[2*i] = a[i];
a[2*i+1] = a[i] + a[i+1];
Your task is easy,
write a program which for a given value of N (0 < N < 1018)
finds the Nth number of the sequence.
Input
Only one number N.
Output
For every N in the input write the Nth number of the sequence.
Sample Input
0
1
2
Sample Output
0
1
1
SequenceTime Limit:1 Sec Memory Limit:128 MBSubmissions:254 Solved:52DescriptionConsider the special sequence of numbers,which satisfies the following requirements:a[0] = 0; a[1] = 1; for every i = 1,2,3,...a[2*i] = a[i]; a[2*i+1] = a[i] + a[i+1]; Yo
dingpwen程序的优化,如果他的程序能通过的话不这么做也无所谓.
#include <iostream>
using namespace std;
#define MAXN 1018
int main()
{
long a[MAXN];
int n;
//预处理
a[0] = 0;
a[1] = 1;
for(int i=2; i<MAXN; i+=2)
{
int k = i/2;
a[i] = a[k];
a[i+1] = a[k] + a[k+1];
}
while(cin>>n) cout<<a[n]<<endl;
return 0;
}