剑指offer_面试题12_打印1到最大的n位数（大数问题）

一时失言乱红尘 2022-08-03 13:46 140阅读 0赞

**题目：输入数字n，按顺序打印出从 1 最大的 n 位十进制数。**比如输入3，则打印出 1、2、3 一直到最大的三位数即 999。

由于题目中，没有说明n的大小，因此这是一个大数问题。

代码如下：

/*数值每次增 1，用一个量来保存，每次增 1，就返回打印*/
    /*算法主要分两块：数值增 1，以及 打印*/
    bool Increment_2(string &str)
    {
        if(str.empty())
            return false;
    
        for(int i = str.size() - 1; i >= 0; i--)
        {
            if(str[i] != '9')        /**每次加1，都是在最后位*/
            {
                str[i] += 1;         /**因为传递的是引用，所以原值同步改变*/
                break;               /**这里的 break 很重要，每次加1，都要跳出去输出*/
            }
    
            if(i == 0){
                return false;        /**代表已到最后一位，退出条件*/
            }else{
                str[i] = '0';        /**当这一位的9 再加1时，这一位变成0，并且，i--，相当于往前进位*/
            }
        }
        return true;
    }
    
    void Print_by_own(int n)
    {
        if(n < 0)
            return;
    
        string temp(n,'0');
    
        while(Increment_2(temp))
        {
            int pos = temp.find_first_not_of('0');     /**输出的时候要跳过前面的0位*/
            cout << temp.substr(pos) << '\t';          /**输出从第一个不是的0的字符到结尾的这段字符串*/
        }
        cout << endl;
    }
    
    int main()
    {
        int n = 3;
        Print_by_own(n);
        return 0;
    }

结果如下：

![20150808204007565][]

类似题：大数相加，实现任意两个非负数相加

算法如下：

#include <iostream>
    #include <string>
    #include <cstdlib>
    
    using namespace std;
    
    string Plus_of_two_big_int(string s1,string s2)
    {
        if(atoi(s1.c_str()) == 0 && atoi(s2.c_str()) == 0)   /**将 string 转换成 int 型，如果两者都是0，返回0*/
            return "0";
    
        string::size_type len1 = s1.size();
        string::size_type len2 = s2.size();
    
        if(len1 > len2)                                 /**两个字符串需要对齐，这一步很重要*/
            s2.insert(0, len1-len2,'0');
        else
            s1.insert(0, len2-len1,'0');
    
    
        string temp(len1+len2, '0');
    
        int i = s1.size()-1;                /**从最后一位开始相加*/
        int j = s2.size()-1;
        int k = temp.size() - 1;
        int t = 0;
    
        while(i >= 0 && j >= 0)
        {
            t = temp[k] - '0' + s1[i] - '0' + s2[j] - '0';
            if(t > 9)
            {
                temp[k] = t % 10 + '0';
                temp[k-1] = temp[k-1] - '0' + 1 + '0';       /**大于9需要进位*/
            }else{
                temp[k] = t + '0';
            }
            i--;
            j--;
            k--;
        }
    
        return temp;
    }
    
    int main()
    {
        string s1;
        string s2;
    
        cin >> s1 >> s2;
    
        string temp = Plus_of_two_big_int(s1,s2);
        if(temp == "0"){                            /**不要忘记非负数，包括0*/
            cout << 0 << endl;
        }else{
            int pos = temp.find_first_not_of('0');  /**找到第一个不为0的数的位置*/
            cout << temp.substr(pos) << endl;       /**从第一个不为0的位置处输出*/
        }
    
        return 0;
    }

/\*点滴积累，我的一小步O(∩\_∩)O~\*/

[20150808204007565]: /images/20220731/bbb06b4c33ba4a019993a2eaf030e693.png