Yukang's Page

一个小题目

2010-08-02

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

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



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

file:///home/heipang/document/wiki/Home_Page/Computer/笔试题.html

//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;
}


使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章