[算法]Google的面试题

auyeung

1. 
   
2. #include <stdio.h>
   
3. int main()
   
4. {       
   
5.         long f(long m);
   
6.         long i=1,y=1;
   
7.         do
   
8.         {
   
9.                 if (i==f(i)) printf("the %ld number is:%ld\n",y++,i);
   
10.                 i++;
    
11.         }
    
12.         while(1);
    
13.         return 0;
    
14. }
    
15. 
    
16. long f(long m)
    
17. {
    
18.         long s,sum,m_c,count;
    
19.         sum=0;
    
20.         s=0;
    
21.         count=1;
    
22.         do
    
23.         {       
    
24.                 m_c=m%10;
    
25.                 if(m_c==0)sum=sum+(m/10)*count;
    
26.                 else if(m_c==1)sum=sum+(m/10)*count+s+1;
    
27.                 else sum=sum+((m/10)+1)*count;
    
28.                 s=s+m_c*count;
    
29.                 count=count*10;
    
30.                 m=m/10;
    
31.         }
    
32.         while(m);
    
33.         return sum;
    
34. }
    
35. 
    

复制代码

初学 我也写了一个 怎么看运行时间？

auyeung

POINTER的程序看不太明白？F（N）在哪里？
怎么这么快？ 我机器运行个HELLO WORLD都要0.01+

auyeung

2. #include <stdio.h>
3. int main()
4. {       
5.         long f(long m);
6.         long i=1,y=1,k;
7.         do
8.         {
9.                 k=f(i)-i;
10.                 if (k==0) printf("the %ld number is:%ld\n",y++,i++);
11.                 else if (k>0) i=i+k;
12.                 else i=i-k;
13.         }
14.         while(i<1111111111);
15.         return 0;
16. }
17. long f(long m)
18. {
19.         long s,sum,m_c,count;
20.         sum=0;s=0;count=1;
21.         do
22.         {       
23.                 m_c=m%10;
24.                 if(m_c==0)sum=sum+(m/10)*count;
25.                 else if(m_c==1)sum=sum+(m/10)*count+s+1;
26.                 else sum=sum+((m/10)+1)*count;
27.                 s=s+m_c*count;
28.                 count=count*10;
29.                 m=m/10;
30.         }
31.         while(m);
32.         return sum;
33. }

复制代码

简单改了一下 递进方式 快是快了 不过得出的结果却漏了1，2个数  等高人讲讲

估计是递进的方法有问题 增加速度也是在这里如果直接I++要13M

Piii500 w2k cygwin

$ time ./a.exe
the 1 number is:1
the 2 number is:199981
the 3 number is:199982
the 4 number is:199983
the 5 number is:199984
the 6 number is:199985
the 7 number is:199986
the 8 number is:199987
the 9 number is:199988
the 10 number is:199989
the 11 number is:199990
the 12 number is:200000
the 13 number is:200001
the 14 number is:1599981
the 15 number is:1599982
the 16 number is:1599983
the 17 number is:1599984
the 18 number is:1599985
the 19 number is:1599986
the 20 number is:1599987
the 21 number is:1599988
the 22 number is:1599989
the 23 number is:1599990
the 24 number is:2600000
the 25 number is:2600001
the 26 number is:35000000
the 27 number is:35000001
the 28 number is:35199981
the 29 number is:35199982
the 30 number is:35199983
the 31 number is:35199984
the 32 number is:35199985
the 33 number is:35199986
the 34 number is:35199987
the 35 number is:35199988
the 36 number is:35199989
the 37 number is:35199990
the 38 number is:35200000
the 39 number is:35200001
the 40 number is:500000000
the 41 number is:500000001
the 42 number is:500199981
the 43 number is:500199982
the 44 number is:500199983
the 45 number is:500199984
the 46 number is:500199985
the 47 number is:500199986
the 48 number is:500199987
the 49 number is:500199988
the 50 number is:500199989
the 51 number is:500199990
the 52 number is:500200000
the 53 number is:500200001
the 54 number is:501599981
the 55 number is:501599982
the 56 number is:501599983
the 57 number is:501599984
the 58 number is:501599985
the 59 number is:501599986
the 60 number is:501599987
the 61 number is:501599988
the 62 number is:501599989
the 63 number is:501599990
the 64 number is:502600000
the 65 number is:502600001
the 66 number is:535000000
the 67 number is:535000001
the 68 number is:535199981
the 69 number is:535199982
the 70 number is:535199983
the 71 number is:535199984
the 72 number is:535199985
the 73 number is:535199986
the 74 number is:535199987
the 75 number is:535199988
the 76 number is:535199989
the 77 number is:535199990
the 78 number is:535200000
the 79 number is:535200001

real    0m0.161s
user    0m0.070s
sys     0m0.080s

william0218

各位说的话，我都看不懂，唉~~，自卑~~

folklore

Number N
0+1+...+log(N)=N
N=?

fuch

不好意思地说一下，高中信息学竞赛和大学的acm/icpc经常做这种题……

easycat

为什么f（13）=6？
1,2,3,4,5,6,7,8,9,10,11,12,13
明明只有5个1...

yangtsecn

Post by easycat
为什么f（13）=6？
1,2,3,4,5,6,7,8,9,10,11,12,13
明明只有5个1...

你再数数吧:beat

easycat

hoho 11 是算2 啊
我还以为1 呢 ..

fuch

Post by dabasir
谁有ACM的题目，传一份给我看看，练习一下
lynux (a) 126.com

acm的oj太多了，比如：
http://acm.pku.edu.cn/
http://acm.uva.es/problemset/
http://acm.zju.edu.cn/
http://acm.timus.ru/

我个人喜欢做后两个