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

梦蓝

unsigned long long int subf(unsigned long long int n)
{
        if(n==1) return 1;
        else if(n<10) return 0;
        else return subf(n/10)+subf(n%10);
}

unsigned long long int f(unsigned long long int n)
{
        if(n<=0) return 0;
        else return subf(n)+f(n-1);
}

niqingliang2003

static int[] aQuotient;     //存放商
        static int[] aRemain;       //存放余数
        static int iDigit;          //存放整数的十进制位数

        static void Initial()
        {
            aRemain = new int[10];
            aQuotient = new int[aRemain.Length + 1];
            iDigit = 0;
        }

        static int Cope(int i)
        {
            Arrange(i);
            return Compute(iDigit - 1);
        }
        static void Arrange(int iInput)
        {
            int i = 0;          //循环变量，计数用
            //初始化
            aQuotient[0] = iInput;
            aRemain[0] = 0;

            for (i = 0; ; i++)
            {
                aRemain[i] = aQuotient[i] % 10;
                if (aRemain[i] == aQuotient[i])
                    break;
                aQuotient[i + 1] = aQuotient[i] / 10;
            }
            iDigit = i + 1;
            aQuotient[0] = 0;
            aQuotient[1] = aRemain[0];

            for (i = 2; i <= iDigit; i++ )
            {
                aQuotient[i] = aRemain[i - 1] * (int)Math.Pow(10,i - 1) + aQuotient[i - 1];
            }
        }

        static int Compute(int i)
        {
            int iCommon = 0;
            if (i == 0)
            {
                if (aRemain[0] == 0)
                    return 0;
                else
                    return 1;
            }
            if (aRemain[i] == 0)
                return Compute(i - 1);
            iCommon = (i) * (int)Math.Pow(10, (i - 1)) * aRemain[i] + Compute(i - 1);
            if (aRemain[i] == 1)
            {
                return aQuotient[i] + 1 + iCommon;
            }
            return (int)Math.Pow(10, i) + iCommon;
        }
    }

0000000009

我的程序:只能返回1~n之间 1 的个数。

1. 
   
2. int f(int t, int station, int i_right)
   
3. {
   
4.         int current = 0;
   
5. 
   
6.         current = pow(10, station-1 ) * station * t;
   
7. 
   
8.         if(t > 1)
   
9.                 current += pow(10, station);
   
10.         else  // t == 1;
    
11.                 current += i_right + 1;
    
12. 
    
13.         return current;
    
14. };
    
15. 
    
16. 
    
17. //----------------------------------------------------------------------
    
18. int _tmain(int argc, _TCHAR* argv[])
    
19. {
    
20.        
    
21.         int count = 0;
    
22.         int station = 1;
    
23.         int i = 0;
    
24.         int i_right = 0;  //从当前那位开始右边的数字
    
25. 
    
26.         cout << "enter a number, please:"<< endl;
    
27.         cin >> i;
    
28. 
    
29.         if(i < 0)
    
30.                 i = -1 * i;
    
31. 
    
32.         if(!i)
    
33.         {
    
34.                 cout << "result is:0" << endl;
    
35.                 return 0;
    
36.         }
    
37. 
    
38.         if(i < 10)
    
39.         {
    
40.                 cout << "result is:1" << endl;
    
41.                 return 0;
    
42.         }
    
43. 
    
44. int i_for_SecondMethod = i;
    
45. 
    
46. 
    
47.         if(i_right = i % 10)
    
48.                 count++;
    
49. 
    
50.                 i /= 10;
    
51. 
    
52.                 int t = i % 10;
    
53.                 int t2 = i;
    
54.                
    
55. 
    
56.                 while(t2)
    
57.                 {
    
58.                         while(!t)
    
59.                         {
    
60.                                 t2 /= 10;
    
61. 
    
62.                                 t = t2 % 10;
    
63.                                 station++;
    
64.                         }
    
65. 
    
66.                 i_right += t * pow(10, station) + i_right;
    
67. 
    
68.                         count += f(t, station, i_right);
    
69. 
    
70.                         t2 /= 10;
    
71.                         t = t2 % 10;
    
72.                         station++;
    
73. 
    
74.                 }
    
75. 
    
76.                 cout << "result:" << count << endl;
    
77. 
    
78. 
    
79.         return 0;
    
80. }
    
