題目
輸入數(shù)字n，按順序打印出從1到最大的n位十進(jìn)制數(shù)。比如輸入3掏缎，則打印出1、2煤杀、3一直到最大的3位數(shù)999
思路1
最直觀的辦法就是先求出最大的n位數(shù)眷蜈，然后用一個(gè)循環(huán)從1開(kāi)始打印。實(shí)現(xiàn)如下：
void PrintToMaxOfNDigits_1(int n)
{
int number = 1;
int i = 0;
while (i++ < n) {
number *= 10;
}
for (i = 1; i < number; i++) {
printf("%d\t", i);
}
}
看起來(lái)好像沒(méi)什么問(wèn)題沈自，但如果仔細(xì)思考這個(gè)問(wèn)題酌儒，我們就能注意到這里沒(méi)有規(guī)定n的范圍。當(dāng)輸入的n很大的時(shí)候枯途，求最大的n位數(shù)是不是用整形（int）或者長(zhǎng)整形（long long）都會(huì)溢出忌怎？也就是說(shuō)需要考慮大數(shù)問(wèn)題。
最常用也是最容易的方法是用字符串或者數(shù)組表達(dá)大數(shù)酪夷。
接下來(lái)使用字符串來(lái)解決大數(shù)問(wèn)題
在用字符串表示數(shù)字的時(shí)候榴啸，最直觀的方法就是字符串里每個(gè)字符都是'0'-'9'之間的某一個(gè)字符，用來(lái)表示數(shù)字中的一位晚岭。因?yàn)閿?shù)字最大是n位的鸥印，因此我們需要一個(gè)長(zhǎng)度為n+1的字符串（字符串中最后一位是結(jié)束符'\0'）。當(dāng)實(shí)際數(shù)字不夠n位的時(shí)候坦报，在字符串的前半部分補(bǔ)0
首先字符串的每一個(gè)數(shù)字都初始化為'0'库说，然后每一次為字符串表示的數(shù)字加1，再打印出來(lái)燎竖。因此，我們只需要做兩件事：
- 一是字符串表達(dá)的數(shù)字上模擬加法
- 二是字符串表達(dá)的數(shù)字打印出來(lái)
基于上面的分析要销，我們可以寫出如下代碼
// n最大的位數(shù)
void PrintToMaxOfNDigits(int n)
{
// 容錯(cuò)處理构回，n不應(yīng)該小于等于0
if (n<=0)
return;
// 分配字符數(shù)組空間
char *number = new char[n+1];
// 字符數(shù)組中的值全部設(shè)置為'0'
memset(number, '0', n);
// 最后一位設(shè)置為'\0'
number[n] = '\0';
while (!Increment(number)) { // 加1打印
PrintNumber(number);
}
// 釋放對(duì)象所占有的空間
delete []number;
}
Increment函數(shù)的代碼，實(shí)現(xiàn)了用O(1)時(shí)間判斷是不是已經(jīng)到了最大的n位數(shù)
bool Increment(char *number)
{
bool isOverflow = false;
int nTakeOver = 0;
// 得到字符串的長(zhǎng)度
int nLength = strlen(number);
// 從后往前遍歷
for (int i=nLength - 1; i >= 0; i--) {
int nSum = number[i] - '0' + nTakeOver;
// 每次累加1
if (i == nLength - 1)
nSum++;
// 累加到10，開(kāi)始進(jìn)位
if (nSum >= 10)
{
if (i == 0) // 溢出纤掸，打印解釋脐供，如：n=3，只打印0-999,在1000的時(shí)候結(jié)束操作
isOverflow = true;
else
{
nSum -= 10; // 回到0
nTakeOver = 1; // 進(jìn)位值
number[i] = '0' + nSum;
}
}
else
{
// 正常的存儲(chǔ)數(shù)據(jù)
number[i] = '0' + nSum;
break;
}
}
return isOverflow;
}
函數(shù)PrintNumber借跪，在這個(gè)函數(shù)里政己，只有在碰到第一個(gè)非0的字符之后才開(kāi)始打印，直至字符串的結(jié)尾掏愁，實(shí)現(xiàn)如下
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");
}
思路2
把問(wèn)題轉(zhuǎn)換成數(shù)字排列的解法歇由，遞歸讓代碼更簡(jiǎn)潔
上述思路雖然比較直觀，但由于模擬了整數(shù)的加法果港，代碼有點(diǎn)長(zhǎng)沦泌。接下來(lái)?yè)Q一種思路來(lái)考慮這個(gè)問(wèn)題。如果我們?cè)跀?shù)字的前面補(bǔ)0辛掠，就會(huì)發(fā)現(xiàn)n位所有十進(jìn)制數(shù)其實(shí)就是n個(gè)從0到9的全排列谢谦。也就是說(shuō)，我們把數(shù)字的每一位都從0到9排列一遍萝衩，就得到了所有的十進(jìn)制數(shù)回挽。只是在打印的時(shí)候，排在前面的0不打印出來(lái)罷了猩谊。
全排列用遞歸很容易表達(dá)千劈，數(shù)字的每一位都可能是0-9中的一個(gè)數(shù)，然后設(shè)置下一位预柒。遞歸結(jié)束的條件數(shù)我們已經(jīng)設(shè)置了數(shù)字的最后一位
void PrintToMaxOfNDigits(int n)
{
if (n<=0)
return;
char *number = new char[n+1];
number[n] = '\0';
for (int i=0; i < 10; i++) {
number[0] = i + '0';
Print1ToMaxOfNDigitsRecursively(number, n, 0);
}
delete [] number;
}
void Print1ToMaxOfNDigitsRecursively(char *number, int length, int index)
{
if (index==length-1) {
PrintNumber(number);
return;
}
for (int i=0; i<10; i++) {
number[index+1] = i + '0';
Print1ToMaxOfNDigitsRecursively(number, length, index + 1);
}
}
參考
《劍指offer》
