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

fly231

這道題答出來不難，關(guān)鍵是效率，樓主比較厲害，很快就算出來了

rainballdh

沒想出什么好方法

flw

練練手：
In Haskell:

1. module Main where
   
2. 
   
3. g y x = x + case y of
   
4.             { '1' -> 1; _ -> 0 }
   
5. f 1 = 1
   
6. f (x+1) = f(x) + foldr (g) 0 (show(x+1))
   
7. 
   
8. h x = do
   
9.         if x == f(x)
   
10.             then
    
11.                 putStrLn( show(x) ++ ":" ++ show( f(x) ) )
    
12.             else
    
13.                 putStr( "" )
    
14.         h(x+1)
    
15. 
    
16. main = h 1

復(fù)制代碼

其實(shí)最核心的也就這四行：

1. g y x = x + case y of
   
2.             { '1' -> 1; _ -> 0 }
   
3. f 1 = 1
   
4. f (x+1) = f(x) + foldr (g) 0 (show(x+1))

復(fù)制代碼

flw

唔……Haskell 學(xué)的不好，上面那個(gè)程序太慢了，
下面換個(gè) Python 的，這個(gè)應(yīng)該快一些：

1. i=1
   
2. sum=0
   
3. 
   
4. while 1:
   
5.     count = str(i).count("1")
   
6.     sum += count
   
7.     if sum == i:
   
8.         print sum
   
9.     i += 1
   

復(fù)制代碼

Perl 的語法和 Python 差不多，不過速度應(yīng)該會(huì)快一些：

1. $i=0;
   
2. $sum=0;
   
3. while(1){
   
4.     $count = $i =~ s/1/1/g;
   
5.     $sum += $count;
   
6.     print "$i\n" if $i == $sum;
   
7.     $i++;
   
8. }

復(fù)制代碼

[ 本帖最后由 flw 于 2006-3-29 16:54 編輯 ]

converse

flw,這個(gè)問題考算法,不是考的語言吧...哈哈

flw

原帖由 converse 于 2006-3-29 16:52 發(fā)表
flw,這個(gè)問題考算法,不是考的語言吧...哈哈

版主不會(huì)出錯(cuò),出錯(cuò)的永遠(yuǎn)是實(shí)習(xí)版主,出了問題請先從自己身上考慮自己是不是犯錯(cuò)了

b46

原帖由 converse 于 2006-3-29 16:52 發(fā)表
flw,這個(gè)問題考算法,不是考的語言吧...哈哈

是不是應(yīng)該從數(shù)本身規(guī)律考慮，好多數(shù)不用測試的
<10    1
<100   11 12 13 14...21 31 41 51....
<1000 101 111 112 113 ....121 131...
今天回家再仔細(xì)想想

flw

還有個(gè)問題，什么叫做“下一個(gè)最大的”？
難道這個(gè)是有最大值的？

b46

原帖由 flw 于 2006-3-29 17:04 發(fā)表
還有個(gè)問題，什么叫做“下一個(gè)最大的”？
難道這個(gè)是有最大值的？

恩，這個(gè)確實(shí)是個(gè)BUG

yzc2002

原帖由 flw 于 2006-3-29 16:50 發(fā)表
唔……Haskell 學(xué)的不好，上面那個(gè)程序太慢了，
下面換個(gè) Python 的，這個(gè)應(yīng)該快一些：
[code]i=1
sum=0

while 1:
    count = str(i).count("1")
    sum += count
    if sum == i:
       ...

這兩個(gè)還差不多能看懂個(gè)70%,前面那個(gè)完全不明白是啥~~~
flw你會(huì)那么多的語言,不會(huì)搞混了么?