打印从1到n的最大n位数——面试题12《剑指offer 》

青旅半醒 2022-05-09 05:10 165阅读 0赞

> 题目：
> 
> 输入数字n，按顺序打印出从1到最大的n位十进制数。例如，输入3，则打印出1,2,3，到最大的三位数999。

C++代码实现：

void printNumber(int n) {
    	if (n < 0) return;
    
        //数组的初始化
    	char *number = new char[n + 1];    //创建一个n+1，多出来一个存储'\0'
    	memset(number, '0', n);            //每一位都设置为0
    	number[n] = '\0';
    
        //递增以及打印
    	while (!Increment(number)) {
    		printNumber(number);
    	}
    	delete[]number;    //释放内存空间
    }
    
    
    //数组高位为数值的个位
    //用于数值向上加,且number只保存当前一个数
    bool Increment（char *number）
    {
        //设置初始状态
        bool isOverFlow = false;    //最高位进位情况
        int carry = 0;              //每次计算的进位情况
        int len =strlen(number);    //字符长度
        for(int i = len-1;i>=0;i--)
        {
            int temp_num = number[i] - '0' + carry;    //字符转换为数值
            if(i==len-1)        //个位加
                temp_num++;        
            if(temp_num >= 10)
            {
                if(i == 0)    //最高为产生进位
                    isOverFlow = True;
                else          //不是最高位则处理数据
                {
                    carry = 1;
                    temp_num -= 10;
                    number = temp_num + '0'; 
                }
            }    
            else             //没有进位，则当前位加完之后退出即可
            {
                number =temp_num +'0';
                break;
            }
        }
        return isOverFlow;
    }
    
    
    //打印字符串,一个数
    void PrintNumber(char *number)
    {
        bool isBeginning0 = true;    //是否以零作为开头，默认为是
        int len = strlen(number)
        for(int i = 0; i<len-1; i++)
        {
            if(isBeginning0 && number[i] != '0')    //当不等于0时候
                isBeginning0 = false;    //置为0，为了输出
            if(!isBeginning0)
                cout << number[i];
        }
        cout <<"\t";    
    }

完整测试代码

#include<iostream>
     
    using namespace std;
    
    bool Increment(char* number) {
    	bool isOverflow = false;
    	int nTakeover = 0;
    	int nLength = strlen(number);
    	for (int i = nLength - 1; i >= 0; i--) {
    		int nSum = number[i] - '0' + nTakeover;
    		if (i == nLength - 1)
    			nSum++;
    		if (nSum >= 10) {
    			if (i == 0)
    				isOverflow = true;
    			else {
    				nSum -= 10;
    				nTakeover = 1;
    				number[i] = '0' + nSum;
    			}
    		}
    		else {
    			number[i] = '0' + nSum;
    			break;
    		}
    	}
    	return isOverflow;
    }
    
    void printNumber(char* number) {
    	bool isBeginning0 = true;
    	int nLength = strlen(number);
    	for (int i = 0; i < nLength; i++) {
    		if (isBeginning0 && number[i] != '0')
    			isBeginning0 = false;
    		if (!isBeginning0) {
    			printf("%c", number[i]);
    		}
    	}
    	printf("\t");
    
    }
    void printNumber(int n) {
    	if (n < 0) return;
    	char *number = new char[n + 1];
    	memset(number, '0', n);
    	number[n] = '\0';
    	while (!Increment(number)) {
    		printNumber(number);
    	}
    	delete[]number;
    }
    
    
    int main()
    {
    	int n;
    	cin >> n;
    	printNumber(n);
    
    	system("pause");
    	return 0;
    }