81. 
    

复制代码

luojiannx

汗,那么多深度递归的,google的题目如果这么草草应付个谁都想得到的答案,那是肯定没戏的

flw估计也没吧

呵呵,别生气,或者考官看你会n国语言,没准考虑给你加分的

0000000009

原帖由 luojiannx 于 2006-4-15 18:48 发表
汗,那么多深度递归的,google的题目如果这么草草应付个谁都想得到的答案,那是肯定没戏的

flw估计也没吧

呵呵,别生气,或者考官看你会n国语言,没准考虑给你加分的

是指我吗?我没用递归

seaheart

我的想法是得到数(abcdefg...)中某一位为1且不大于该数的数目, 遍例所有位, 求和得到0到数字abcdefg之间含有1的个数。f(n)函数时间复杂度是log10(n).
这里还少一个对最大数字判断的算法（淘汰部分马上可确认n != f(n)的数）

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <math.h>
   
5. 
   
6. using namespace std;
   
7. 
   
8. int f(int n)
   
9. {       
   
10.         int total = 0;       
    
11.         int m = ((int) log10(n)) + 1; //m是n的数字位数
    
12.        
    
13.         int ax;
    
14.         float fn = (float) n;
    
15.         for (int x=0; x<m; x++)  // 假设数字是[a0 a1 a2 ... ax ... am](a0,a1,a2...代表每一位)
    
16.         {               
    
17.                 int num = 0;
    
18.                 ax = (int) (n / (int) pow(10, m-1-x)) % 10; //第x位的数
    
19.                
    
20.                 int n_begin = (int) floor(fn /pow(10, m-x)); // ax之间的数字[a0...a(x-1)]               
    
21.                 switch (ax)
    
22.                 {
    
23.                         case 0: //0时 直接取[a0 a1 a2 .. a(x-1) 0 0 0...](m-x-1个0)
    
24.                         {
    
25.                                 num = n_begin * ((int) pow(10, m-x-1));
    
26.                                 break;
    
27.                         }
    
28.                         case 1: //1 比0的情况多了[a(x+1) ... am]个数
    
29.                         {
    
30.                                 num = n_begin * ((int) pow(10, m-x-1));
    
31.                                 int n_end = (int) floor(n % ((int) pow(10, m-x-1)));
    
32.                                 num = num + n_end;
    
33.                                 break;
    
34.                         }
    
35.                         default: // 其他的情况 为[a0 a1 a(m-1) + 1]*(10^(m-x-1))
    
36.                         {
    
37.                                 num = (n_begin + 1) * ((int) pow(10, m-x-1));
    
38.                                 break;
    
39.                         }
    
40.                 }
    
41.         }
    
42. 
    
43.         if (total == n) printf("%d\n", n);
    
44.         return total;
    
45. }
    
46. int main()
    
47. {
    
48.         for (int i=0; i<99999999; i++)
    
49.         {
    
50.                 f(i);
    
51.         }       
    
52.         return 0;
    
53. }
    

复制代码

[ 本帖最后由 seaheart 于 2006-4-19 10:10 编辑 ]

rihua

狗屁东西

marinekiller

这道题不难，甚至可以说很简单，重要的是速度，怎么好像很多人都没有意识到呢？
楼主说不用一秒钟算出给出结果，说实在的我不信！

还有大家不要只是给出程序，把运行结果也贴上来，好用来比较......

yzc2002

呵~没想到这贴会被水成这样。。。
请版主取消精华，锁贴，让它沉了吧！
不然，会被同行瞧不起的~~

converse

原帖由 rihua 于 2006-4-19 13:02 发表
狗屁东西

你说话注意点啊,不喜欢可以不要进来说话,谢谢