1029. Rabbit

最新推荐文章于 2017-06-29 09:52:05 发布

chenhq1991

最新推荐文章于 2017-06-29 09:52:05 发布

阅读量1k

点赞数

分类专栏： Sicily 文章标签： string n2 存储

本文链接：https://blog.csdn.net/chenhq1991/article/details/7909344

版权

Sicily 专栏收录该内容

67 篇文章

订阅专栏

1.一个简单的递归求和即可

2.m = 1应该是特殊的情况

#include<iostream>
#include<string>
#include<vector>
using namespace std;

class BigNum
{
public:
	BigNum()
	{
		this->num = "0";
	}
	BigNum(string n)
	{
		this->num = n;
	}
	string getNum()
	{
		return this->num;
	}

	friend BigNum operator +(const BigNum &n1, const BigNum &n2)
	{
		string temp;//和的倒置
		int carry = 0;
		//计算结果
		for(int i = n1.num.length() - 1, j = n2.num.length() - 1; i >= 0 || j >= 0; i--, j--)
		{
			if(i >= 0 && j >= 0)//两者、进位之和
			{
				temp.push_back(((n1.num[i] - 48) + (n2.num[j] - 48) + carry) % 10 + 48);//存储结果
				if((n1.num[i] - 48) + (n2.num[j] - 48) + carry > 9)//有新的进位
				{
					carry = 1;//两个十进制之和的进位不会超过1
				}
				else//没有进位
				{
					carry = 0;
				}
			}
			else//某一个数的位数已经结束
			{
				if(i >= 0)
				{
					temp.push_back(((n1.num[i] - 48) + carry) % 10 + 48);
					if((n1.num[i] - 48) + carry > 9)
					{
						carry = 1;
					}
					else
					{
						carry = 0;
					}
				}
				else//j >= 0
				{
					temp.push_back(((n2.num[j] - 48) + carry) % 10 + 48);
					if((n2.num[j] - 48) + carry > 9)
					{
						carry = 1;
					}
					else
					{
						carry = 0;
					}
				}
			}
		}
		if(carry == 1)//最高进位
			temp.push_back('1');

		//获取正确的结果
		string rev;
		bool flag = true;//去除头部的0 
		for(int i = temp.length() - 1; i >= 0; i--)
		{
			if(temp[i] == '0' && flag)
			{
				continue;
			}
			else
				flag = false;

			rev.push_back(temp[i]);
		}

		//创建一个BigNum对象,并返回
		BigNum sum(rev);
		return sum;
	}

	friend ostream& operator<<(ostream& outs, const BigNum& n)
	{
		outs << n.num;
		
		return outs;
	}
private:
	string num;
	
};

int main()
{
	int m, d;
	vector<BigNum> rabbit;//rabbit[0]表示已经成年，rabbit[1]表示还有1个月才成年
	while(cin >> m >> d && m != 0)
	{
		rabbit.clear();
		BigNum first("1");//一开始有一对
		rabbit.push_back(first);
		for(int i = 1; i < m; i++)
		{
			BigNum temp;
			rabbit.push_back(temp);
		}

		for(int i = 0; i < d; i++)
		{
			if(m != 1)
			{
				BigNum temp = rabbit[0];//生育
				for(int j = 0; j < m - 1; j++)
				{
					if(j == 0)
					{
						rabbit[j] = rabbit[j] + rabbit[j + 1];
					}
					else
					{
						rabbit[j] = rabbit[j + 1];
					}
				}
				rabbit[m - 1] = temp;
			}
			else
			{
				rabbit[0] = rabbit[0] + rabbit[0];
			}
		}

		BigNum sum;
		for(int i = 0; i < m; i++)
		{
			sum = sum + rabbit[i];
		}

		cout << sum << endl;
	}
	return 0;
}