首页 > 代码库 > sicily-1029 Rabbit
sicily-1029 Rabbit
一． 题意(0.04s)
每一对成熟的兔子可以生一对兔子，兔子在m个月之后成熟，假设兔子都不会死，计算d个月后一共有多少只兔子。
二． 要高精度加法（用string）
三． 公式：ans[m] = ans[m - 1] + ans[m-M]。
这里M最大值只可能是10，所以开个最大存10个string的数组。把1到N分成数量的M的小组，重复使用数组里面的数据，节省空间。
四． 源代码
1 // 2 // main.cpp 3 // sicily-1029 4 // 5 // Created by ashley on 14-12-5. 6 // Copyright (c) 2014年 ashley. All rights reserved. 7 // 8 9 #include <iostream>10 #include <string>11 using namespace std;12 string ans[10];13 string clearZeros(string data)14 {15 if (data[0] == ‘0‘) {16 int key = (int) data.length() - 1;17 for (int i = 0; i < data.length(); i++) {18 if (data[i] != ‘0‘) {19 key = i;20 break;21 }22 }23 data.erase(0, key);24 }25 if (data =http://www.mamicode.com/= "") {26 data = http://www.mamicode.com/"0";27 }28 return data;29 }30 31 //对位操作32 void countPoint(string &operand1, string &operand2)33 {34 while (operand1.length() < operand2.length()) {35 operand1 = "0" + operand1;36 }37 while (operand1.length() > operand2.length()) {38 operand2 = "0" + operand2;39 }40 }41 42 string addition(string addent, string adder)43 {44 //先对位，在加数和被加数前面适当补0，使他们包含相同的位数45 countPoint(addent, adder);46 //前面再补一个0，确定和的最多位数47 addent = "0" + addent;48 adder = "0" + adder;49 //从低位开始，对应位相加，结果写进被加数中，如果有进位，直接给被加数前一位加150 for (int i = (int) addent.length() - 1; i > 0; i--) {51 addent[i] = addent[i] + adder[i] - 48;52 if (addent[i] > ‘9‘) {53 addent[i] = addent[i] - 10;54 addent[i - 1] = addent[i - 1] + 1;55 }56 }57 return clearZeros(addent);58 }59 60 int main(int argc, const char * argv[])61 {62 int month, deadline;63 while (cin >> month >> deadline) {64 if (month == 0 && deadline == 0) {65 break;66 }67 string increment;68 increment = "1";69 ans[0] = "1";70 for (int i = 1; i <= month - 1; i++) {71 ans[i] = addition(ans[i - 1], increment);72 }73 for (int i = month; i <= deadline; i++) {74 increment = ans[i % month];75 ans[i % month] = addition(ans[(i - 1) % month], increment);76 }77 cout << ans[deadline % month] << endl;78 }79 return 0;80 }
sicily-1029 Rabbit
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。