题意：



方法一：
模拟


思路：
        首先，通过添加前缀0的方式将字符串长度凑成3的倍数；
        然后，循环遍历字符串，以3个为一组，进行计算；
        最后，输出答案。 



#include <bits/stdc++.h>

using namespace std;
string a[]={"billion","million","thousand"};
string b[]={"","one","two","three","four","five","six","seven","eight","nine"};//个位
string c[]={"ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen",
            "nineteen"};
string d[]={"","","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};
string s;

void f(int i){
    int flag=0;//标志位，判断是否加and
    if(s[i]>='1'){//百位
        flag=1;
        cout << b[s[i]-'0'] << " hundred ";
    }
    if(s[i+1]=='1'){//十分位
        if(flag)
            cout << "and ",flag=0;
        cout << c[s[i+2]-'0'] << " ";
        return;
    }else if(s[i+1]>='2'){
        if(flag)
            cout << "and ",flag=0;
        cout << d[s[i+1]-'0'] << " ";
    }
    
    if(s[i+2]>'0'){//个位
        if(flag)
            cout << "and ",flag=0;
        cout << b[s[i+2]-'0'] << " ";
    }
}
int main(){
   
    while(cin >> s){
        int len=s.size();//字符串长度
        int num=0;
        if(len%3)
            num=3-len%3;
        len+=num;
        while(num--){//加前缀0,将字符串长度凑成3的倍数
            s='0'+s;
        }
        int i=0;
        if(len>9){//十亿
            f(i);
            cout << "billion ";
            i+=3;
        }
        if(len>6){//百万
            f(i);
            cout << "million ";
            i+=3;
        }
        if(len>3){//千
            f(i);
            cout << "thousand ";
            i+=3;
        }
        f(i);
        cout << endl;
    }
    return 0;
}

时间复杂度：
空间复杂度：

方法二：
递归

思路：
      从输入数字的个位开始，从右到左每三个为一组。
      递归实现。
      最后后序遍历输出。
      

 
#include <bits/stdc++.h>

using namespace std;
string a[]={"","thousand","million","billion"};
string b[]={"","one","two","three","four","five","six","seven","eight","nine"};//个位
string c[]={"ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen",
            "nineteen"};
string d[]={"","","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};

void f(int x,int y){//递归
    if(x==0)
        return;
    f(x/1000,y+1);
    //后序遍历
    int flag=0;
    int u=x/100%10,v=x/10%10,w=x%10;//百分位、十分位、个位
    if(u){//百分位
        flag=1;
        cout << b[u] << " hundred ";
    }
    if(v==1){//十分位
        if(flag)
            cout << "and ",flag=0;
        cout << c[w] << " ";
        cout << a[y] << " ";
        return;
    }else if(v>1){
        if(flag)
            cout << "and ",flag=0;
        cout << d[v] << " ";
    }
    if(w){//个位
        if(flag)
            cout << "and ",flag=0;
        cout << b[w] << " ";
    }
    cout << a[y] << " ";//输出单位
}
int main(){
   int x;
    while(cin >> x){
        f(x,0);//递归
        cout << endl;
    }
    return 0;
}
时间复杂度：
空间复杂度：