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

yzc2002

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

有最大值的啊
我给的结果就是全集

b46

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

有最大值的啊
我给的结果就是全集

只是部分数据的全集
呵呵

yzc2002

原帖由 b46 于 2006-3-29 17:12 发表

只是部分数据的全集
呵呵

什么意思?
就是说除了我列出的数外,不可能有别的解了,所以叫全集

b46

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

什么意思?
就是说除了我列出的数外,不可能有别的解了,所以叫全集

你证明过了？

stonepct

最笨的办法,
PS: 运行环境为在windows xp下 vs2005 cl.exe compiler，默认编译/优化选项 release binary
amd sempron2800 + ５１２Ｍ，　ＨＰ笔记本
findallone(100)时，没算出，等了２分钟，ｃｐｕ１００％　

1. 
   
2. #include "stdafx.h"
   
3. #include "windows.h"
   
4. 
   
5. 
   
6. int findone(long t)
   
7. {
   
8.         int theunit = 0;
   
9.         int count = 0;
   
10.         while(t>0)
    
11.         {
    
12.                 theunit = t%10;
    
13.                 if(theunit == 1)
    
14.                         count++;
    
15.                 t = t/10;
    
16.         }
    
17.         return count;
    
18. }
    
19. 
    
20. void findallone(int count)
    
21. {
    
22.         DWORD time = 0;
    
23.         long n =13;
    
24.         long sumofone=6;
    
25.         int i = 0;
    
26.         for( ; i<count; i++)
    
27.         {
    
28.                 time = GetTickCount();
    
29.                 while(n != sumofone)
    
30.                 {
    
31.                         n++;
    
32.                         sumofone += findone(n);
    
33.                 }
    
34.                 time = GetTickCount()-time;
    
35.                 printf("%3d: need time:%5d; the value:%d\n",i+1,time, n);
    
36.                 n++;
    
37.                 sumofone += findone(n);
    
38.         }
    
39.         return ;
    
40. }
    
41. 
    
42. int _tmain(int argc, _TCHAR* argv[])
    
43. {
    
44.        
    
45.         findallone(40);               
    
46.         return 0;
    
47. }
    

复制代码

结果：
1: need time:    0; the value:199981
2: need time:    0; the value:199982
3: need time:    0; the value:199983
4: need time:    0; the value:199984
5: need time:    0; the value:199985
6: need time:    0; the value:199986
7: need time:    0; the value:199987
8: need time:    0; the value:199988
9: need time:    0; the value:199989
10: need time:    0; the value:199990
11: need time:    0; the value:200000
12: need time:    0; the value:200001
13: need time:   62; the value:1599981
14: need time:    0; the value:1599982
15: need time:    0; the value:1599983
16: need time:    0; the value:1599984
17: need time:    0; the value:1599985
18: need time:    0; the value:1599986
19: need time:    0; the value:1599987
20: need time:    0; the value:1599988
21: need time:    0; the value:1599989
22: need time:    0; the value:1599990
23: need time:   78; the value:2600000
24: need time:    0; the value:2600001
25: need time: 1172; the value:13199998
26: need time: 2469; the value:35000000
27: need time:    0; the value:35000001
28: need time:   31; the value:35199981
29: need time:    0; the value:35199982
30: need time:    0; the value:35199983
31: need time:    0; the value:35199984
32: need time:    0; the value:35199985
33: need time:    0; the value:35199986
34: need time:    0; the value:35199987
35: need time:    0; the value:35199988
36: need time:    0; the value:35199989
37: need time:    0; the value:35199990
38: need time:    0; the value:35200000
39: need time:    0; the value:35200001
40: need time: 9750; the value:117463825

yzc2002

原帖由 b46 于 2006-3-29 17:16 发表

你证明过了？

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

b46

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

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

呵呵
没想到这样把答案骗到了，意外
不管怎么样，拿回家研究研究
多谢了

yzc2002

如果能看懂上面的证明，那下面的这个程序就很自然了

1. long long f(long long n)
   
2. {
   
3.     int k;
   
4.     long long e, m = n, r;
   
5.     if(n <= 1) return n;
   
6.     for(k=0, e=1; m >= 10; k++, e *= 10) m /= 10;
   
7.     r = n - m*e;
   
8.     if(m == 1)
   
9.         return(e/10*k+r+1+f(r));
   
10.     else
    
11.         return(e/10*k*m+e+f(r));
    
12. }
    
13. 
    
14. int digit_num(long long n)
    
15. {
    
16.     int k;
    
17.     for(k=0; n > 0; k++) n /= 10;
    
18.     return k;
    
19. }
    
20. 
    
21. int main()
    
22. {
    
23.     int k;
    
24.     long long n, v;
    
25.     for(n = 1; n<10000000000;)
    
26.     {
    
27.         v = f(n);
    
28.         if(v == n) {
    
29.             printf("%lld\n", n);
    
30.             n++;
    
31.         }
    
32.         else if(v > n) n = v;
    
33.         else {
    
34.             k = digit_num(n + n - v);
    
35.             n += (n-v)/k + 1;
    
36.         }
    
37.     }
    
38. }

复制代码

[ 本帖最后由 yzc2002 于 2006-4-3 12:49 编辑 ]

yzc2002

原帖由 b46 于 2006-3-29 17:23 发表

呵呵
没想到这样把答案骗到了，意外
不管怎么样，拿回家研究研究
多谢了

:em12::em12::em12:

b46

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

:em12::em12::em12:

智者千虑，必有一失