du熊学斐波那契I-白红宇

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

1 1 2

1 1 8

1 4 8

Sample Output

Case #1: 1

Case #2: 3

Case #3: 9

Hint

对于第一、二组数据，串为112358134711235......

对于第三组数据，串为14591459145914......

不知道这代码好不好，但是这是我做出来的哦~~~~~~~~

1 #include
      
        2 #include
       
         3 using namespace std; 4  5 typedef struct node 6 { 7     int data; 8     struct node *next; 9 }SqStack;10 11 void Push(SqStack *&s,int a)12 {13     SqStack *p;14     p=(SqStack *)malloc(sizeof(SqStack));15     p->data=a;16     p->next=s->next;17     s->next=p;18 }19 void FBNQ(SqStack *&s,int a,int b,int n)20 {21     int sum;22     Push(s,a);23     n--;24     if(n==0)25         return;26     Push(s,b);27     n--;28     if(n==0)29         return;30     while(n!=0)31     {32     sum=s->next->data+s->next->next->data;33     if(sum>9)34     {35         Push(s,sum/10);36         n--;37         if(n==0)38             return;39     }40     Push(s,sum%10);41     n--;42     }43 }44 45 int main()46 {47     SqStack *s;48     int i,a,b,T;49     int n;50     s=(SqStack *)malloc(sizeof(SqStack));51     s->next=NULL;52     cin>>T;53     for(i=1;i<=T;i++)54     {55         cin>>a>>b>>n;56         FBNQ(s,a,b,n);57         cout<<"Case #"<
        <<": ";58         cout<
         
          next->data<

来自：

本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/archive/2012/12/13/2815718.html，如需转载请自行联系原作者