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

fly231

这道题答出来不难，关键是效率，楼主比较厉害，很快就算出来了

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

复制代码

其实最核心的也就这四行：

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))

复制代码

flw

唔……Haskell 学的不好，上面那个程序太慢了，
下面换个 Python 的，这个应该快一些：

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
   

复制代码

Perl 的语法和 Python 差不多，不过速度应该会快一些：

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. }

复制代码

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

converse

flw,这个问题考算法,不是考的语言吧...哈哈

flw

原帖由 converse 于 2006-3-29 16:52 发表
flw,这个问题考算法,不是考的语言吧...哈哈

版主不会出错,出错的永远是实习版主,出了问题请先从自己身上考虑自己是不是犯错了

b46

原帖由 converse 于 2006-3-29 16:52 发表
flw,这个问题考算法,不是考的语言吧...哈哈

是不是应该从数本身规律考虑，好多数不用测试的
<10    1
<100   11 12 13 14...21 31 41 51....
<1000 101 111 112 113 ....121 131...
今天回家再仔细想想

flw

还有个问题，什么叫做“下一个最大的”？
难道这个是有最大值的？

b46

原帖由 flw 于 2006-3-29 17:04 发表
还有个问题，什么叫做“下一个最大的”？
难道这个是有最大值的？

恩，这个确实是个BUG

yzc2002

原帖由 flw 于 2006-3-29 16:50 发表
唔……Haskell 学的不好，上面那个程序太慢了，
下面换个 Python 的，这个应该快一些：
[code]i=1
sum=0

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

这两个还差不多能看懂个70%,前面那个完全不明白是啥~~~
flw你会那么多的语言,不会搞混了么?