输入数字n,按顺序打印出从1到最大的n位十进制数

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

跳进面试官的陷阱

1 void PrintfToMaxNDigits(int n)
2 {
3  int number=1;
4  int i=0;
5  while(i++<n)
6  number *=10;
7  for(i=1;i<number;i++)
8  printf("%d	",i);
9 }

这样初看起来没有什么问题,但是如果仔细分析这个问题就会发现"当n输入很大时"，数据就会发生溢出。

所以可以尝试通过字符串来模拟数字加法的解法,绕过陷阱才能拿到Offer

因此我们只需要做两件事情：

1,在字符串表达的数字上模拟加法；

2,把字符串表达式的数字打印出来；

基于上面的分析,我们可以写出如下代码:

 1 void Print1ToMaxNdigits(int n)
 2 {
 3  if(n<=0)
 4  return;
 5  char *number=new char[n+1];
 6  memset(number,'0',n);
 7  number[n]='';
 8  while(!Increment(number))
 9  { 
10   PrintfNumber(number);
11  }
12   delete []number;
13  }
14 
15 bool Increment(char* number)
16 {
17  bool isOverflow=false;
18  int nTakeOver=0;
19  int nLength=strlen(number);
20  for(int i=nLength-1;i>=0;i--)
21  {
22   int nSum=number[i]-'0'+nTakeOver;
23   if(i==nLength-1)
24   nSum++;
25   if(nSum>=10)
26   {
27    if(i==0)
28     isOverflow=true;
29    else
30    {
31     nSum -=10;
32     nTakeOver=1;
33     number[i]='0'+nSum;
34     }
35   }
36  else
37  {
38  number[i]='0'+nSum;
39  break;
40  }
41  }
42 return isOverflow;
43 }
44 
45 void PrintfNumber(char *number)
46 {
47  bool isBeginning0=true;
48  int nlength=strlen(number);
49  for(int i=0;i<nlength;++i)
50  {
51   if(isBeginning0&&number[i]!='0')
52   isBeginning0=false;
53   if(!isBeginning0)
54   {
55    printf("%c",number[i]);
56    }
57  }
58 printf("	");
59 }

把问题转换成数字排列的解法,递归让代码更简洁:

接下来我们换一种思路来考虑这个问题，如果我们在数字前面补0的话,就会把数字的每一位都从0~9排列一遍,就得到了所有的十进制数.只是我们在打印的时候,数字排在前面的0我们不打印出来罢了。全排列用递归很容易表达,数字的每一位都可能是0~9中的一个数,然后设置下一位,递归结束的条件是我们已经设置了数字的最后一位.

 1 void Print1ToMaxOfNDigitsRecursively(char* number,int length,int index)
 2 {
 3     if(index==length-1)
 4     {
 5         PrintNumber(number);
 6         return;
 7     }
 8     for(int i=0;i<10;++i)
 9     {
10         number[index+1]=i+'0';
11         Print1ToMaxOfNDigitsRecursively(number,length,index+1);
12     }
13 }
14 
15 void Print1ToMaxOfNDigits(int n)
16 {
17     if(n<=0)
18         return;
19     char* number=new char(n+1);
20     number[n]='';
21     for(int i=0;i<10;++i)
22     {
23         number[0]=i+'0';
24         Print1ToMaxOfNDigitsRecursively(number,n,0);
25     }
26     delete [] number;
27 }