首页 > 代码库 > 打印1到最大的n位数
打印1到最大的n位数
题目:输入数字n,按顺序打印出从1到最大的n位十进制数。比如输入3,则打印输出1,2,3一直到最大的三位数999.
直接方法:
void Print1ToMaxOfNDigits_1(int n) { int number=1; int i=0; while(i++<n) number*=10; for(i=1;i<number;i++) printf("%d\t",i); }
这样做其实就陷入了本题的陷阱:如果n很大,n位数用int甚至long long都会溢出?也就是说我们需要考虑大数问题。
方法:用字符串模拟数字的加法的解法,然后打印出字符串。
void Print1ToMaxOfNDigits(int n) { if(n<=0) return; char *number=new char[n+1]; memset(number,‘0‘,n); number[n]=‘\0‘; while(!Increment(number)) { PrintNumber(number); } delete []number; } bool Increment(char* number) { bool isOverflow =false; int nTakeOver=0; int nLength=strlen(number); for(int i=nLength-1;i>=0;i--) { int nSum=number[i]=‘0‘+nTakeOver; if(i==nLength-1) nSum++; if(nSum>=10) { if(i==0) isOverflow=true; else { nSum-=10; nTakeOver=1; number[i]=‘0‘+nSum; } } else { number[i]=‘0‘+nSum; break; } } return isOverflow; } void PrintNumber(char* number) { bool isBeginning0=true; int nLength=strlen(number); for(int i=0;i<nLength;++i) { if(isBeginning0&&number[i]!=‘0‘) isBeginning0=false; if(!isBeginning0) { printf("%c",number[i]); } } printf("\t"); }
上述思路虽然简单,但是代码有些长。我们可以把该问题转换成数字排列问题,如果在数字前面补零,发现n位所有十进制数其实就是n个从0到9的全排列。也就是说,我们把数字的每一位都从0到9排列一遍,就得到了所有的数。全排列用递归很容易表达,解法如下:
void Print1ToMaxOfNDigits(int n) { if(n<=0) return; char* number=new cahr[n+1]; number[n]=‘\0‘; for(int i=0;i<10;++i) { number[0]=i+‘0‘; Print1ToMaxOfNDigitsRecursively(number,n,0); } delete []number; } void Print1ToMaxOfNDigitsRecursively(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‘; Print1ToMaxOfNDigitsRecursively(number.length,index+1); } } void PrintNumber(char* number) { bool isBeginning0=true; int nLength=strlen(number); for(int i=0;i<nLength;++i) { if(isBeginning0&&number[i]!=‘0‘) isBeginning0=false; if(!isBeginning0) { printf("%c",number[i]); } } printf("\t"); }
本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1582843
打印1到最大的n位数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。