劍指offer 17. 列印從1到最大的n位數

目錄

題目描述

測試程式

正常解法

遞歸解法

題目描述

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

測試程式

void printNumber(char* const);    //列印數字的函數
void print1MaxOfNDigits(const long long&);    //我們需要寫出的函數

int main() {
	long long test_number;
	while (cin >> test_number) {
		print1MaxOfNDigits(test_number);
        cout << endl;
	}
	return 0;
}

void printNumber(char* const num) {
	long long beg = 0;
	while (num[beg] == '0') ++beg;
	for (long long i = beg; num[i]; ++i) {
		cout.put(num[i]);
	}
	cout << " ";
}
           

正常解法

bool Increment(char* const num, const long long& len) {
	char carry = 1;    //進位
	for (long long i = len - 1; i >= 0; --i) {    //末位+1，将進位逐位高位傳遞，直到不再産生進位
		num[i] += carry;
		if (num[i] == 0x3A) {    //'9'的ASCII值為0x39
			num[i] ^= 0x0A    //置為'0'
		}
		else {
			carry = 0;    
			break;
		}
	}
	return carry ? true : false;    //如果最高位産生進位，那麼傳回true，否則傳回false
}

void print1MaxOfNDigits(long long n) {
	char* const buffer = new char[n + 1];
	memset(buffer, '0', n);
	buffer[n] = '\0';

	while (!Increment(buffer, n)) {
		printNumber(buffer);
	}
}
           

遞歸解法

原理：n位10進制數，其實就是n個從0到9的全排列。 

typedef long long Lgth;

void print1ToMaxOfNDigitsRecursively(char* const number, const Lgth& length, const Lgth& idx) {
	for (int i = 0; i < 10; ++i) {
		number[idx] = '0' + i;    //處理idx位
		if (idx == length) printNumber(number);    //如果已經遞歸到末位，那麼輸出
		else print1ToMaxOfNDigitsRecursively(number, length, idx + 1);    //否則繼續向後遞歸
	}
}

void print1MaxOfNDigits(const Lgth& n) {
	char* const number = new char[n + 1];
	memset(number, '0', n);
	number[n] = '\0';

	print1ToMaxOfNDigitsRecursively(number, n - 1, 0);
}