哥德巴赫猜想的验证算法

yaomingwei_ren

这个是我参加华为面试时候的题目，下面是我的实现代码，面试官说思想有问题，我想请教大家一下，我的毛病究竟出现在哪里呢？请大家指点一下。下面的算法可以直接运行。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <iostream.h>
bool judge(int t)
{
        for(int i=2;i<=sqrt(t);i++)
                if(t % i == 0)
                        return false;
        return true;
}
bool find(int array[],int t,int j)
{
        int max = j-1;
        int min = 0;
        while(min <= max)
        {
                if(array[(min+max)/2] == t)
                        return true;
                if(array[(min+max)/2] > t)
                        max = (min+max)/2-1;
                else
                        min = (min+max)/2+1;
        }
        return false;
}
int f(int n)
{
        int j=0;
        int * array ;
        bool flag = false;
        array = (int *)malloc(sizeof(int)*n/2);
        for(int i=3;i<=n-3;i++)
                if(judge(i))
                        array[j++]=i;
        for(i=6;i<=n;i=i+2)
        {
                int pos = 0;
                flag = false;
                while(array[pos] <= i/2)
                {
                        if(find(array,i-array[pos],j))
                        {
                                flag = true;
                                break;
                        }
                        pos++;
                }
                if(!flag)
                        return 1;
        }
        return 0;
}
int main()
{
        int n;
        scanf("%d",&n);
        cout<<f(n);
        return 0;
}

[ 本帖最后由 yaomingwei_ren 于 2005-11-17 12:31 编辑 ]

hellhell

应该叫验证算法吧

yaomingwei_ren

对，是验证算法，今天改进了一下find和f函数
int find(int array[],int t,int j)
{
        int max = j-1;
        int min = 0;
        while(min <= max)
        {
                if(array[(min+max)/2] == t)
                        return -1;
                if(array[(min+max)/2] > t)
                        max = (min+max)/2-1;
                else
                        min = (min+max)/2+1;
        }
        return min;
}
int f(int n)
{
        int j=2;
        int * array ;
        bool flag = false;
        array = (int *)malloc(sizeof(int)*n/2);
        array[0]=3;
        array[1]=5;
        for(int i=6;i<=n;i++)
        {
                if(i%2 != 0 && judge(i))
                {
                        array[j++]=i;
                        continue;
                }else
                        if(i%2 == 0)
                        {
                                int pos = 0;
                                int pos2 = j;
                                flag = false;
                                while(array[pos] <= i/2)
                                {
                                        if((pos2=find(array+pos,i-array[pos],pos2)) == -1)
                                        {
                                                flag = true;
                                                break;
                                        }
                                        pos++;
                                }
                                cout<<i<<","<<array[pos]<<","<<i-array[pos]<<endl;
                                if(!flag)
                                        return 1;
                        }
        }
        return 0;
}

win_hate

思想有问题？ 这么严重么？

如果考官认为你算法上不合理，你把自己的算法写一下，而不是给出代码，我估计会更多的答复。

至于代码，有不少问题的，比如
(1)  c, c++ 混在一起, scanf, malloc, <<
(2)  c++ 的写法过时了，应该 include <iostream> 而不是 <iostream.h>, 应该 using namespace std.
(3)  malloc 之后没有 free

yzc2002

2个问题:
(1)用大小为n/2的整型数组，当n很大时，内存空间的消耗很厉害。
(2)得到<=n/2的素组列表的算法太差，用筛法是最快的。

yzc2002

1. #include <iostream>
   
2. #include <vector>
   
3. #include <iterator>
   
4. #include <math.h>
   
5. 
   
6. using namespace std;
   
7. 
   
8. int next_prime(vector<int>& vPrime)
   
9. {
   
10.     int n = vPrime[vPrime.size() - 1] + 2;
    
11.     int m = (int)sqrt(2.0*n);
    
12.     for(int i = n; ; i+= 2)
    
13.     {
    
14.         vector<int>::const_iterator itr;
    
15.         for(itr = vPrime.begin(); *itr <= m && i % (*itr); ++itr);
    
16.         if(*itr > m)
    
17.         {
    
18.             vPrime.push_back(i);
    
19.             return i;
    
20.         }
    
21.     }
    
22. 
    
23. }
    
24. 
    
25. bool find(vector<int>& vPrime, const int x)
    
26. {
    
27.     int i=0, j=vPrime.size() - 1, m;
    
28.     while(i <= j)
    
29.     {
    
30.         m = (i + j) / 2;
    
31.         if(x == vPrime[m])
    
32.             return true;
    
33.         else if(x > vPrime[m])
    
34.             i = m + 1;
    
35.         else
    
36.             j = m - 1;
    
37.     }
    
38.     return false;
    
39. }
    
40. 
    
41. bool split(vector<int>& vPrime, const int sum, int &x, int &y)
    
42. {
    
43.     vector<int>::const_reverse_iterator itr;
    
44.     for(itr = vPrime.rbegin(); 2*(*itr) >= sum; ++itr)
    
45.     {
    
46.         if(find(vPrime, sum - (*itr)))
    
47.         {
    
48.             x = *itr;
    
49.             y = sum - (*itr);
    
50.             return true;
    
51.         }
    
52.     }
    
53.     int p;
    
54.     while((p = next_prime(vPrime)) <= sum - 3 )
    
55.     {
    
56.         if(find(vPrime, sum - p))
    
57.         {
    
58.             x = p;
    
59.             y = sum - p;
    
60.             return true;
    
61.         }
    
62.     }
    
63.     return false;
    
64. }
    
65. 
    
66. void check(int n)
    
67. {
    
68.     vector<int> vPrime;
    
69.     int x, y;
    
70.     vPrime.push_back(2);
    
71.     vPrime.push_back(3);
    
72.     for(int i = 6; i < n; i += 2) {
    
73.         if(split(vPrime, i, x, y))
    
74.             cout << i << " = " << x << " + " << y << endl;
    
75.         else
    
76.             cout << "false[" << i << "]!" << endl;
    
77.     }
    
78. }
    
79. 
    
80. int main()
    
81. {
    
82.     int sum;
    
83.     cin >> sum;
    
84.     check(sum);
    
85. }
    

复制代码

yaomingwei_ren

感谢大家的指导！尤其感谢yzc2002给出的实现，让我发现差距真的很大！我的C/C++实在是太差了，这样的水平去华为被鄙视也是属于应该！（刚开始我觉得还挺冤的）看来真要好好学习一下C/C++还有数据结构。yzc2002给出的算法时间复杂度要不我的小很多，充分利用了已经求出的素数，真的很巧妙！十分感谢！

mq110

我怀疑 yzc2002 是搞大型游戏开发的