题目：输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入数字 3，则打印出 1、2、3 ··· 999（因为最大的 3 为数即为 999）。
这个题目看似简单。最容易想到的办法就是先求出 n 位十进制数的最大值，然后利用for循环逐个打印出即可；
代码如下：
1 // Print1ToMaxOfNDigits.c 2 #include "stdio.h" 3 #include "stdlib.h" 4 5 void Print1ToMaxOfNDigits(int n) 6 { 7 int num = 1; 8 int i = 0; 9 while(i++ < n) 10 num *= 10; 11 12 for(i = 1; i < num; ++i) 13 printf("%d ", i); 14 printf(" "); 15 } 16 17 int main(int argc, char *argv[]) 18 { 19 int i; 20 while(printf("Please input a num: "), scanf("%d", &i)) 21 { 22 Print1ToMaxOfNDigits(i); 23 } 24 return 0; 25 }
如果仔细分析这个问题，我们可能就注意到这里并没有规定 n 的范围。因此当输入的 n 很大的时候，我们求最大的 n 位数无论是用 int 整型还是 long 长整形都会溢出。这里实际所描述的是大数问题。
解法：在字符串上模拟数字加法
1、由于数字最大是 n 位的，因此我们需要一个长度为 n+1 的字符串（最后一个为结束符‘ ’）
2、当实际数字不够 n 位的时候，在字符串的前半部分补 0 即可。打印时，需要绕过前面为 0 的位。
3、首先为我们所申请的 n+1 位字符初始化，皆为'0'。
4、然后我们只需要做两件事：
一是在字符串所表达的数字上模拟加法；
二是把字符串表达的数字打印出来。
基于上面的分析，我们可以写出如下代码：
1 void Print1ToMaxOfNDigits(int n) 2 { 3 if(n <= 0) 4 return; 5 6 char *result = new char[n+1]; 7 memset(result, '0', n); 8 result[n] = ' '; 9 10 while(!Increment(result)) // 完成+1，并判断是否溢出 11 { 12 PrintNumber(result); // 打印字符串 13 } 14 delete []result; 15 }
一、用字符串模拟数字加法
函数原型为：bool Increment(char *result)
在模拟加法时，我们要注意下面几点：
1、何时产生进位：当我们对最后一位字符进行加 1 操作，并且该字符大于 ‘10’的时候；
2、何时到达最大值：假设我们输入数字 3，这时我们所要打印的范围为 1、2、3、4 ··· 999，那么只有对 999 加 1 的时候，才会停止打印，退出循环。也只有对 999 加 1 的时候，才会在第一个字符（下标为 0）的基础上产生进位，其他情况下都不会在第一个字符上产生进位。
该函数实现代码如下：
1 bool Increment(char *result) 2 { 3 bool isOverflow = false; 4 int nTakeover = 0; 5 int len = strlen(result); 6 7 for (int i = len -1; i >= 0; ++i) 8 { 9 int nNum = result[i] - '0' + nTakeover; 10 if(i == len -1) 11 nNum ++; 12 13 if(nNum < 10) 14 { 15 result[i] = nNum + '0'; 16 break; 17 } 18 else 19 { 20 if(i == 0) // 溢出 21 { 22 isOverflow = true; 23 break; 24 } 25 else // 其他位置上的进位 26 { 27 nTakeover = 1; 28 result[i] = nNum - 10 + '0'; 29 } 30 } 31 } 32 return isOverflow; 33 }
用此方法，我们实现了在 O(1) 的时间负责度上判断了是否溢出（已到达最大值）。
二、把字符串表达的数字打印出来
函数原型：void PrintNumber(char *result)
注意：在打印时，遍历字符串，直到找到第一个不为 ‘0’ 的字符，并且从该字符处开始打印。 也就是说 “000000123”仅仅代表整数 123，一般在我们打印整型 123 时，是不打印出前面的 0 的。而解决此问题的办法是设置一个布尔型标志位 isBegin0，代表遍历的该字符是不是前面补位的 ’0‘；
具体代码如下：
1 void PrintNumber(result) 2 { 3 bool isBegin0 = true; 4 int len = strelen(result); 5 6 for(int i = 0; i < len; ++i) 7 { 8 if(isBegin0 && result[i] != '0') 9 isBegin0 = false; 10 11 if(!isBegin0) // 不是补位的'0' 12 printf("%c", result[i]); 13 } 14 }
完整的测试代码如下：
1 // Print1ToMaxOfNDigits.cpp 2 #include "stdio.h" 3 #include "stdlib.h" 4 #include "string.h" 5 6 7 bool Increment(char *number); 8 void PrintNumber(char *number); 9 10 void Print1ToMaxOfNDigits(int n) 11 { 12 if(n <= 0) 13 return; 14 15 char *number = new char[n+1]; 16 memset(number, '0', n); 17 number[n] = ' '; 18 19 while(!Increment(number)) 20 { 21 PrintNumber(number); 22 } 23 printf(" "); 24 delete []number; 25 } 26 27 bool Increment(char *number) // 实现+1，并判断是否达到最大值 28 { 29 bool isOverFlow = false; 30 int nTakeover = 0; 31 int len = strlen(number); 32 33 for(int i = len - 1; i >= 0; --i) 34 { 35 int nNum = number[i] - '0' + nTakeover; 36 if(i == len - 1) 37 nNum += 1; 38 39 if(nNum < 10)// 小于10,退出循环 40 { 41 number[i] = nNum + '0'; 42 break; 43 } 44 else // 大于10 45 { 46 if(i == 0) // 第一位进位，表示已经溢出 47 { 48 isOverFlow = true; 49 break; 50 } 51 // 其余为进位 52 nTakeover = 1; 53 number[i] = nNum - 10 + '0'; 54 } 55 56 } 57 return isOverFlow; 58 } 59 60 void PrintNumber(char *number) // 打印数字 61 { 62 bool isBegin0 = true; 63 int len = strlen(number); 64 65 for(int i = 0; i < len; ++i) 66 { 67 if(isBegin0 && number[i] != '0') 68 isBegin0 = false; 69 70 if(!isBegin0) // 不是补位的'0' 71 printf("%c", number[i]); 72 } 73 printf(" "); 74 } 75 76 int main(int argc, char *argv[]) 77 { 78 int i; 79 while(printf("Please input a int: "), scanf("%d", &i)) 80 { 81 Print1ToMaxOfNDigits(i); 82 } 83 return 0; 84 }
本文完。