剑指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] = '';

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