题目的主要信息：

将输入的整数转为英文读法的字符串，数组不超过13位
在英语读法中三位数字看成一整体，后面再加一个计数单位，本题中可能会加billion 、million、thousand
百位的hundred也需要加上，百位数和十位数之间要加and，如果百位为0则不加
结果返回全部小写

方法一：迭代

具体做法：

我们根据上述三个数字为一组，用除法取余的方式取出十亿位的三位数、百万位的三位数、千位的三位数、最后百十个的三位数。

对于这四个三位数，我们依次比较，从十亿位开始。对于每个三位数，如果不为0则要准备输出，后面要加上相应的计量单位，如果它的前面输出更高位的数还要在这个输出前添加空格隔开。

对于输出函数，其实都是一样的，在后面接计量单位的情况下，都是直接输出百、十、个三位数。首先检查这个数是否大于等于100，不超过100的不需要输出百位，否则要输出百位加上" hundred"，然后输出十位和个位，我们采用字符串查表的方式，1到19直接查表，20到99采用十位加上个位的方式，整十单独讨论。同时输出十位个位之前要查看百位是否有输出，如果有则前面还需要添加" and ".

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

void print(int x){ //打印三位数字（百 十 个）
    string num1[] = { "", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nighteen"};
    string num2[] = { "", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };
    bool flag = false;
    if(x >= 100){ //大于100要打印百位
        cout << num1[x / 100] << " hundred"; //打印百位数字
        flag = true;
    }
    x %= 100; //去掉百位
    if(x >= 20){ //大于20要分十位和个位
        if(flag) //百位有数字要加and
            cout << " and ";
        cout << num2[x / 10]; //十位
        x %= 10;   
        if(x) //个位
            cout << " " <<num1[x];
    }else if(x > 0){ //小于20直接打印
        if(flag) //百位有数字要加and
            cout << " and ";
        cout << num1[x];
    }
}

int main(){
    long long n;
    while(cin >> n){
        vector<int> num(4, 0); 
        num[0] = n / (1000 * 1000 * 1000); //十亿位前的数字 
        num[1] = (n / (1000 * 1000)) % 1000; //百万位前的数字
        num[2] = (n / 1000) % 1000; //千位前的数字
        num[3] = n % 1000; //百十个位
        bool flag = false;
        if(num[0] != 0){ //如果十亿位不为0
            print(num[0]); //输出这个数字
            cout << " billion"; //后加billion
            flag = true;
        }
        if(num[1] != 0){ //如果百万位不为0
            if(flag) //先检查它前面有没有数字
                cout << " ";
            print(num[1]); //输出
            cout << " million"; //后加million
            flag = true;
        }
        if(num[2] != 0){ //如果千位不为0
            if(flag) //先检查它前面有没有数字
                cout << " ";
            print(num[2]); //输出
            cout << " thousand"; //后加thousand
            flag = true;
        }
        if(num[3] != 0){ //如果百十个位不为0
            if(flag) //先检查它前面有没有数字
                cout << " ";
            print(num[3]); //输出
        }
        cout << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (1)$ ，不超过13位的数字，都是常数时间
空间复杂度： $O (1)$ ，常数空间

方法二：递归

具体做法：

方法一我们也发现了，除了输出计量单位不同以外，计量单位之前的三位数我们都是复用同一个函数，因此我们可以递归地将数字缩小，每次输出三位数，同时加上计量单位。

当然，百位输出判断起来很麻烦，我们可以把百位也加入递归的过程，只判断直接输出个位和十位，也是查表的方式。

alt

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

string num1[] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
string num2[] = { "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nighteen" };
string num3[] = { "zero", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };
string num4[] = { "hundred", "thousand", "million", "billion" };
long long num5[] = {100, 1000, 1000000, 1000000000, 1000000000000};

string toEnglish(long long n){ //递归函数
    if(n >= 0 && n<= 9) //个位数字直接输出
        return num1[n];
    if(n >= 10 && n < 19) //10-19
        return num2[n % 10]; 
    if(n >= 20 && n < 100) //20-99
        return num3[n / 10] + (n % 10 == 0 ? "" : " " + num1[n % 10]); //注意避开整十
    for(int i = 0; i < 4; i++){
        if(n < num5[i + 1]) //找到该数字在哪两个基数之间
            return toEnglish(n / num5[i]) + " " + num4[i] + (n % num5[i] ? (i ? " " : " and ") + toEnglish(n % num5[i]) : "");
    }
    return "";
}

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

复杂度分析：

时间复杂度： $O (1)$ ，最大不超过13位数，常数时间
空间复杂度： $O (1)$ ，递归栈也是常数空间

题解 | #学英语#

题目的主要信息：

方法一：迭代

方法二：递归