肥康

前些天在班级群里看到一个笔试题：

从1到100000中任意拿掉两个数字，把剩下的99998个数顺序打乱，并且放入数组A中。要求只扫描一遍，把这两个数找出来；可以使用最多不超过5个局部变量，不能使用数组变量，并且不能改变原数组的值。

也想不到什么更好的解法，原解法是顺序扫一边求得所有数的乘积(mul_res)、和(sum_res)。用(N!)/mul_res得到两个数的乘积，1到100000的和减去sum_res得到两个数之和。 解这个方程得到两个数。关键是N!太大了，C会溢出。刚开始想想乘积每次模100000，后来写了一下还是不对的，因为模100000中可能就出现了0，后面全为0了。最后想到这么一个办法，不过中间 除法和比较多。也许有更快的解法。

//1到100 000
#include <iostream>
#include <math.h>

using namespace std;
#define N 100000
typedef long long LL;

LL a;
LL b;
LL vec[N];
int cnt;
LL  MAX_MUL;

void Find(const LL* vec)
{
    int sum=0;
    LL  mul=1;
    LL  Now=1;
    for(int i=0;i<cnt;i++)
    {
        sum+=vec[i];
        while(mul%vec[i]!=0)
            mul*=(++Now);
        mul/=vec[i];
    }
    while(Now<100000)
         mul*=(++Now);
    LL diff=((1+N)*N)/2-sum;
    cout<<diff<<" "<<mul<<endl;
    LL a=(diff+sqrt(diff*diff-4*mul))/2;
    cout<<a<<" "<<diff-a<<endl;
}

int main()
{
    srand(time(NULL));
    a=(rand()%100000)+1;
    b=(rand()%100000)+1;
    cnt=0;
    for(int i=1;i<=N;i++)
    {
        if(i!=a&&i!=b)
            vec[cnt++]=i;
    }
    cout<<a<<" "<<b<<" "<<endl;
    cout<<a+b<<" "<<a*b<<endl;
    Find(vec);
}

———————————————————-
经熊师兄指点，上面的解法还是不对，如果vec前面刚好为比较大的素数，mul就溢出了。正确的解法应该为求x+y=B, x^2+y^2=A, 1-100000的平方和可以用double存下来，然后减去vec里面的平方和就得到x^2+y^2的值。

void Find(const LL* vec)
{
    double sum=0;
    double  square_sum=0;
    for(int i=0;i<cnt;i++)
    {
        sum+=vec[i];
        square_sum+=(vec[i]*vec[i]);
    }
    double diff=((1+N)*N)/2-sum;
    double square_sum_diff=
        ((double)N*(N+1)*(2*(double)N+1))/6 - square_sum;
    cout<<diff<<" "<<square_sum_diff<<endl;
    a=(2*(diff)+sqrt(8*square_sum_diff-4*diff*diff))/4;
    cout<<a<<" "<<diff-a<<endl;
}

随机日志

• Find duplicated Number and Cycle detection (0)
• 常听的一首歌 (0)
• 让Emacs提醒睡觉 (0)
• 给老婆介绍OOD (3)
• 读memcached (2)
• 优化算法 (3)
• 近期 (3)
• The Game of Life (0)
• 从豆瓣FM下载喜欢的音乐 (4)
• 又是一些歌 (1)

Tags: 笔试题

This entry was posted on 星期一, 八月 2nd, 2010 at 7:54 上午 and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.