加入收藏 | 设为首页 | 会员中心 | 我要投稿 核心网 (https://www.hxwgxz.com/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

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

发布时间:2021-03-11 05:29:43 所属栏目:大数据 来源:网络整理
导读:题目:输入数字N,按顺序打印从1到最大的n位十进制数。比如输入3,则打印出1、2、3一直到最大的三位数即:999. 乍一看这个题目很简单,我们很快就会写出下面的代码: void onetoN(int n){int number=1;for(int i=0;in;i++){number*=10;}for(int i=1;inumber;

题目:输入数字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]='';
   while(!Increment(number))
   {
	   printNumber(number);
   }
   delete []number;
}
int main()
{
	onetoN(5);
	system("pause");
	return 0;
}

运行结果:

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

??

? 因为是输出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,n);
	number[n]='';
	for(int i=0;i<10;i++)
	{
		number[0]=i+'0';
		printRcursive(number,n,0);
	}
	delete []number;
}

(编辑:核心网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    热点阅读