據(jù)說是google的面試題，看誰的快

stonepct

原帖由 yzc2002 于 2006-3-29 17:22 發(fā)表

是的，有興趣的話我貼上來吧
說實(shí)話，打這個(gè)東西可不容易啊~~

Ｃｏｏｌ！
Ｇｏｔ�。椋�！

艾斯尼勒

數(shù)學(xué)沒學(xué)好，證明都沒看懂：（

shield8171

還是沒理解到。。。
怎么算出來的數(shù)會(huì)這么大呢？
你說的最大是不是long最大的時(shí)候能得出的結(jié)果？

bombzhao

呵呵!學(xué)習(xí)是很重要滴!

emacsnw

原帖由 yzc2002 于 2006-3-29 01:22 發(fā)表

是的，有興趣的話我貼上來吧
說實(shí)話，打這個(gè)東西可不容易啊~~

這個(gè)證明應(yīng)該是嚴(yán)謹(jǐn)了。我有一個(gè)想法，要簡(jiǎn)單的多。
考慮從0到 99...9 （n個(gè)9）這10^n個(gè)數(shù)，如果不足n位的數(shù)字前面補(bǔ)0，那么這樣10^n個(gè)數(shù)
的每位數(shù)字正好編歷了一樣個(gè)數(shù)的0,1,...,9。也就是每位數(shù)字出現(xiàn)1的概率正好是1/10。

當(dāng)n>10的時(shí)候，考慮0到 99...9 (n個(gè)9)這么多數(shù)字，根據(jù)上面結(jié)論，這n位上每一位出現(xiàn)1的
概率還是1/10，但是整個(gè)數(shù)有n>10位，所以平均每個(gè)數(shù)出現(xiàn)多于1個(gè)1，因此 f(n)-n 的差會(huì)
越來越大，再也不會(huì)出現(xiàn)f(n) = n的情況。

當(dāng)然這算不上嚴(yán)謹(jǐn)?shù)淖C明，比起上面這位差了不少。

liubaochen

強(qiáng)！

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的都沒有什么
技巧可言，都是以統(tǒng)計(jì)單個(gè)“1”出現(xiàn)的次數(shù)為基
礎(chǔ)的。這個(gè)題目沒有想清楚算法，是很難寫出高效
率的程序的。

macrodba

good support

libin1983

這道題我只推出了
f(10^n  - 1) = n * 10^(n-1)
僅此而已 !

----------------------------------
我的算法：
                        
令 g(n)=f(n) - f(n-1)
g(n)={n中元素1的個(gè)數(shù)}，如：g(1)=0，g(5)=0， g(11)=2 ， g(12)=1   ...

不妨設(shè)f(0)=0。
可得f(n) = f(n-1) + g(n)   
則使用迭代法可以計(jì)算f(n)    n=1,2,3 ...

[ 本帖最后由 libin1983 于 2006-3-30 13:13 編輯 ]