1029-rabbit.cpp

中大oj（Sicily）1029的题目。这道题目主要是看清递归关系式而编即可。注意处理精度。本程序利用四位进位处理精度。

// fatlin 2009-3-21
//1029 Ratbit
/*************************** Rabbit
Problem
	The rabbits have powerful reproduction ability. 
One pair of adult rabbits can give birth to one pair of kid rabbits every month. 
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 exactly 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 cases. 
In each test case, there is one line having two integers m(1<=m<=10), 
d(1<=d<=100), m is the number of months after which kid rabbits can 
become adult rabbits, and d is 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 must print the number of pairs of rabbits after d months, one integer per line. 

*/

/*
#include<iostream>
#include<fstream>
using namespace std;
#define DIGIT 30
#define MAX 101

int main()
{
	int m,d;
	int i,j;
	int carry;//进位
	int num[MAX][DIGIT]={0};
	int temp;
	ifstream in;
	ofstream out;
	in.open("in.txt");
	out.open("out.txt");

	in >>m >>d;
	while( m!=0 || d!=0 )
	{	
		for( i = 0; i<=m; i++ )
			num[i][0]= i+1;
		for( i = m+1; i<=d; i++ )
		{
		//	num[i]=num[i-1]+num[i-m];
			carry=0;
			for(j=0;j<DIGIT;j++)
			{
				temp=num[i-1][j]+num[i-m][j]+carry;
				num[i][j]=temp%10000;
				carry=temp/10000;				
			}
		}
		for( i=DIGIT-1; num[d][i]==0; i-- )
			;
		for(;i>=0;i--)
			out << num[d][i];
		out << endl;
		in >>m >>d;		
	}

	in.close();
	out.close();
	return 0;
}

*/

#include<iostream>
#include<stdio.h>
using namespace std;
#define DIGIT 30
#define MAX 101

int main()
{
	int m,d;
	int i,j;
	int carry;//进位
	int num[MAX][DIGIT]={0};
	int temp;
	

	cin >>m >>d;
	while( m!=0 || d!=0 )
	{	
		for( i = 0; i<=m; i++ )
			num[i][0]= i+1;
		for( i = m+1; i<=d; i++ )
		{
		//	num[i]=num[i-1]+num[i-m];
			carry=0;
			for(j=0;j<DIGIT;j++)
			{
				temp=num[i-1][j]+num[i-m][j]+carry;
				num[i][j]=temp%10000;
				carry=temp/10000;				
			}
		}
		for( i=DIGIT-1; num[d][i]==0; i-- )
			;
		printf("%d", num[d][i--]);
		for(;i>=0;i--)
		{
			printf("%04d",num[d][i]);
			/*cout << setfill('0');
			cout<< setw(4)<< num[d][i];*/
		}
		cout << endl;
		cin >>m >>d;		
	}
	return 0;
}