《劍指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;
}