du熊学斐波那契I
Time Limit : 2000/1000ms (C/Other) Memory Limit : 65535/32768K (C/Other)
本次组委会推荐使用C、C++
Problem Description
du熊对数学一直都非常感兴趣。最近在学习斐波那契数列的它,向你展示了一个数字串,它称之为“斐波那契”串:
11235813471123581347112358……..
聪明的你当然一眼就看出了这个串是这么构造的:
1.先写下两位在0~9范围内的数字a, b,构成串ab;
2.取串最后的两位数字相加,将和写在串的最后面。
上面du熊向你展示的串就是取a = b = 1构造出来的串。
显然,步骤1之后不停地进行步骤2,数字串可以无限扩展。现在,du熊希望知道串的第n位是什么数字。
Input
输入数据的第一行为一个整数T(1 <= T <= 1000), 表示有T组测试数据;
每组测试数据为三个正整数a, b, n(0 <= a, b < 10, 0 < n <= 10^9)。
Output
对于每组测试数据,输出一行“Case #c: ans”(不包含引号)
c是测试数据的组数,从1开始。
Sample Input
3
1 1 2
1 1 8
1 4 8
Sample Output
Case #1: 1
Case #2: 3
Case #3: 9
Hint
对于第一、二组数据,串为112358134711235……
对于第三组数据,串为14591459145914……
自己的解题过程:
自己刚开始做的时候,将题意理解错了,以为是数字的斐波那契数列,然后将数字串变成字符串,计算第几个元素的值。
后来仔细一看,原来不是,而是字符串的斐波那契数列,也就是不可能超过两位。于是在前面的基础上做了一些改动,于是形成了下面的程序。
#include
#include
#include
using namespace std;
int main()
{
int count;
cin>>count;
string outchar;
for(int i =0;i>a>>b>>c;
string total;
char temp[9];
int pre1,pre2;
pre1=a;pre2=b;
char temp1[9],temp2[9];
sprintf(temp1,"%d",pre1);
sprintf(temp2,"%d",pre2);
total+=temp1;
total+=temp2;
for(int i = 2;i=10)
{
pre1 = tempnum/10;
pre2 = tempnum%10;
}
else
{
pre1=pre2;
pre2=tempnum;
}
}
outchar += total.c_str()[c-1];
}
for(int j = 0;j
由于忽略了时间的要求,所写 的程序只能运行在较小的输入规模上,当与别人讨论的时候,才意识到这一点。这也给自己以后写程序敲了一个警钟,以后不仅要注意程序如何实现,同时也应该注意算法的时间效率。
于是在别人的提醒下,重新开始写程序。
在原来的基础上进行了如下修改(添加注释的部分为新加部分)
#include
#include
#include
using namespace std;
int main()
{
int count;
cin>>count;
string outchar;
for(int i =0;i>a>>b>>c;
string total;
char temp[9];
int pre1,pre2;
pre1=a;pre2=b;
char temp1[9],temp2[9];
sprintf(temp1,"%d",pre1);
sprintf(temp2,"%d",pre2);
total+=temp1;
total+=temp2;
int countxun = 0;//统计循环节的大小
int isxun = 0;//标记是否大于循环节
for(int i = 2;i=10)
{
pre1 = tempnum/10;
pre2 = tempnum%10;
countxun+=2;//如果和为两位数,则循环节个数加2
}
else
{
pre1=pre2;
pre2=tempnum;
countxun +=1;//如果和为两位数,则循环节个数加1
}
if(pre1==a&&pre2==b)//如果遇到循环,则退出
{
isxun=1;
break;
}
}
int tempc = isxun?c%countxun:c;
if (tempc == 0)//说明是正好结束一个循环节,做特殊处理
tempc = countxun;
outchar += total.c_str()[tempc-1];
}
for(int j = 0;j
学习了
谢谢