記錄來自《劍指offer》上的算法題。

題目如下：

輸入數字n，按順序打印出從1到最大的n位十進制數。比如輸入3，則打印出1，2，3一直到最大的3位數即999。

第一種解法是比較容易想到，但是遇到大數問題的時候會有溢出的問題，其代碼如下：

// 簡單的解法，但遇到輸入值很大時會出現問題 void Print1ToMaxOfNDigits_1(int n){int number = 1;int i = 0;while (i++ < n)number *= 10;for (i = 1; i < number; i++)cout << i << " ";cout << endl; }

所以這里需要表達一個大數。最常用也是最容易的方法是用字符串或數組表達大數。下面使用字符串來表達大數。解法代碼如下：

bool Increment(char* number){bool isOverflow = false;int nTakeOver = 0;int nLength = strlen(number);for (int i = nLength - 1; i >= 0; i--){int nSum = number[i] - '0' + nTakeOver;if (i == nLength - 1)nSum++;if (nSum >= 10){if (i == 0)isOverflow = true;else{nSum -= 10;nTakeOver = 1;number[i] = '0' + nSum;}}else{number[i] = '0' + nSum;break;}}return isOverflow; } // 打印用字符串表示的數字 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"); }// 利用字符串來表達大數 void Print1ToMaxOfNDigits_str(int n){if (n <= 0)return;// 初始化為'0'char *numbers = new char[n + 1];memset(numbers, '0', n);numbers[n] = '\0';while (!Increment(numbers)){PrintNumber(numbers);}delete[] numbers; } // 測試 int main(void){int t[] = { 0, 1, 3, -1 };for (int i = 0; i < 4; i++){cout << "test num=" << t[i] << ": \n";Print1ToMaxOfNDigits_str(t[i]);cout << endl;}system("pause");return 0; }

這種解法中，函數Increment()實現在表示數字的字符串numbers上增加1，并判斷是否出現溢出問題，也就是是否達到最大的n位數，而PrintNumber()函數則是打印出numbers。

其中在函數Increment()中，每次增加1后快速判斷是否到了最大的n位數的辦法是判斷第一個字符是否產生了進位，因為只有達到最大的n位數的情況才會對第一個字符（下標是0）進行進位，如n=3，只有對999再加1，才會對第一個字符進行進位，在函數中的體現就是在如下代碼:

if (nSum >= 10){if (i == 0)isOverflow = true;.... }

這種解法思路比較直觀，但是由于模擬了整數的加法，代碼有點長，下面換另一種思路。如果我們在數字面前補0，可以發現n位所有十進制數其實就是n個從0到9的全排列。也就是說，我們把數字的每一位都從0到9排列一遍，就可以得到所有的十進制數。

全排列用遞歸很容易表達，數字的每一位都是0到9中的一位，然后設置下一個數。遞歸結束的條件是已經設置了數字的最后一位。代碼如下：

// 遞歸方法 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);} } // 利用字符串來表達大數 void Print1ToMaxOfNDigits_str(int n){if (n <= 0)return;// 初始化為'0'char *numbers = new char[n + 1];//memset(numbers, '0', n);numbers[n] = '\0';/*while (!Increment(numbers)){PrintNumber(numbers);}*/for (int i = 0; i < 10; ++i){numbers[0] = i + '0';Print1ToMaxOfNDigitsRecursively(numbers, n, 0);}delete[] numbers; }

上述代碼中注釋掉的是第二種解法中的代碼，然后增加適用于遞歸方法的代碼。

更完整例子看出我的Github。

總結

以上是生活随笔為你收集整理的剑指offer--打印1到最大的n位数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。