大数问题:打印1到最大的n位数

2017-06-29 23:12 阅读 804 次 评论 0 条

这道题属于一个经典的"大数问题",一个表面看似简单的算法,却深藏很多bug。只有考虑周全,才能斩获offer,此题出自剑指offer第12题,我们对递归与非递归两个版本进行分析。

算法要求

输入数字n,按顺序打印出从1到最大的n位10进制数。比如输入3,则打印出1、2、3一直到最大的3位数即999。

字符串上模拟加法

我们可以使用字符串来表示数字,每个字符都时'0'到'9'之间的某一个字符,我们需要使用一个长度位n+1的字符串(最后一位存储'\0')。

① 首先我们将字符串中的每一个数字都初始化为'0',然后从最低位递增,当最低位等于10时产生进位,并将最低位清零,直到最高位产生进位时,终止循环(借助标志位)。

② 由于我们初始化符串时给的'0',因此,当我们打印的数字不足n位时,高位会自动补0。因此我们需要从第一个非0字符之后开始打印(可使用标志位)。

数字全排列(递归)

如果我们在数字前面补0的话,就会发现n位所有10进制数就是n个0到9的全排列,到后面打印的时候不打印0就好了。

我们采用递归可以将一个大问题划分成多个子问题来求解,我们从数字的最高位递归,直到设置了最低位,进行打印。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:大数问题:打印1到最大的n位数 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情