打印从1到最大的n位数:使用大数

x33g5p2x  于10个月前 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(101)

题目:

给定一个正整数 n,打印从 1 到最大的 n 位数。

例如:
n = 2, 则打印从 1 到 99;
n = 3, 则打印从 1 到 999。

思路:

在 n 比较小(比如n=1或n=2或n=3)时,可以使用一个循环简单的解决问题,但当 n 比较大时,打印的数字可能会超出 int 或 long所能表示的范围,这是就应该使用string来表示大数以解决问题。

代码:

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

char chararr[10] = {'0','1','2','3','4','5','6','7','8','9'};

void dfs(int n, string s, string &res)
{
	if(s.size()==n)
	{
		for(int i=0; i<s.size(); ++i)  //处理前缀0
		{
			if(s[i]!='0')
			{
				break;
			}
			else
			{
				s.erase(0,1);
				i--;
			}
		}
		if(s.size()==0)
		{
			return;
		} 
		res = res + s + " ";
		return;
	}
	for(int i=0; i<10; ++i)
	{
		s += chararr[i];
		dfs(n,s,res);
		s.erase(s.size()-1,1);
	}
}

int main()
{
	int n = 0;
	cin >> n;
	string s = "";
	string res = "";
	dfs(n,s,res);
	cout << res;
}

相关文章