《剑指offer》:[16]打印1到最大的N位数

题目：输入数字N，按顺序打印从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的三位数即：999.

乍一看这个题目很简单，我们很快就会写出下面的代码：

void onetoN(int n)
{
	int number=1;
	for(int i=0;i<n;i++)
	{
		number*=10;
	}
	for(int i=1;i<number;i++)
	{
		cout<<i<<" ";
	}
}
           

  但是这里又有问题了，仔细一想，如果n是特别大的一个数呢？如果用long long都会溢出？多以这里要考虑大数问题。解决大数问题，我们一般采取两种方法：

第一：采用数组；

第二：采用字符串。这里我们采用字符串来解决。

代码实现如下：

#include <iostream>
using namespace std;
void printNumber(char * number)
{
	bool isbeginning0=true;
	int length=strlen(number);
	for(int i=0;i<length;i++)
	{
		if(isbeginning0 && number[i]!='0')
			isbeginning0=false;
		if(!isbeginning0)
			cout<<number[i];
	}
	cout<<" ";
}
bool Increment(char *number)
{
	bool isoverflow=false;
	int nTakeOver=0;
	int Length=strlen(number);
	for(int i=Length-1;i>=0;i--)
	{
		int nSum=number[i]-'0'+nTakeOver;
		if(i==Length-1)
			nSum++;
		if(nSum>=10)
		{
			if(0==i)
				return true;
			else
			{
				nSum-=10;
				nTakeOver=1;
				number[i]='0'+nSum;
			}
		}
		else
		{
			number[i]='0'+nSum;
			break;
		}
	}
	return isoverflow;
}
void onetoN(int n)
{
   if(n<0)
	   return ;
   if(0==n)
   {
	   cout<<0<<endl;
	   return;
   }
   char *number=new char[n+1];
   memset(number,'0',n);
   number[n]='\0';
   while(!Increment(number))
   {
	   printNumber(number);
   }
   delete []number;
}
int main()
{
	onetoN(5);
	system("pause");
	return 0;
}
           

运行结果：

  因为是输出1--N位数的数字，所以可以用全排列来完成。这里还可以使用递归方法：

   具体代码实现如下：

void printRcursive(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';
		printRcursive(number,length,index+1);
	}
}
void onetoN(int n)
{
	if(n<0)
		return ;
	if(0==n)
	{
		cout<<0<<endl;
		return;
	}
	char *number=new char[n+1];
	memset(number,'0',n);
	number[n]='\0';
	for(int i=0;i<10;i++)
	{
		number[0]=i+'0';
		printRcursive(number,n,0);
	}
	delete []number;
}