打印1到最大的n位数(大数问题)
发布时间:2020-12-14 03:42:05 所属栏目:大数据 来源:网络整理
导读:/******************************************************题目:输入数字n,按顺序打印出从1最大的n位十进制。比如输入3,则打印出1,2,3,4一直到3位数最大值999。******************************************************//*分析:这个题目需要考虑大数问题
/****************************************************** 题目:输入数字n,按顺序打印出从1最大的n位十进制。比如输 入3,则打印出1,2,3,4一直到3位数最大值999。 ******************************************************/ /*分析: 这个题目需要考虑大数问题。也就是如果我们输入的n值比较大, 比如n=100,那么将会超出所有整形所能表示的范围(不论是int还是 long)。 解决办法: 在字符串解决大数问题 */ #include<stdio.h> #include<string.h> void printNumber(char* number); /* //实现方法1 bool increment(char* number); void print1ToMaxOfNDigital(int n) { if(n<=0) return; char* number = new char[n+1]; memset(number,'0',n); number[n] = ' '; while(!increment(number)) //increment函数用来使字符串表示的数字自增 { printNumber(number); //用来输出字符来代替数字 } delete[] number; } //实现字符自增,模拟数字自增 bool increment(char* number) { bool isOverFlow = false; //如果超过范围,溢出 int nTakeOver = 0; //超过10,进位 int nLength = strlen(number); //字符串长度,也就是位数n for(int i=nLength-1; i>=0; --i) { int nSum = number[i]-'0'+nTakeOver; if(i == nLength-1) nSum++; if(nSum>=10) //如果某一位上的数大于10 { if(i == 0) //如果在字符串的最低位,也就是数字上的最高位 isOverFlow = true; //超出范围 else { nTakeOver = 1; //进位 nSum -= 10; number[i] = '0'+nSum; //将超过10的这一位减去10 } } else { number[i] = '0' + nSum; //设置位上的数值 break; } } return isOverFlow; } */ //实现方法2,以上方法虽然能够实现基本功能,但编程思路落实不易 //下面采用将问题转换为数字全排列的解法 void print1ToMaxOfNDigitsRecursively(char* number,int length,int index); void print1ToMaxOfNDigital(int n) { if(n<=0) return; char* number = new char[n+1]; number[n] = ' '; for(int i=0; i<10; ++i) { number[0] = '0'+i; //数字表示最高位 print1ToMaxOfNDigitsRecursively(number,n,0); } delete[] number; } void print1ToMaxOfNDigitsRecursively(char* number,int index) { if(index == length-1) { printNumber(number); return; } for(int i=0; i<10; i++) { number[index + 1] = '0' + i; print1ToMaxOfNDigitsRecursively(number,length,index+1); } } //打印数字,防止高位为0是也打印出来 void printNumber(char* number) { bool isBeginning0 = true; int nLength = strlen(number); for(int i=0; i<nLength; ++i) { if(isBeginning0 && number[i]!='0') //从字符串最低位开始寻找第一个不是‘0’的位置 isBeginning0 = false; if(!isBeginning0) //如果不以‘0’开头,则打印 printf("%c",number[i]); } printf("t"); } int main() { print1ToMaxOfNDigital(3); }总结: 1.用字符串解决大数问题值得研究 2.需要注意的问题是字符串或者数组的最高位对于数字上的最低位。 3.如果面试题是关于n位的整数并且没有限定n的取值范围,或者是输入任意大小的整数, 那么这个题目很有可鞥需要考虑大数问题的字符串是一个简单、有效的表示大数的方法。 相关题目: 1)前面的代码中,我们都是用一个char型字符表示十进制数字的一位。 8个bit的char型字符最多能表示256个字符,而十进制数字只有0-9的10个数字。 因此用char型字符串来表示十进制的数字并没有充分利用内存,有一些浪费。 有没有更高效的方式来表示大数。 2)定义一个函数,在该函数中可以实现任意两个整数的加法。由于没有限定输入 两个数的大小范围,我们也要把它当做大数问题来处理。在前面的代码的第一个 思路中,实现了在字符串表示的数字上加1的功能,我们可以参考这个思路实现 两个数字相加功能,另外还有一个需要注意的问题:如果输入的数字中有负数, 我们应该怎么处理? 建议方案
void printf1ToMaxOfNDigits_1(int n) { if(n<=0) return; char* number = new char[n+1]; number[n] = ' '; for(int i=0; i<10; ++i) { number[0] = '0' + i; printf1ToMaxOfNDigits_1(number,0); } delete[] number; //不要忘记释放内存 } void printf1ToMaxOfNDigits_1(int* number,int len,int index) { if(index == len-1) { printfNumer(number); return; } else { for(int i=0; i<10; ++i) { number[index+1] = '0' + i; printf1ToMaxOfNDigits_1(number,len,index+1); } } } void printfNumer(char* number) { bool isBegingWith0 = true; int len = strlen(number); for(int i=0; i<len; ++i) { if(isBegingWith0 && number[i] != '0') isBegingWith0 = false; if(!isisBegingWith0) { printf("%c",number[i]); } } printf("t"); } ==参考剑指offer (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |