CPP大数运算

蜜蜂路线

题目背景

无

题目描述

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房 $m$ 开始爬到蜂房 $n$，$m<n$，有多少种爬行路线？（备注：题面有误，右上角应为 $n-1$）

输入格式

输入 $m,n$ 的值

输出格式

爬行有多少种路线

样例 #1

样例输入 #1

1 14

样例输出 #1

377

提示

对于100%的数据，$1 \le M,N\le 1000$

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to add two big numbers represented as vectors of digits.
vector<int> addBigNumbers(const vector<int>& num1, const vector<int>& num2) {
    vector<int> result;
    int carry = 0;
    auto it1 = num1.rbegin(), it2 = num2.rbegin();

    while (it1 != num1.rend() || it2 != num2.rend() || carry != 0) {
        int sum = carry;
        if (it1 != num1.rend()) sum += *it1++;
        if (it2 != num2.rend()) sum += *it2++;
        carry = sum / 10;
        result.push_back(sum % 10);
    }

    reverse(result.begin(), result.end());
    return result;
}

int main() {
    int n, m;
    cin >> m >> n;
    int num = n - m + 1;

    vector<vector<int>> a(1001);
    
    // Initialize the first three numbers in the sequence.
    a[0] = {1};
    a[1] = {1};
    a[2] = {1};

    for (int i = 3; i < 1001; ++i) {
        a[i] = addBigNumbers(a[i-2], a[i-1]);
    }

    // Print the number at position 'num'.
    for (int digit : a[num]) {
        cout << digit;
    }
    cout << endl;

    return 0;
}

---

思路与问题：

1. 这是斐波那契数列问题，需要关注n-m
2. 实际编程问题：斐波那契数列膨胀过快，需要用大数存储运算

cpp实现大数：

1. 用vector动态数组来存放长度无法确定的大数
2. 利用rend rbegin而非begin end迭代，即从低位向高位加，最后结果再reverse得到
3. 输出时，使用vector本身的迭代输出