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

xiongyingyx

不知道搂主的答案是什么，小弟试验了几个算法，最后选出了一个，但是速度还是不够快，从1计算到0x4FFFFFFF用了大概是37s。迫切的想知道大虾的高见~

#define MAX 0x4FFFFFFF

void f(int start=1)
{
#define N 10

        char array[N];
                                                                                                                  
        unsigned int i;
       
        unsigned int iCount=0;

        char* p;
        int c;

        memset(array,0,N);

        for(i=1; i<MAX; i++)
        {
                p = &array[N-1];

                while(*p == 9)        *p-- = 0;

                (*p)++;

                c = 0;

                p = array;
               
                while(p < &array[N])
                        if(*p ++ == 1) c++;

                iCount += c;

                if(i==iCount)
                        printf("%u\n",i);
        }
        printf("Over...\n");

}

choki

vc6.0

1. #include <stdlib.h>
   
2. #include <stdio.h>
   
3. //#include <iostream.h>
   
4. #include <string.h>
   
5. //#include <ctype.h>
   
6. //#include <conio.h>
   
7. #include <time.h>
   
8. #define  NUMBER  99999999999  //终点
   
9. #define  START   2    //起点
   
10. 
    
11. 
    
12. long one_count(long stop)
    
13. {
    
14.         int  num;
    
15.         long i;
    
16.         long count=0;
    
17.         char sData[12];
    
18. 
    
19.         for(i=1 ; i<=stop ;i++)
    
20.         {
    
21.                 memset(sData , 0 , sizeof(sData));
    
22.                 sprintf(sData , "%-ld" , i);
    
23. //                printf("sData:[%s]\n",sData);
    
24.                 num=0;
    
25.                 while( sData[num] != NULL )
    
26.                 {
    
27.                         if( sData[num] == '1')
    
28.                         {
    
29.                                 count++;
    
30.                         }
    
31. 
    
32.                         num++;
    
33.                 }
    
34.                        
    
35. //                printf("count:[%ld]\n",count);
    
36. 
    
37.         if( (i == count) && (i>START) )
    
38.                 {
    
39. //                        printf("found:[%ld]\n",i);
    
40.                         return(i);
    
41.                 }       
    
42.         }
    
43.        
    
44.         return(2);
    
45. }//one_count func end
    
46. 
    
47. int main(void)
    
48. {
    
49. 
    
50.         long zzz;
    
51.         char timebuf1[20];
    
52.         char timebuf2[20];
    
53. 
    
54. 
    
55.         memset( timebuf1 , 0 , sizeof(timebuf1));
    
56.         memset( timebuf2 , 0 , sizeof(timebuf2));
    
57.         _strtime(timebuf1);
    
58. 
    
59. 
    
60.         zzz=one_count(NUMBER);
    
61.         if( zzz == 2 )
    
62.         {
    
63.                 printf("No found.\n");
    
64.         }
    
65.         else
    
66.                 printf("Found [%ld]\n",zzz);
    
67. 
    
68.         _strtime(timebuf2);
    
69. 
    
70.         printf("time1[%s].\n" ,timebuf1);
    
71.         printf("time2[%s].\n" ,timebuf2);
    
72. 
    
73.     return 0;
    
74. }

复制代码

结果：
Found [199981]
time1[16:50:39].
time2[16:50:39].
Press any key to continue...

算是得到结果啦
没用递归

eastsun-2006

贴个算单个数的，找出所有的楼主是怎么实现的，遍历也不止一秒啊！
#include <math.h>
#include <windows.h>
#include <iostream>
using namespace std;

int find_low_power(int num)
{
        int power = 0;
        while(pow(10,power) <= num)
        {
                power ++;
        }
        return power - 1;
}

int fullnum(int power)
{
        return (int)(power*pow(10,power - 1));
}

int find(int num)
{
        int count = 0;
        if(num == 0)
        {
                return 0;
        }
        if((0 < num) && (num < 10))
        {
                return 1;
        }
        int low_power = find_low_power(num);
        if((num - pow(10,low_power) < pow(10,low_power)))
        {
                count += (num - (int)pow(10,low_power) + 1);
                count += fullnum(low_power);
                count += find(num % (int)pow(10,low_power));
        }
        else
        {
                count += (int)pow(10,low_power);
                count += (num/(int)pow(10,low_power))*fullnum(low_power);
                count += find(num % (int)pow(10,low_power));
        }
        return count;
}

int main(int argc, char* argv[])
{
        int num;
        while(1)
        {
                cout << "please input a num!" << endl;
                cin >> num;
                if(num < 0)
                {
                        num = -num;
                }
                unsigned long time = GetTickCount();
                cout << find(num) << endl;
                cout << "use time:" << (GetTickCount() - time) << "milli-second" << endl;
        }
        return 0;
}

xiaonanln

谁能解释下，什么叫 What is the next largest n such that f(n)=n?  
next n such that f(n)=n 就是下一个f(n) = n
largest n such that f(n)=n就是最大的f(n)=n
next largest又是什么意思？？？

Momoass

靠死历遍的效率是很低的，要用统计学。

大大狗

学习了..

jiajs

原帖由 Momoass 于 2006-6-16 12:50 发表
靠死历遍的效率是很低的，要用统计学。

怎么统计？不是一个一个算下来的怎么保证你的是正确的？

freebingo

楼主理解的优点问题吧，What is the next largest n such that f(n)=n?  求一个，而不是列出所有的！可能要求的算法不一样哦。

周若水

经典，拿回家学习

michaelds

今天无意中搜到了这个帖子，Google出的题就是有味道，在尝试后发现确实考得有独到之处。纵览所有回帖，楼主对该问题是最深入，最细致，也是最接近完美答案的。
不过当把一个问题拆解到统计学的这种角度，程序本身的趣味性就快要索然无味了，正如如果我们求解费波纳契数列，最快的方法莫过于推导出通项公式，然后求解，那再写程序本身还有很大的意思吗？楼主的探索精神，我十分赞赏，通过自己推导，我终于找到了一个漂亮的解决方法，性能未必比楼主的强多少，但是可读性和欣赏性一定是强一些，我猜想这个方法也是Google出这道题的原意。需要一点预先的证明工作，不过不用繁琐的符号推导，我们只需坐而论道，就可得证，然后付诸编码，代码也短而整齐。
我用Python实际做了一下，如果打印出所有结果，大致需要0.95秒，如果只记录不打印，只需0.28秒，如果按照题目的意思只找出最大的那一个，那就不到0.1秒了。
我请对这个问题仍怀有兴趣的朋友再来重新考虑这个问题吧，我暂且先卖个关子不说，特别是楼主，其实你的方法还差一半就可以得到这个更漂亮一些的方法。你是最接近的人，不妨再试一试吧。我相信通过自身努力找到这个方法的人都会为它本身的漂亮而喜悦良久。