百度之星2012年12月

第一题：

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