每天一道算法题(15)——打印1到最大的n位数

题目：

打印1到最大的n位数。如n=4，打印1-9999。

思路：

由于直接使用循环会导致int或者long long都不够存储。因此使用字符串来存储数据，这里涉及到数字转换成字符串以及字符串的加法。

代码：

1.使用递归思路。

可以认为。从高位到低位，高位数先固定，在此情况下，低位数依次调整。每一位涉及0-9调整，这里每一级的都要嵌套10次。

void printMax(char* number,const int index,const int size){//嵌套打印函数,size为总的位数
if(!number)
return ;
if(index==size){//嵌套截止条件
show(number);
return ;
}
for(int i=0;i<10;i++){
number[index]=i+'0';//index---当前调整的位数
printMax(number,index+1,size);
}
}
void print2(const int& n){//主函数
if(n<=0)
return ;
char* number=new char[n+1];
memset(number,'0',(n+1)*sizeof(char));number[n]='\0';
printMax(number,0,n);delete []number;
}

     2.假设不使用递归思路

则单次循环是对上次循环产生的数的+1。即要模拟加法过程。这里使用了进位辅助数组，当最高位产生进位时，循环停止。

void increment(char* num,int size,int* add){//单次增1函数
if(!num||!add||size<=0)
return;
char* number=num+size-1;//从最后一位开始变化
for(int i=size-1;i>=0;i--){
if(*number-'0'+add[i+1]==10){//产生进位
*number='0';
add[i]=1;//存储进位
number--;//指针前移
}
else{
*number=*number+add[i+1];
add[i+1]=0;//删除进位信息
break;
}
}
}
void printMax(const int& n){//主函数
if(n<=0)
return;char* num=new char[n+1];//数字存储字符串
int* add=new int[n+1];//进位辅助数组，代表当前是否产生进位
memset(num,'0',(n+1)*sizeof(char));num[n]='\0';
memset(add,0,(n+1)*sizeof(int));while(1){
add[n]=1;
increment(num,n,add);
if(add[0])//最高位产生进位，循环打印停止
break;
show(num);//打印数字
}delete []num;
delete []add;
}

 

   3.字符串打印函数

void show(const char* num){
const char* p=num;
while(*p=='0')
p++;
if(*p)//*p='\0'
cout<<p<<endl;
}