一道面试题

yikaikai

见<<具体数学>> 1.3
有详细的数学分析

erlangs

这种帖子在C版已经说了好几次了吧,用数学逆推

w_anthony

发一个看似笨拙，但实际上进行较大数计算很有效的方法，n = 1000时，结果是603。

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. int main(int argc, char** argv)
   
6. {
   
7.         const int n = 1000;
   
8.         for (int i = 0; i < n; i++)
   
9.         {
   
10.                 int l = i, s = n, c = 2;
    
11.                 while ((l % 3 != c) && (s > 1))
    
12.                 {
    
13.                         const int a = 2 - c;
    
14.                         l -= (l + a) / 3;
    
15.                         c = 2 - (s + a) % 3;
    
16.                         s -= (s + a) / 3;
    
17.                 }
    
18.                 if (s <= 1)
    
19.                 {
    
20.                         printf("result = %d\r\n", i);
    
21.                         break;
    
22.                 }
    
23.         }
    
24.         return 0;
    
25. }
    

复制代码

测试了下，当n=1000000000时，计算经过了2-3分钟，结果是672612259。这种较大数计算，如果是链表的方法，是算不出结果的。

tempname2

见 1.3
有详细的数学分析
yikaikai 发表于 2011-02-24 09:09

这些知识对一般程序员有什么用？修养？

robin254817

回复 13# w_anthony


    我用笨法单向循环链表，求得左后删除的是705.链表最后剩余225和603.

w_anthony

回复  w_anthony


    我用笨法单向循环链表，求得左后删除的是705.链表最后剩余225和603.
robin254817 发表于 2011-02-24 14:25

705删掉以后，还剩两个，要继续删，最后删的是225。不过我那方法完全不知道删的过程……

duwei211

楼主不是和我面试的一家公司吧，我用的循环单链表