howmanyrabbits.c

这是ACM国际大学生程序设计竞赛的一个参赛试题的解决算法。算法简单易懂。

//How many rabbits?
/*
Description 

The rabbits have powerful reproduction ability. One pair of adult rabbits can give birth to one of pair of kid rabbits every moth.And after m months,the kid rabbits can become adult rabbits. 
As we all know, when m=2,the sequence of the number of pairs of rabbits in each month is called Fibonacci sequence.But when m<>2, the problem seems not so simple. You job is to calculate after d months, how many pairs of the rabbits are there if there is excactly one pair of adult rabbits initially.You may assume that none of the rabbits dies in this period. 


Input 

The input may have multiple test case.In each test case,there is one line having two integers m(1<=m<=10) ,d(1<=d<=100), 
m is number of months after which kid rabbits can becomes adult rabbits, and d if the number of months after which you should calculate the number of pairs of rabbits.The input will be terminated by m=d=0.

Output 

You muxt print the number of pairs of rabbits after d months, one integer per line.

Sample Input 
2 3
3 5
0 0

Sample Output 
5 
9

*/


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int main()
{  
    int m,d,i,j,k,flag;
    int totalnumber1,temp[101][32];
    
    while(1)
    {   
         scanf("%d %d",&m,&d);      
         if ( m==0 && d==0 ) 
         {
             return 0;
         }        
         if (m>=1 && d>=1 &&  m<=10  &&  d<101 )
         {
              if(m>=d)
               {
                totalnumber1=d+1; 
                printf("%d",totalnumber1);
               }
              else  if(m<d)
               {  
                 for (i=0;i<32;i++) 
                  {
                     for(j=0;j<101 ;j++) 
                         temp[j][i]=0;
                   }
                  for(j=0;j<m;j++)
                  {
                       if(j<99)
                           {
                             temp[j][1]=(j+1)/10;
                             temp[j][0]=(j+1)%10;
                            };
                       if (j>=99 && j<999)
                           {
                           temp[j][2]=(j+1)/100;
                           temp[j][1]=(j+1)/10;
                           temp[j][1]=(j+1)%10;                           
                           temp[j][0]=(j+1)%100;
                            
                           };
                     }       
                  for(k=m;k<=d;k++)
                  {
                     flag=0;                     
                     for(i=0;i<32 ;i++)
                     {  
                        temp[k][i]=(temp[k-1][i]+temp[k-m][i]+flag);
                        flag=temp[k][i]/10;                        
                        temp[k][i]=temp[k][i]%10;
                     }
                  }
                  for (i=31;i>=0;i--)
                   {
                      if (temp[d][i]!=0)
                      { 
                         k=i; 
                         break;
                      }
                     
                   }
                   for (i=k;i>=0;i--)
                   {  printf("%d",temp[d][i]); }
                  } 
                  printf("\n"); 
               } 
         } 
}