技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 从一道题目谈计算机和数学

从一道题目谈计算机和数学

浏览:3412次  出处信息

    统计从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)的实现即可,这样就更加把编程与数学统一起来解决问题了。

剩下的,如果读者有兴趣,自已来试试接下来的工作吧。

建议继续学习:

  1. 数学常数e的含义    (阅读:9233)
  2. 难倒犹太人的11个数学问题    (阅读:4373)
  3. 看来看去都是看数学书    (阅读:3218)
  4. 千万别学数学:最折磨人的数学未解之谜(二)    (阅读:2631)
  5. 集数学与艺术于一体的几何幻方    (阅读:2410)
  6. 数学之美:Marden定理    (阅读:1557)
  7. [Java基础教程]第六章-Java数学运算符    (阅读:921)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1