转载请注明出处：http://blog.csdn.net/ns_code/article/details/25562105

剑指offer第12题。九度OJ測试通过。

题目描写叙述：

给定一个数字N，打印从1到最大的N位数。

输入：

每一个输入文件仅包括一组測试例子。
对于每一个測试案例。输入一个数字N(1<=N<=5)。

输出：

相应每一个測试案例，依次打印从1到最大的N位数。

例子输入：

1

例子输出：

1

2

3

4

5

6

7

8

9

题目要求N<=5,因此不会出现大数问题。我们这里考虑大数问题。相同用字符串来处理大数问题，用字符串模拟实现大数自加1。

AC代码例如以下：

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<stdbool.h>

/*

打印字符数表示的数字。要跳过前面的'0'

*/

void PrintNum(char *num)

{

	int i = 0;

	while(num[i] == '0')

		i++;

	puts(num+i);

}

/*

字符串表示的数字模拟自加1

*/

bool Increment(char *num)

{

	bool isOverflow = false;

	int len = strlen(num);

	int i;

	//字符转化为整数

	for(i=0;i<len;i++)

		num[i] = num[i] - '0';

	//计算加1的结果

	num[len-1]++;

	for(i=len-1;i>=0;i--)

	{

		if(num[i]>=10)

		{

			if(i == 0)

			{	//假设在最高位进位，则说明打印完了

				isOverflow = true;

				num[i]--;

			}

			else

			{

				num[i] -= 10;

				num[i-1] += 1;

			}

		}

		else

			break;

	}

	//整数转化为字符

	for(i=0;i<len;i++)

		num[i] = num[i] + '0';	

	return isOverflow;

}

/*

打印从1到最大的n位数

*/

void PrintToMaxN(int n)

{

	if(n<=0)

		return;

	char *num = (char *)malloc((n+1)*sizeof(char));

	if(num == NULL)

		exit(EXIT_FAILURE);

	//每一个字节都初始化为'0'字符

	memset(num,'0',n*sizeof(char));

	num[n] = '\0';

	while(!Increment(num))

		PrintNum(num);

	free(num);

	num = NULL;

}

int main()

{

	int n;

	scanf("%d",&n);

	PrintToMaxN(n);

	return 0;

}

全排列递归实现方法：

数字的每一位都可能是0-9中的一个位数，我们把数字的每一位都从0到9排列一边，就得到了所有的十进制数，全排列用递归非常easy表达，数字的每一位都可能是一个数，然后设置下一位。这里递归结束的条件是我们已经设置了数字的最后一位。

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<stdbool.h>

/*

打印字符数表示的数字。要跳过前面的'0'

*/

void PrintNum(char *num)

{

	int i = 0;

	while(num[i] == '0')

		i++;

	puts(num+i);

}

/*

递归设置从index位往右的各位数字。并打印出来

*/

void RecursionPrint1ToN(char *num,int len,int index)

{

	if(index == len)

	{

		PrintNum(num);

		return;

	}

	int i;

	for(i=0;i<10;i++)

	{

		num[index] = i + '0';

		RecursionPrint1ToN(num,len,index+1);

	}

}

/*

打印从1到最大的n位数

*/

void Print1ToMaxN(int n)

{

	if(n<=0)

		return;

	char *num = (char *)malloc((n+1)*sizeof(char));

	if(num == NULL)

		exit(EXIT_FAILURE);

	//每一个字节都初始化为'0'字符

	memset(num,'0',n*sizeof(char));

	num[n] = '\0';

	//所有打印出来

	RecursionPrint1ToN(num,n,0);

	free(num);

	num = NULL;

}

int main()

{

	int n;

	scanf("%d",&n);

	Print1ToMaxN(n);

	return 0;

}