输出1到最大的N位数
【转】http://zhedahht.blog.163.com/blog/static/2541117420094279426862/
?
?
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");
}
??? 第二种思路基本上和第一种思路相对应，只是把一个整型数值换成了字符串的表示形式。同时，值得提出的是，判断打印是否应该结束时，我没有调用函数strcmp比较字符串number和”99…999”（n个9）。这是因为strcmp的时间复杂度是O(n)，而判断是否溢出的平均时间复杂度是O(1)。
???????? 第二种思路虽然比较直观，但由于模拟了整数的加法，代码有点长。要在面试短短几十分钟时间里完整正确写出这么长代码，不是件容易的事情。接下来我们换一种思路来考虑这个问题。如果我们在数字前面补0的话，就会发现n位所有10进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的10进制数。只是我们在输出的时候，数字排在前面的0我们不输出罢了。
???????? 全排列用递归很容易表达，数字的每一位都可能是0到9中的一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。
// Print numbers from 1 to the maximum number with n digits, in order
void Print1ToMaxOfNDigits_3(int n)
{
??? // 0 or minus numbers are invalid input
??? if(n <= 0)
??????? return;
?
??? char* number = new char[n + 1];
??? number[n] = '\0';
?
??? for(int i = 0; i < 10; ++i)
??? {
??????? // first digit can be 0 to 9
??????? number[0] = i + '0';
?
??????? Print1ToMaxOfNDigitsRecursively(number, n, 0);
??? }
?
??? delete[] number;
}
?
// length: length of number
// index: current index of digit in number for this round
void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index)
{
??? // we have reached the end of number, print it
??? if(index == length - 1)
??? {
??????? PrintNumber(number);
??????? return;
??? }
?
??? for(int i = 0; i < 10; ++i)
??? {
??????? // next digit can be 0 to 9
??????? number[index + 1] = i + '0';
?
??????? // go to the next digit
??????? Print1ToMaxOfNDigitsRecursively(number, length, index + 1);
??? }
}
函数PrintNumber和前面第二种思路中的一样，这里就不重复了。对比这两种思路，我们可以发现，递归能够用很简洁的代码来解决问题。
