* 面试题17：打印从1到最大的n位数

题目：输入数字n，按照顺序打印出从1到最大的n位十进制数。比如n为3，打印出1
到999.

思路：
这道题看起来很简单，最容易想到的是先求出最大数，然后再逐次打印，但是注意这道题有一个很大的陷阱，就是当数字很大时，会超出整型或者长整型，所以考虑用字符串实现模拟加法，解决大数问题。可以用排列组合来思考这道题 ，如果将前面的0补齐，那么所有的数其实就是n个0-9的全排列。只是在打印时排在前面的0不打印出来。根据以上思路，可以用递归来实现。（具体思路待研究）
分析: 假设 n=2, 从高位开始遍历，高位设置为0，然后跳到低位，低位从0开始设置到9，低位满9，则高位加1，低位则又开始从0设置到9，一直重复下去，直到找到最大的n位数。（如下图）

遍历示意

代码实现：

class Solution:
    def Print1ToMaxOfNDigits(self,n):
        if n <= 0:
            return None
        number = ['0']*n
        self.Print1ToMaxOfNDigitsRecursively(number,n,0) #调用递归函数


    def Print1ToMaxOfNDigitsRecursively(self,number,length,index):
        #此处的number为一个str类型的数组，每个数组元素是一个0-9之间数字的字符串形式
        if index == length:
            self.PrintNumber(number)    #如果已经赋值到最后一位，则打印这个字符串
            return
        for i in range(0,10):  
            number[index] = str(i) #给对应位置赋值
            self.Print1ToMaxOfNDigitsRecursively(number,length,index+1) #递归给下一位赋值

    def PrintNumber(self,number):
        Isbegining = True
        
        for char in number:
            if Isbegining==True and char == '0': #符合人类的体验，首位0不显示
                continue
            else:
                Isbegining =False #如果不是首位0，改变标志位
            print(char,end='') #默认为打印结束符为换行，此时不需要回车，故结束符为空
        print('\t') # 等价于print(),即一个回车符换行

if __name__=="__main__":
    Solution().Print1ToMaxOfNDigits(3)

运行结果:

打印结果