从一道题目谈计算机和数学
统计从1至400亿之间的自然数中含有多少个1?比如1-11中,有1,10,11这三个自然数有4个1。
拿到这道题目,您会如何去计算呢?如果是计算机方面的面试,你又该如何去思考呢?也有同事拿这道题目谈到了“数学”与“数感”的理解,不过笔者却想谈一些更实际一些东西。
如果是计算机方面的出现这道题目,我们可能首先想到的是挨个去找。比如1含有一个1,然后2不含有1,…10含有1个1, 11含有2个1,….直到4亿。实际去想想,可能还有第二种方法,即对于每一个数字,转换成一个字符串,然后查里面的1,这或许处理的时候简单一些,但思路基本一致。
方法二:对于每一个数字,首先转换成字符串,然后查询里面的1的个数,然后求合。这实际上没有实质的进步,无论计算复杂度还是难度,都没有质的简化。实际上如果仔细观察的话,我们会发现给出的一个有效数字是4亿,也意味着除了最高位是4位,其它全是0,那么由此可以知道它的位数是9位以内的,如果是9位,最高位只可能是1、2、3。有了这些信息我们就可以进一步分析了。
如果数字为9位,那么最高位只可能是1, 2, 3。如果最高位是1,那么剩余的8位可能含有1-8个1。因此进行分类分析。
剩余8位含有1个1的情况:2 * C(8, 1) * P(7, 7)。
剩余8位含有2个1的情况:3 * C(8, 2) * P(6, 6)。
….
然后将上面的值进行求合。
最高位是2, 3则可以进行类似计算,实际注意一下规范,可以利用上面的结果的。
我们再考虑一下其它情况,即含有1 - 8位的情况。我们假设含有N位,以此来进行说明。
最高位可能是1, 也可能是2-9,位不可能是0。因此可以利用上面类似的算法。
S(N) = 2 * C(N-1, 1) + 3 * C(N-1, 2) …. + (N-1) * C(N-1, N-1) + 8*(1 * C(N-1, 1) + 2 * C(N-1, 2) + … + (N-1) * C(N-1, N-1))
= ….(这里就看化简技巧了)
最终得出一个公式。实际上,如果你推出这样一个公司后,不一定需要化简,专门编一个子函数实现C(n, i)的实现即可,这样就更加把编程与数学统一起来解决问题了。
剩下的,如果读者有兴趣,自已来试试接下来的工作吧。
建议继续学习:
- 数学常数e的含义 (阅读:9274)
- 难倒犹太人的11个数学问题 (阅读:4395)
- 看来看去都是看数学书 (阅读:3239)
- 千万别学数学:最折磨人的数学未解之谜(二) (阅读:2655)
- 集数学与艺术于一体的几何幻方 (阅读:2433)
- 数学之美:Marden定理 (阅读:1652)
- [Java基础教程]第六章-Java数学运算符 (阅读:998)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:zja601 来源: Zhang Jiuan' Notes
- 标签: 数学
- 发布时间:2009-11-10 12:34:39
- [70] Twitter/微博客的学习摘要
- [66] 如何拿下简短的域名
- [65] IOS安全–浅谈关于IOS加固的几种方法
- [64] find命令的一点注意事项
- [63] android 开发入门
- [63] Go Reflect 性能
- [61] 流程管理与用户研究
- [59] 图书馆的世界纪录
- [59] 读书笔记-壹百度:百度十年千倍的29条法则
- [59] Oracle MTS模式下 进程地址与会话信