题目的主要信息：

此题要求将数字转换成英文，具体规则如下:

• 从最右边往左数，三位数字作为一个单位，例如12,345等。
• 每三位数后记得带上计数单位，分别是thousand, million, billion。
• 公式：百万以下千以上的数 X thousand X, 10亿以下百万以上的数：X million X thousand X, 10 亿以上的数：X billion X million X thousand X. 每个X分别代表三位数或两位数或一位数。
• 百位数和十位数之间要加and。

方法一：

采用递归。用itoe函数实现递归。ones中储存了个位数的英文，tens储存了10-19对应的英文，twenties中储存了10的倍数的英文，ihundreds用来划分数字的范围，hundreds中储存了百、千、百万、十亿对应的英文。

首先判断数字的范围，如果数字属于0-9，则直接输出；如果数字属于10-19，也可以直接输出；如果数字属于20-99，则需要将十位和个位数字单独输出。如果数字大于等于100，首先确定数字的范围，如果数字n的范围是ihundreds[i]-ihundreds[i+1]之间，则递归处理n/ihundreds[i]和n%ihundreds[i]的部分，将两部分拼起来。整个过程中需要注意百位数和十位数之间要加and。

具体做法：

#include <iostream>
#include <string>

using namespace std;

const string ones[] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
const string tens[] = { "ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen" };
const string twenties[] = { "zero","ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety" };
const int ihundreds[] = { (int)1e2, (int)1e3, (int)1e6, (int)1e9, (int)1e12 };
const string hundreds[] = { "hundred", "thousand", "million", "billion" };

string itoe(long long n){
    if (0<=n && n<=9){//个位数，直接输出
        return ones[n];
    }
    if (10<=n && n<20){//十位数，直接输出
        return tens[n%10];
    }
    if (20<=n && n<1e2){//20-100
        return twenties[n/10] + (n%10 ? " " + ones[n%10] : "");
    }
    for (int i=0; i < 4; i++){//大于100
        if (n < ihundreds[i+1]) {//确定范围
            return itoe(n/ihundreds[i]) + " " + hundreds[i] + (n%ihundreds[i] ? (i ? " ": " and ") + itoe(n%ihundreds[i]) : "");//递归转换
        }
    }
    return "";
}

int main(){
    long long n;
    while (cin>>n){
        cout<<itoe(n)<<endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，数字小于2000000，递归只需常数时间。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

模拟法。根据题目的信息模拟整个过程，根据题目意思，我们从低位开始，每三位为一个单位单独考虑，然后把所有单位拼起来就是最终结果。需要注意的是在划分过程中，可能会遇到最后不足三位的情况，因此我们在处理每个单位时需要判断长度，如果是三位，则从百位开始，如果是两，从十位开始，如果是一位，直接在num1中找到对应的英文。

具体做法：

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

using namespace std;

const vector<string> num1 = {"", "thousand", "million", "billion"};
const vector<string> num2 = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
const vector<string> num3 = {"", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
const vector<string> num4 = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};

int main(){
    long n;
    while(cin >> n){
        vector<string> res;
        string s = to_string(n);
        vector<string> v;
        int i = s.size() - 1;//此时i指向数字的最低位
        while(i >= 0){//从低位开始每三位划分
            int j = i;
            while(j > 0 && i - j < 2) j--;
            v.push_back(s.substr(j, i - j + 1));
            i = j - 1;
        }
        reverse(v.begin(), v.end());
        for(int i = 0; i < v.size(); ++i){
            if(v[i].size() == 3){//三位数字
                if(v[i][0] - '0' != 0){//最高位不为0时，需要跟上百
                    res.push_back(num2[v[i][0] - '0']);
                    res.push_back("hundred");
                    if(v[i][1] - '0' != 0 || v[i][2] - '0' != 0){
                        res.push_back("and");//个位或十位不为零食，需要and
                    }
                }
                if(v[i][1] - '0' == 1){//处理10-19
                    res.push_back(num4[v[i][2] - '0']);
                }else {//处理20-99
                    res.push_back(num3[v[i][1] - '0']);
                    res.push_back(num2[v[i][2] - '0']);
                }
            }else if(v[i].size() == 2){//两位数字
                if(v[i][0] - '0' == 1){//10-19
                    res.push_back(num4[v[i][1] - '0']);
                }
                else {//20-99
                    res.push_back(num3[v[i][0] - '0']);
                    res.push_back(num2[v[i][1] - '0']);
                }
            }else{//只有一位数字，直接在num2中对应英文，0-9
                res.push_back(num2[v[i][0] - '0']);
            }
            res.push_back(num1[v.size() - i - 1]);//确定每三位的单位
        }
        for(auto it : res){//输出最后结果
            if(it != "")
            cout << it << ' ';
        }
        cout << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，迭代只需常数时间。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。