一. 题意(0.04s)
每一对成熟的兔子可以生一对兔子,兔子在m个月之后成熟,假设兔子都不会死,计算d个月后一共有多少只兔子。
二. 要高精度加法(用string)
三. 公式:ans[m] = ans[m - 1] + ans[m-M]。
这里M最大值只可能是10,所以开个最大存10个string的数组。把1到N分成数量的M的小组,重复使用数组里面的数据,节省空间。
四. 源代码
//
// main.cpp
// sicily-1029
//
// Created by ashley on 14-12-5.
// Copyright (c) 2014年 ashley. All rights reserved.
// #include <iostream>
#include <string>
using namespace std;
string ans[];
string clearZeros(string data)
{
if (data[] == '') {
int key = (int) data.length() - ;
for (int i = ; i < data.length(); i++) {
if (data[i] != '') {
key = i;
break;
}
}
data.erase(, key);
}
if (data == "") {
data = "";
}
return data;
} //对位操作
void countPoint(string &operand1, string &operand2)
{
while (operand1.length() < operand2.length()) {
operand1 = "" + operand1;
}
while (operand1.length() > operand2.length()) {
operand2 = "" + operand2;
}
} string addition(string addent, string adder)
{
//先对位,在加数和被加数前面适当补0,使他们包含相同的位数
countPoint(addent, adder);
//前面再补一个0,确定和的最多位数
addent = "" + addent;
adder = "" + adder;
//从低位开始,对应位相加,结果写进被加数中,如果有进位,直接给被加数前一位加1
for (int i = (int) addent.length() - ; i > ; i--) {
addent[i] = addent[i] + adder[i] - ;
if (addent[i] > '') {
addent[i] = addent[i] - ;
addent[i - ] = addent[i - ] + ;
}
}
return clearZeros(addent);
} int main(int argc, const char * argv[])
{
int month, deadline;
while (cin >> month >> deadline) {
if (month == && deadline == ) {
break;
}
string increment;
increment = "";
ans[] = "";
for (int i = ; i <= month - ; i++) {
ans[i] = addition(ans[i - ], increment);
}
for (int i = month; i <= deadline; i++) {
increment = ans[i % month];
ans[i % month] = addition(ans[(i - ) % month], increment);
}
cout << ans[deadline % month] << endl;
}
return ;
}