首页 > 代码库 > 算法题：打印1到最大的n位数

算法题：打印1到最大的n位数

2024-07-15 15:40:02   227人阅读

说明：本文仅供学习交流，转载请标明出处，欢迎转载！
       今天看到剑指offer上的第12题，题目如下：
       输入数字n，按顺序打印出从1到最大的n位十位数。比如输入3，则打印出1,2,3,...,999。
       当我看到这个题目的时候，第一感觉就是用递归，为什么呢？首先得从我们的一个实际数字出发，比如123，我们对数字加1，实际上分为如下两个步骤：
       步骤1：最低位加1；
       步骤2：若发生进位，则向更高位传播该进位的影响（这也是递归的所在）。
       在完成这个算法题之前，我想插一句“细节决定成败！”，我们写一个程序，其实大体的思路都能想到，而往往忽略对细节的考虑，如果本题需要考虑的问题如下：
        1.如何表示一个n位数？（用字符数组）
        2.每次加1都在最低位进行；
        3.加1后若发生进位，则将该进位传播给高位数字（这里既可用循环，也可用递归）；
        4.若最高位发生进位，则溢出，该溢出可作为打印最后一个数的标志；
        5.打印数字时，只能从最高位不为0的数字起开始打印。（这符合数字的正常表示）
       递归实现如下：
#include<iostream>
#include<cstring>
using namespace std;
bool Increment(char *str,int length)//字符串加1，如果为发生溢出，则返回true，否则返回返回false
{
	if(str==NULL && length<1)//如果发生溢出，则返回false
	{
		return false;
	}
	int sum=str[length-1]-'0'+1;
	if(sum<10)//如果不发生进位
	{
		str[length-1]+=1;
		return true;
	}
	else
	{
		if(length-1==0)//如果溢出，则返回false
		{
			return false;
		}
		str[length-1]='0';//发生进位，把剩下的任务交给前length-1个字符
		return Increment(str,length-1);//递归表达式
	}
}
void print(char *str)//打印字符，打印时去掉前面的几个0
{
	bool isBegin=false;//标识是否可以开始输出
	int i;
	for(i=0;i<strlen(str);i++)
	{
		if(!isBegin && str[i]!='0')//如果找到第一个非0字符，则标识可以开始输出了
		{
			isBegin=true;
		}
		if(isBegin)
		{
			cout<<str[i];
		}
	}
	cout<<endl;
}

void ToMaxN(int n)//打印从1到最大的N位数
{
	if(n>=1)
	{
		char *str=new char[n+1];
		memset(str,'0',n);
		str[n]='\0';
		while(Increment(str,n))//如果能顺利增长
		{
			print(str);
		}
		delete []str;
	}
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n>=1 && n<=5)
		{
			ToMaxN(n);
		}
	}
	return 0;
}
        非递归实现如下：
#include<iostream>
#include<cstring>
using namespace std;
bool Increment(char * str)//用于将当前字符串对应的数字加1，返回true表示增加成功
{
	int len=strlen(str);
	int current=str[len-1]-'0'+1;//将个位数字加1，current表示加1后的值
	int i=len-1;//下面开始传播个位加1后的连锁进位反应
	while(i>=0)//用i表示当前位
	{
		if(current<10)//若加1后不进位
		{
			str[i]=str[i]+1;
			break;
		}
		else//如果当前位发生进位
		{
			if(i==0)//如果进位的是最高位，则直接发生溢出
			{
				return false;
			}
			else//如果进位的不是最高位,这里能保证i!=0,因为上面有个为0的分支处理
			{
				str[i]='0';//先将本位归零
				i=i-1;//开始处理本位的上一位
				current=str[i]-'0'+1;
			}
		}
	}
	return true;
}
void print(char *str)//显示该数字
{
	bool begin=false;
	int i;
	int len=strlen(str);
	for(i=0;i<len;i++)
	{
		if(!begin && str[i]!='0')
		{
			begin=true;
		}
		if(begin)//如果已经找到第一个非0的高位数字
		{
			cout<<str[i];
		}
	}
	cout<<endl;
}

void ToMaxN(int n)//客户端调用的函数
{
	char *str=new char[n+1];
	memset(str,'0',n);//注意初值在中间，不是第三个参数
	str[n]='\0';
	while(Increment(str))
	{
		print(str);
	}
	delete []str;
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n>=1 && n<=5)
		{
			ToMaxN(n);
		}
	}
	return 0;
}
        测试结果如下：
       
参考资料：
   《剑指offer》


联系
我们