专注于 ActionScript 3.0 在各应用领域的研究。
« Adobe Flex编码指南v1.2(AS3 Flex3程序代码编写规范)与君共难 祭汶川8.0级大地震 »

2008-4-26 1:23:59

1-400亿中包含有多少个1? 微软面试题算法分析－原创－Flex版

   题目是：统计从1至400亿之间的自然数中含有多少个1？比如1-11中，有1，10，11这三个自然数有4个1。

   这是一道微软的面试题，我在网上看到的，但是没有答案，这是件很痛苦的事情，折磨人，所以我决心自己来搞定。

   实际解题过程中，用递归的方法很容易，但是仅仅局限于400亿这样的数字，如果是1-1231111321这样的数字的话，就复杂多了，我在文档类里面有非常详尽的解题思路，用了3种解题的方法，因为排版麻烦，我就不重复贴在网页上了，要看的朋友下载看吧。

   有可能算法不是最完美的，希望朋友们能多指教。

   本来用的是flash写文档类，今天改了一下，用flex做了一个界面，方便大家计算使用。
   此外这个计算器还有计算1到任意数字(如1230321)中有多少个1。
   注：第一种算法有最大限制。

  

  提供的下载为flex工程。

  countNumberOneFlex.rar

Tags: AS3  原创  微软面试题  算法  经验  
发布:dmh2002 | 分类:数据结构与算法 | 评论:8 | 引用:0 | 浏览:
  • quote 2.hydra1983
  • http://blog.163.com/hydra1983
  • 我的阶乘算法有点问题，呃，算错了，最终答案是540000000000
    执行时间3msec
    有个算法比我的要快，也简单的很
    private function anotherFunc(max:Number):Number
    {
    var numbers:String = max.toString();
    var x:Number = Math.pow(10,numbers.length-1);

    var count:Number = 0;

    for(var i:int = 0 ;i <numbers.length;i++)
    {
    count+= Number("0"+numbers.substring(0,i))*x;

    if(numbers.charAt(i) > "1")
    {
    count+=x;
    }
    else if(numbers.charAt(i)=="1")
    {
    count +=Number("0"+numbers.substring(i+1))+1;
    }
    x/=10;
    }
    return count;
    }
  • 2008-4-26 16:53:21 回复该留言
  • quote 3.lann
  • 你的flex真不错，希望能向你请教!

    我想这是个排列组合问题吧，用笔就好了。
    用400亿减所有不含1的自然数的个数。

    不含1自然数的个数：
    400亿，有11位。若不含有1，除最高位有3种可能0、2、3（4只有一个数，400亿），其他位均有0、2、..9(没有1）的9种可能。这么就出来了：
    40000000000-(3*9^10-1+1)=29 539 646 797（这个用笔有点囧，google！）
    “-1”是去掉0，“+1”是包含400亿。

  • 2008-4-28 16:58:55 回复该留言
  • quote 4.dmh2002
  • lann:
    你好，我看了你的算法，发现一些问题。
    先举个小例子：
    我们知道1-10之间有2个1，
    但是按照你的算法
    10 - ( 1*9^(2-1)+1)=0
    少了2个，怎么会变得一个都没有了？
    看看你排除的数字，0，2，3，4，5，6，7，8，9，再加上10位上的1，正好10个数字，所以答案就变成0 了
    此外，这个flex的计算器不单能计算400亿，还可以计算类似于12343212032这样的数字，你可以试试。
  • 2008-4-29 0:52:26 回复该留言
  • quote 5.hydra1983
  • 第一个框框还是做个输入限制的好，哪位同志一不小心输入个400000000000，呃，他就等吧～～
  • 2008-4-29 9:00:23 回复该留言
  • quote 6.lann
  • 这回囧大了。发完就知道理解错了~~重做(这败家孩子）！
    s=1*f(1)+2*f(2)+……10*f(10)+11*f(11)这么表示方便点：【x*f(x)】(x:[1,11])
    s：400亿含有1个数。
    f(x):400亿里含有x个1的自然数个数。
    f(x)=n(x)+m(x)
    n(x):最高位（百亿位）是1
    m(x):最高位不是1
    n(x)=C(10,x-1)*9^(11-x)
    m(x)=3*C(10,x)*9^(10-x)
    n=【x*n(x)】=……=【11*C(10,t)*9^t】-【3*C(10,t)*9^t】=11*10^10-9*10^10=2*10^10 (x:[1,11]，t=11-x ,t:[0,10])
    m=【x*m(x)】=3*10^10 (x:[1,11])
    s=5*10^10
    打的好累~~

  • 2008-4-29 9:26:32 回复该留言
  • quote 7.lann
  • 还有另一种角度，那就简单多了(真的好简单)。
    1在百亿位出现的次数：10^10
    1在其他位(个位，十位……十亿位共10位)出现的次数：(4*10^9)*10
    s=10^10+4*10^10=5*10^10
    s(10^x)=x*10^(x-1)+1
    s(1-1231111321)=1231111321*10^1231111320+1

  • 2008-4-29 9:32:46 回复该留言
  • quote 8.zxj
  • select -- 400,0000,0000 400亿一共11位
    4*( -- 4种 100,0000,0000 的统计结果
    power(9,9)*1*(10)/1+ -- 由 9 个 非 1 和 1 个 1 构成 , 1 出现的情况为 10 种
    power(9,8)*2*(10*9)/2+ -- 由 8 个 非 1 和 2 个 1 构成 , 1 出现的情况为 10 * 9 种
    power(9,7)*3*(10*9*8)/3/2+
    power(9,6)*4*(10*9*8*7)/4/3/2/1+
    power(9,5)*5*(10*9*8*7*6)/5/4/3/2/1+
    power(9,4)*6*(10*9*8*7*6*5)/6/5/4/3/2/1+
    power(9,3)*7*(10*9*8*7*6*5*4)/7/6/5/4/3/2/1+
    power(9,2)*8*(10*9*8*7*6*5*4*3)/8/7/6/5/4/3/2/1+
    power(9,1)*9*(10*9*8*7*6*5*4*3*2)/9/8/7/6/5/4/3/2/1+ -- 由 9 个 1 和 1 个 非1 构成 , 1 出现的情况为 10 种
    10 * 1
    ) -- 10个1 只有1种情况
    + 1 --100,0000,0000
    + 11 -- 11个数 全部为 1 的情况
    from dual;


    select -- 100一共2位 , 1,10,11,12,13,14,15,16,17,18,19, 21,31,41,51,61,71,81,91,100 共 21 个
    1*(2*1)*power(9,3-1-1)+ -- 1个1构成 , 1的可选位置为2个, 1的位置有 2*1种, 其他字符的摆放位置 power(9,3-1-1) 种
    2*(1) *power(9,3-1-2)+ -- 2个1构成 , 1的可选位置为1个, 1的位置有 1 种, 其他字符的摆放位置 power(9,3-1-2) 种
    1 -- 100个1只有1种情况
    from dual;
  • 2010-7-9 11:40:58 回复该留言

发表评论:

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

日历

最新评论及回复

最近发表

Powered By Z-Blog 1.8 Walle Build 100427 Code detection by Codefense

Copyright 2008-2010 DMH2002's Blog Some Rights Reserved.沪ICP备07021739号