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

stonepct

原帖由 yzc2002 于 2006-3-29 17:22 发表

是的，有兴趣的话我贴上来吧
说实话，打这个东西可不容易啊~~

Ｃｏｏｌ！
Ｇｏｔ　ｉｔ！

艾斯尼勒

数学没学好，证明都没看懂：（

shield8171

还是没理解到。。。
怎么算出来的数会这么大呢？
你说的最大是不是long最大的时候能得出的结果？

bombzhao

呵呵!学习是很重要滴!

emacsnw

原帖由 yzc2002 于 2006-3-29 01:22 发表

是的，有兴趣的话我贴上来吧
说实话，打这个东西可不容易啊~~

这个证明应该是严谨了。我有一个想法，要简单的多。
考虑从0到 99...9 （n个9）这10^n个数，如果不足n位的数字前面补0，那么这样10^n个数
的每位数字正好编历了一样个数的0,1,...,9。也就是每位数字出现1的概率正好是1/10。

当n>10的时候，考虑0到 99...9 (n个9)这么多数字，根据上面结论，这n位上每一位出现1的
概率还是1/10，但是整个数有n>10位，所以平均每个数出现多于1个1，因此 f(n)-n 的差会
越来越大，再也不会出现f(n) = n的情况。

当然这算不上严谨的证明，比起上面这位差了不少。

liubaochen

强！

fkiori

perl的代码
#!usr/bin/perl
while (<STDIN>)
{
  chomp;
  print get_one($_),"\n";
}

sub get_one
{
  my $num = shift();
  return 0 if ($num !~ /^\d+$/);
  print $num ." = ";
  my $longnum;
  for(my $i=1;$i<=$num;$i++){$longnum .= $i;}
  my @result = $longnum =~ /1/g;
  return $#result + 1;
}

苏蓉蓉

除了LZ，你们楼上的代码包括FLW的都没有什么
技巧可言，都是以统计单个“1”出现的次数为基
础的。这个题目没有想清楚算法，是很难写出高效
率的程序的。

macrodba

good support

libin1983

这道题我只推出了
f(10^n  - 1) = n * 10^(n-1)
仅此而已 !

----------------------------------
我的算法：
                        
令 g(n)=f(n) - f(n-1)
g(n)={n中元素1的个数}，如：g(1)=0，g(5)=0， g(11)=2 ， g(12)=1   ...

不妨设f(0)=0。
可得f(n) = f(n-1) + g(n)   
则使用迭代法可以计算f(n)    n=1,2,3 ...

[ 本帖最后由 libin1983 于 2006-3-30 13:13 编辑 ]