据说是google的面试题，看谁的快

linmingren

俺用java写了个,大家看看问题在哪


public class Numen
{
  public long f(int n)
   {
          if (n == 1)
          {
                  return 1;
          }
          
          else return f(n-1) + y(n);
   }
  
  public int y(int n)
  {
          String s = new Long(n).toString();
          
       
          
          int iNum = 0;
          
          for(int i = 0;i<  s.length(); ++i)
          {
                  String t = s.substring(i,i+1);
                  
                  if ( t.equals("1"))
                  {
                          ++ iNum;
                  }
          }
          
          return iNum;
          
          
  }
}


public class Main {

        /**
         * @param args
         */
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                Numen numen = new Numen();
               
                /*
                for( long i =0;i < Long.MAX_VALUE,f(n) ;++i)
                {
                        if ( numen.f((int)i) == i )
                        {
                                System.out.println(i);
                        }
                }
                */
                System.out.println(numen.f(199981));
        }

}

AndyFastow

In business world, money is king, so we have a phrase -- cash king .  Google is in this situation now.

In computer world, algorithm is king, I create a phrase:  alg-king. haha..  Google is in this situation too..

TurboDisk

用C写了一个算到结果为6位数的时候还可以不到1秒，但结果过了6位之后就不行了，写这个算法用了10多分钟啊！！！

TurboDisk

刚刚又想了起来，用移位的怎么样？

TurboDisk

最后看了看前面兄弟的贴，说白了考的是脑袋的机动性和经验，谁要是以前碰到过类似的题那不一下就把OFFER给KO了。不过佩服机动性比较好的那几位。

yangtou

对于数A＝(anan-1an-2.......a2a1a0)计1个数为f(A)

10^n内的1的个数:个位、十位、百位....(n)位的1都是10^(k-1),还有一个1，总共是n*10^(n-1)+1计为p(n)+1
1 ~　1
10 ~ 1 + 1
100 ~ 20 + 1
1000~ 300 +1
10000~ 4000 + 1
100000 ~ 50000 +1
..............
10^10 ~ 10^10 +1
p(0)=0 p(1) = 1 p(2)=20 p(3) = 300 ....  p(10) = 10^10
对于数A＝(anan-1an-2.......a2a1a0)
an=1                          f(A) = p(n) 　　　　+     (an-1an-2.......a2a1a0) +1 　　　　　　　　+ f((an-1an-2.......a2a1a0))
an >1                         f(A) = an * p(n) 　 +     10^n 　　　　　　　　　　　　　　　　　　　+ f((an-1an-2.......a2a1a0))

这样就定义了f(A)递归函数。
从p(10)可以看出A<10^n
注意到　f((an-1an-2.......a2a1a0)) <= p(n) 可以估计f(A)的上界
先比较f(A)前几项与A的大小，若A 比f(A)的上界大，就不需要再计算后面的位，这样
只需很少计算就可以解决。

j_zou

计算10里面有几个1, 100里有几个1, 1000里有几个1...

leonjoe

好答案，Google对于数学能力的要求还是比较高，面试短时间能算出来不容易

redspider

原帖由 TurboDisk 于 2006-4-1 03:07 发表
用C写了一个算到结果为6位数的时候还可以不到1秒，但结果过了6位之后就不行了，写这个算法用了10多分钟啊！！！

6位才10万数量级,perl 的模式匹配都不止这个速度。写代码只要1分钟

1. 
   
2. #! /usr/bin/perl
   
3. use warnings;
   
4. use strict;
   
5. 
   
6. my $i = 1;
   
7. my $tmp = 0;
   
8. 
   
9. while (1) {
   
10.     $tmp++ while ($i =~ /1/g);
    
11. 
    
12.     print $i,"\n" if ($tmp == $i);
    
13.     $i++;
    
14. }
    

复制代码

happer_xc

#include <stdio.h>
#include <stdlib.h>
main(int argc, char *argv[])
{
   long    num = 0 ;
   long    sum = 0 ;
   long    val = 0 ;
   register    i = 1 ;

   num = atol( argv[1] ) ;
   while(i<=num)
   {
       val = i ;
       while( val )
       {
           if( val % 10 == 1 ) sum++ ;
           val = val / 10 ;
       }
       if( i == sum ) printf("next is: [%ld]\n", i ) ;
       i++ ;
   }
   exit(0) ;
}