您的位置：程序门 -> 专题开发/技术/项目 -> 数据结构与算法

微软最新面试题求解

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

微软最新面试题求解[已结贴,结贴人:libihui422]

发表于：2007-02-03 23:24:49 楼主

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

发表于：2007-02-04 01:04:561楼得分:0

x+y=a
x*x+y*y=b

1+2-a[1]-a[2]+3+4-a[3]-a[4]

发表于：2007-02-04 09:58:462楼得分:10

混沌宝宝闯江湖！第一帖！

********************
设拿掉的两个数为a，b。
则有1000，000> = a > =1；1000，000 > = b > =1，且a！=b。
通过遍历数组得：sum1（999998个数的和），multi1（999998个数的积）。
又有sum2（1000，000个数的和），multi2（1000，000个数的积）。
则：a+b=sum2-sum1；a*b=multi2/multi1。
则可以构造二元一次方程：x*x-（a+b)*x+a*b=0,则方程的两个解为a，b。方程的解可以用公式来求。

关于所加的数和所乘的数特别的大时：
1：用long double 型来存储。
2：在每步做加时，同时，做减。例如：a[1]，同时做a[1]-1000，000。a[1]+a[2]，同时做a[1]+a[2]-1000，000-999，999。
3：在每步做乘，同时，做除法。如果有除不尽的，可以一个就这么做，得到一个不准确的值，也可以将要做的数，先存起来，等可以除尽时再做除法（尤其是遇到质数时）。
************************

混沌宝宝闯江湖！第一帖！

发表于：2007-02-04 10:25:063楼得分:0

ls可行性几乎为零

发表于：2007-02-04 10:49:294楼得分:0

混沌宝宝闯江湖！第二帖！

***********
void gettwonumbers （vector <int> &numberarray,long double &sum2,long double &multi2)
{
//i用来做循环使用，temp存放不可整除的数的积
//sum2存放做加与减的结果，multi2存放做乘与除的结果
long double i = 0;
long double temp = 1;
sum2 = 0;
multi2 = 1;

for （i = 999997;i > = 0;--i){
sum2 += i;
sum2 -= numberarray [i];

multi2 *=i;
if （multi2 % a[i])
multi2 /= a[i];
else
temp *= a[i];
}
sum2 += 1000000 + 999999 + 999998;//此时的sum2为a+b
multi2 *= 1000000 * 999999 * 999998;
multi2 /= temp;//此时的multi2为a*b

for （ i = 1;i != static_cast <int> （ sqrt （multi2)) + 1;++i){
if （multi2 % i)
if （（i + multi2 / i) == sum2){
sum2 = i; //sum2存放了a
multi2 /= i;//multi2存放了b
break;
}
}

}
**************

混沌宝宝闯江湖！第二帖！

发表于：2007-02-04 11:07:365楼得分:0

混沌宝宝闯江湖！第三帖！

******************
貌似楼主，该问题是要给20分的吧？
请看以上解答，如果觉得还可以，就请给我分吧。
谢谢！

ps：本人初到csdn，才开始混江湖，经验值和分很少。同时经常看到好多好多好心的大大在散分，心中激动不已，这世界还是好人多啊。另外，如果各位大大再散分的话，请考虑我哦。小弟万分感激！！
先在这里谢过各位思想活，境界高的xdjm了。
**************

混沌宝宝闯江湖！第三帖！

发表于：2007-02-04 11:13:446楼得分:0

混沌宝宝闯江湖！第四帖！

*************
yaunx（杨) （ ) 信誉：100 blog 2007-02-04 10:25:06 得分: 0

ls可行性几乎为零

ps：ls是什么意思，另外，请给出可行性为0的理由。
谢了。
**************

混沌宝宝闯江湖！第四帖！

发表于：2007-02-04 20:06:367楼得分:0

全部乘起来就题意来说是不可能的，只是两个变量肯定溢出
只是2、3个相乘还凑合
应该是求
m=a+b（2个临时变量）
n=a*a+b*b（2个临时变量）
（a-b)^2=2n-m^2

发表于：2007-02-05 18:32:488楼得分:0

/*
name: 微软最新面试题
copyright: your company
author: wizardblue
date: 05-02-07 18:03
description: 齐次线性方程组
齐次线性方程组在数值分析中应该有更简单的解法，
不过偶忘记掉了，由于10^6刚刚可以穷举，所以解
x+y = c
x^0.9+y^0.9=c2的时候，采用穷举试算，如果你觉得
这个太ugly,自行修改 :p.
*/
#include <iostream>
#include <cmath>
using namespace std;
int main（){
long max =1e6;
long n0= rand（)%max;
long n2 = rand（)%max;
cout < < "n0: " < <n0 < <endl;
cout < < "n2: " < <n2 < <endl;
double c = 0;
double c2 = 0;
long i =0;
for（i=1;i <max+1;i++){
c +=i;
c2 +=pow（i,0.9);
}
long x ,y;
for（i=1;i <max+1;i++){
if（i==n0 ¦ ¦ i==n2)continue;
c -= i;
c2 -=pow（i,0.9);
}
cout < < "c: " < <c < <endl;
cout < < "c2: " < <c2 < <endl;

double epsilo = max;

for（i = 1;i <max+1;i++){
double v = pow（c-i,0.9)+pow（i,0.9);
if（abs（v-c2) <epsilo){
epsilo = abs（v-c2);
y = i;
}
}

cout < < "y: " < <y < <endl;
cout < < "x: " < <c-y < <endl;

return 0;
}

发表于：2007-02-05 18:34:069楼得分:0

基本上还是按照二楼的思路,只不过把二式中的 ^2 改成了^0.9,这样就不会溢出了,然后,解方程采用的穷举,大家不要打偶就是了,微偷了点懒.

发表于：2007-02-05 18:49:3110楼得分:0

用位图表示法.申请int bitmap,搜索时将搜索到的当前值对应的bitmap中的位置1,结束后判断bitmap的值.
比较懒,只说思路,不写源代码

发表于：2007-02-05 19:35:5311楼得分:0

同意wx214083（) 的建议

发表于：2007-02-05 21:54:5512楼得分:0

设拿掉的两个数字为x，y
被拿掉数字的数组的总和为sum_a,
没拿掉数字的和为sum_b，
被拿掉数字的数组的平方和为sum2_a,
没拿掉数字的和为sum2_b，
则问题可以转换为如下的形式：
x+y=sum_b-sum_a ---1式
x*x+y*y=sum2_b-sum2_a ---2式
其中sum_a,sum_b，sum2_a,sum2_b，可以扫描一次数组得到
联立１式和２式　就可以得到x,y

发表于：2007-02-06 13:48:4913楼得分:0

楼上提到的位图表示法。

我没有找到相关的描述。

混沌宝宝闯江湖！第五帖！

******************
按我的理解，就是一个
bitset <1000000> bittemp;
然后遍历置1。

不过题目要求是：不能用数组变量，并且不能改变原数组的值。

这个解答貌似，使用了数组（或者相关的概念，比如：位图）。

请楼上给出解答。
谢谢。
**************

混沌宝宝闯江湖！第五帖！

发表于：2007-02-06 14:30:5914楼得分:0

mark

发表于：2007-02-06 14:50:0615楼得分:0

1-9 9个
10-99 90个
100-999 900个
1000-9999 9000个....
先确定这两个数是几位数
统计个位为0 1 2 3 4 5 6...9的数的个数
然后for 循环找出x+y=sum1-sum2

发表于：2007-02-06 14:50:5616楼得分:0

不符合题意瞎想的

发表于：2007-02-06 15:06:0217楼得分:0

给出一个解法：

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

author: njurain @feb.6 14:35pm complier:gnu cpp */

#include <iostream>
#include <cmath>
using namespace std;

int main（){
long max =1e6;
long lost1= rand（)%max;
long lost2= rand（)%max;
cout < < "lost1= " < <lost1 < < '\n ' < < "lost2= " < <lost2 < < '\n ';
double delta=0;// 1.
double multidivide=1; //2.record the result of pie （tmp/a[tmp]
long temp=1;//3 for mark

for（temp=1;temp <max+1;temp++){
delta+=temp;
multidivide*=temp;
if（temp==lost1 ¦ ¦temp==lost2)continue;//遍历
delta-=temp;multidivide/=temp;}

cout < < "delta= " < <delta < < '\n ';
cout < < "temp= " < <multidivide < < '\n ';
cout < < "--------------------caculating------------------- " < < '\n ';
cout < < "the two numbers are: " < < '\n ' < <int（（delta-sqrt（delta*delta-4*multidivide))/2) < < '\n '
< <int（（delta+sqrt（delta*delta-4*multidivide))/2) < < '\n '; //solve the equation
// lost1+lost2=delta; lost1*lost2=multidivide;

return 0;
}

发表于：2007-02-06 15:10:3918楼得分:0

only use 3 temps.

the array can be unsorted,but mine are sorted...

i am lazy..

results:

lost1=41
lost2=18467
delta=18508
temp=757147 // 大错了一个单词。。。不好意思啊
--------------------caculating-------------------
the two numbers are:
41
18467

terminated with return code 0
press any key to continue ...

// 打错一个字：倒数第八行应该是：cout < < "multidivide= " < <multidivide < < '\n ';

发表于：2007-02-06 15:14:4719楼得分:0

用二叉排序树
if（父亲节点-左孩子> =2)
{
if（父亲节点-左孩子=2)
{
x=父亲节点-> data-1;
递归找下个数;
}
if（父亲节点-左孩子> 2)
{
x=父亲节点-> data-1;
y=父亲节点-> data-2;return;
}
}
if（右孩子-父亲> =2))//和上面相反

发表于：2007-02-06 20:57:0520楼得分:0

@ wizardblue（) （ )
把0.9 次方换成 0.5 次方就可以用求根公式来求了
@renzaijiang
怎么用二差排序树？？

发表于：2007-02-06 21:35:3921楼得分:0

--> shinstone,你帮忙写一个吧,求根的公式偶也不知道,偶看见是1e6么就直接秒杀了,呵呵

发表于：2007-02-06 22:52:5822楼得分:0

我只用3个变量就解决了呀。。。

貌似这里用英语就被鄙视了。。。
上面有贴代码。

想法就是：阶乘会溢出，所以及时的把已经找到的除掉，就可以了。
最后知道 a*b, a+b,直接求 a,b.

发表于：2007-02-06 23:10:0723楼得分:0

ls没搞错吧?

发表于：2007-02-06 23:21:5524楼得分:0

关键是你的a*b是怎么算的，给你一个数组算的话，很难不溢出

发表于：2007-02-06 23:50:0425楼得分:0

是会溢出的。。。
马虎了。。

我再换个方法，变量可以再少点的，虽然意义不大。。

发表于：2007-02-07 13:06:0226楼得分:0

/*
name: 微软最新面试题
copyright: your company
author: oversense ,wizardblue, shinstone（按发帖顺序)
date: 05-02-07 18:03
07-02-07 12:39

description: x+y = c1
sqrt（x)+sqrt（y) = c2;
联立方程求解x,y;
@version 1.0 按oversense的想法，把其中的^2改成0.9次,防止中间结果溢出
@version 1.1 按shinstone的建议,把^0.9 改成0.5次,使可由求根公式得到x,y

*/
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

long max_size = 1000000;
double coeff = 0.5;

vector <int> data = vector <int> （max_size);
vector <int> res = vector <int> （2);

void producedata（){

for（long i=0;i <max_size;i++){
data[i]=i+1;
}
long n1= rand（)%max_size ;
long n2 = rand（)%max_size ;
cout < < "the remove data are: " < <n1 < < ", " < <n2 < <endl;
data.erase（data.begin（)+n1-1,data.begin（)+n1);
data.erase（data.begin（)+n2-1,data.begin（)+n2);
}

void solve（){
double c1 = 0;
double c2 = 0;
double c3 = 0;
long i =0;
for（i=1;i <max_size +1;i++){
c1 +=i;
c2 +=pow（i,coeff);
}
for（i=0;i <data.size（);i++){
c1 -= data[i];
c2 -= pow（data[i],coeff);
}

c3 = （c1-c2*c2)*（c1-c2*c2);

double va = 4;
double vb = -4*c1;
double vc = c3;

double x1 = （-vb+sqrt（vb*vb-4*va*vc))/2/va;
double x2 = （-vb-sqrt（vb*vb-4*va*vc))/2/va;

res[0] = （int)x1;
res[1] = （int)x2;

}

int main（){
producedata（);
solve（);
cout < < "the solution is: " < <res[0] < < ", " < <res[1] < <endl;
system（ "pause ");
return 0;
}

发表于：2007-02-07 13:07:3027楼得分:0

用链表排序再搜索不知是否符合他说的要求

发表于：2007-02-07 14:16:3628楼得分:0

遍历数组，求出两数之和，同时将数组中的数放到字符变量中。
对字符串进行查找，找出不存在的数，同时求出另一个数。

发表于：2007-02-07 19:56:3529楼得分:0

提个建议：
--------建议在贴的代码的时候先描述一下算法
这样比较容易阅读些，单看代码看的有点眼花，而且不容易看懂，毕竟不是自己写的东西，不容易看懂。

发表于：2007-02-07 19:57:1230楼得分:0

只能用5个简单变量且不能改变源数组。很多人没认真看

发表于：2007-02-07 21:55:2531楼得分:0

我的方法:

五个变量:
sum_even = 所有偶数和;
sum_odd = 所有奇数和;
sqr_even = 所有偶数平方和;
sqr_odd = 所有奇数平方和;
这些数可以通过n（1,000,000,任意n),用公式即可求,相信不用多说.

扫描数组,奇偶数在对应项上减去相应值.
eg: 设扫描到的数m为偶数.
则sum_even -= m;
sqr_even -= m^2;

设拿掉的两个数为x,y.
若x,y一奇一偶.则,sum_even sum_odd已经分别是x,y.
否则,不妨设x,y均偶,则x+y = sum_even.
x^2+y^2 = sqr_even.
解议程,亦可得x,y.

发表于：2007-02-07 23:11:2532楼得分:0

请问在使用x^0.9+y^0.9=c2方法解的时候，多次求根多次累加，是否存在由于误差而导致的错误呢？

偶学c时间不长，也没学过什么高级的算法，我写了一个不知道有什么问题不，大家给看看
void seach（long a[]){

long t,s,t2,s2,i;

s=500000*1000001;//1000000个数的和

for（t=1,i=2;i <=1000000;i++)
t=t^i;//1000000个数的按位异或

for（s2=a[0],t2=a[0],i=1;i <999997;i++)
{
t2^=a[i];
s2+=a[i];
}//数组中的数的和，按位异或

for（i=1;i <（s-s2)/2;i++)
{
if（t==t2^i^（s-s2-i)）
{
printf（ "x=%ld,y=%ld\n ",i,s-s2-i);
break;//打印并跳出循环
}
}
}

发表于：2007-02-07 23:34:2233楼得分:0

--> weijue（味觉全无)
-------------------------------
大致的算法,二楼已经有说了,
设缺失的两个数为x,y,对数组进行扫描一遍,
1e6（x,y除外)
sum1 = ∑x
　　　　x=1

1e6（x,y除外)
sum2 = ∑√x
　　　　x=1

再用x,y不缺失的相应的和减去sum1,sum2即可求得x+y = c1,x^0.5+y^0.5 = c2,再对这两式进行变形求根,即可求出x,y的值

---------------

--> ahjoe（强哥) 只能用5个简单变量且不能改变源数组。很多人没认真看
---------------------------------------------------------------
上面给的版本中,因为不致表达过长,使用了一些变量,事实上这些变量是可以去掉的说,也就是说,再简化一下可以满足五个变量的要求

--> bicidedida（)
不需要奇偶分开算,只要计算出x+y = c1,x^2+y^2 = c2,即可解出x,y,问题是x^2+y^2这个在计算的过程发生的误差较大,故改为了x^0.5+y^0.5=c2,再对此式变形,转成一元二次方程,即可解出x,y

--> sofix（)
^0.9,和^0.5,^2的时候都是存在误差的,只不过^0.9误差在小数部分,而^2的误差在整数部分,故^2误差较大,还有^0.9的时候误差较小,基本上已经满足需求,按最接近的那个即可,而事实上采用求^0.5之后,就不需这样了,直接用求根公式搞定

发表于：2007-02-08 01:18:1634楼得分:0

知道自己错了

发表于：2007-02-08 09:09:3835楼得分:0

顶！但是总觉得还是有其他的方法。

比如说 a+b=x
2a+b=y 或者其他的不是乘的也可以简单确定a, b的

但是怎么凑出来其他的形式暂时还没想到

发表于：2007-02-08 09:29:5136楼得分:0

to softwarewander（目标在远方，路在脚下……)
上面的和，2次方和。。。。的原理是基于凡得蒙行列式
对于其他的方法，你可以查一下柯西行列式

发表于：2007-02-08 10:24:3437楼得分:0

top
wizardblue（) （ ) 信誉：100 blog 2007-2-7 23:34:22 得分: 0
问题是x^2+y^2这个在计算的过程发生的误差较大,故改为了x^0.5+y^0.5=c2,再对此式变形,转成一元二次方程,即可解出x,y
--------------------------------------------------------
（除了溢出）还会发生什么误差？

---------------------解方程组的代码：
for（int i=1;i <1000001&&i <c1;i++)
{
if（i^2+（c1-i)^2==c2)
{
printf（ "%d%d ",i,c1-i);
}
}

发表于：2007-02-08 10:40:4638楼得分:0

--> weijue（味觉全无) ,就是指溢出

发表于：2007-02-08 11:02:2039楼得分:0

支持bicidedida（)的办法。

发表于：2007-02-08 14:19:5840楼得分:0

呵呵，原来oversense（步步文) （三级（初级))早就想到了，厉害！

发表于：2007-02-08 17:32:2341楼得分:0

看了半天才发现一楼的解答一语道破啊
学习.

发表于：2007-02-08 17:59:1442楼得分:0

实现oversense（步步文),c很久不用，见笑
int j=0;
int64 乘合计=0;
int64 合计 = 0;
for（int i=1;i <999998;i++)
{
合计 = 合计 + 数组（i);
乘合计 = 乘合计 + 数组（i) * 数组（i);
while（乘合计 > j*j) {
乘合计 = 乘合计 - j * j;
j= j+ 1;
}
}
合计 = 1000000 /2 *（1000000 +1)) -合计
while （j < 1000000)
{
乘合计 = 乘合计 - j * j;
j= j+ 1;
}
乘合计 = -1 * 乘合计

for（int i=1;i <1000001;i++)
{
if（i^2+（合计-i)^2==乘合计)
{
printf（ "%d%d ",i,合计-i);
break;
}
}

发表于：2007-02-08 18:00:4543楼得分:0

while （j < 1000000)
为
while （j < 1000001)

发表于：2007-02-09 10:49:2044楼得分:0

根据楼上各位思想，编写代码如下：

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

const int size = 1000001;

void init_array（vector <int> & array);
void find_2_missing（const vector <int> & array);
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

const int size = 1000001;

void init_array（vector <int> & array);
void find_2_missing（const vector <int> & array);

int main（void)
{
vector <int> array;
init_array（array);
find_2_missing（array);
}

void init_array（vector <int> & array)
{
array.resize（size + 1);
for （int i = 0; i <= size; ++i)
{
array[i] = i;
}
cout < < "input 2 missing numbers: ";
int m1, m2;
cin > > m1 > > m2;
array[m1] = 0;
array[m2] = 0;
// copy（array.begin（), array.end（), ostream_iterator <int> （cout, "\n "));
random_shuffle（array.begin（)+1, array.end（));
}

void find_2_missing（const vector <int> & array)
{
int x_plus_y = 0;
int xx_plus_yy = 0;

for （int i = 0; i <= size; ++i)
{
x_plus_y += i - array[i];
xx_plus_yy += i*i - array[i]*array[i];
}
cout < < "x + y = " < < x_plus_y < < endl;
cout < < "x^2 + y^2 = " < < xx_plus_yy < < endl;
}

发表于：2007-02-09 13:49:2345楼得分:0

帮你测试了一下
---------------------
input 2 missing numbers: 999998 999999
x + y = 1999997
x^2 + y^2 = -1460759931

发表于：2007-02-09 18:22:0646楼得分:0

用两个64位长整型（long64)就可以了

发表于：2007-02-10 12:08:2347楼得分:0

思路如下，计算a+b和a^2+b^2。
扫描一遍序列，做两次计算，从1000000往下扫：
1.用序列号减去当前的数，差值相加记为sum。
2.用序列号平方减去当前的数的平方，差值相加记为product。
因为少了两个数，所以扫描一遍后，还有两个数没有计算，为2和1，分别加上这两个数和他们的平方。这样就可以比较简单的获得a+b和a^2+b^2。
这样就可以容易得到a和b了。

我觉得难点是要考虑1000000个数字的空间。反正直接用数组存放这些数字是肯定不现实的了，本人的机器是跑不起来了。sinall的代码不错，不过在我机器上跑了也有点慢。8-p另外为什么有负数啊？

发表于：2007-02-10 17:47:5948楼得分:0

#include <iostream>
using namespace std;

#define max_size 1000000
int main（){
srand（time（null));
long missing1 = rand（)%max_size;
long missing2 = rand（)%max_size;
cout < < "missing1: " < <missing1 < <endl;
cout < < "missing2: " < <missing2 < <endl;

double c1 = 0;
double c2 = 0;
long i=0;
long cv1 = 1;
long cv2 = 1;
for（i = 1;i <max_size+1;i++){
if（i==missing1 ¦ ¦ i==missing2)continue;
c1 -=i;
while（c1 <0 && cv1 <max_size+1){
c1 +=cv1;
cv1++;
}
c2 -=1.0*i*i;
while（c2 <0 && cv2 <max_size+1){
c2 +=1.0*cv2*cv2;
cv2++;
}
}
cout < < "x+y= " < <（long)c1 < <endl;
cout < < "x^2+y^2= " < <（long)c2 < <endl;
system（ "pause ");
return 0;
}

发表于：2007-02-11 11:46:1549楼得分:0

我觉得这道题目的难点不是怎么求这两个数字，从数学上来说是很简单的。问题是如何用尽量少的代码来解决这个问题，以及效率的问题。

发表于：2007-02-11 18:02:4250楼得分:0

// find2numbers.cpp : defines the entry point for the console application.
//

#include "stdafx.h "
#include "iostream "
#include "vector "
#include "algorithm "

const int max_number = 100000;

using namespace std;

int _tmain（int argc, _tchar* argv[])
{
vector <int> list;
int a, b;

cout < < "please enter two numbers: ";
cin> > a> > b;
while （a == b)
{
cout < < "please enter two different numbers: ";
cin> > a> > b;
}

// start to initialize number list.
for （int i = 1; i <= max_number; i++)
{
if （i != a && i != b)
list.push_back（i);
}
random_shuffle（list.begin（), list.end（));

unsigned __int64 _sum, _sum2;
_sum = 0;
_sum2 = 0;
for （long i = max_number; i > 2; i--)
{
_sum += i - list[i-3];
_sum2 += i * i - list[i-3] * list[i-3];
}
_sum += 1 + 2;
_sum2 += 1 + 4;

return 0;
}
好像用了__int64类型，在大数的时候，还是有问题，搞不懂了。请求指点。

发表于：2007-02-13 15:17:3951楼得分:0

设两个数为x和y
x+y=sum1（1到1000000的和-剩下的999998个数的和),
x*x+y*y=sum2（1到1000000每个数的平方的和-剩下的999998个数每个数的平方的和）,
2*x*y=sum1*sum1-sum2，
然后自己解方程式

发表于：2007-02-13 15:49:3552楼得分:0

to 楼上：
_sum2 += i * i - list[i-3] * list[i-3];
i * i存储在long型空间，也会溢出
试试_sum2 += （__int64)i * i - （__int64)list[i-3] * list[i-3];

发表于：2007-02-14 09:13:1253楼得分:0

to 楼上：
这是我的失误，没有说明，所有变量都要用64位的

发表于：2007-02-23 10:39:3054楼得分:0

金石新创携手启异新创共同推出“精准通”智能网站分析平台

北京金石新创网络科技有限公司（金石新创）携手北京启异新创信息技术有限公司（启异新创）于2006年12月6日，推出ccmedia集团的创新业务“精准通”智能网站分析系统。
ccmedia集团是专业的跨国电子商务软件领导公司，一直致力于网站客户行为分析的方面的研究，其产品和服务在台湾已取得第一品牌之地位，在韩国更有超过50%的市场占有率。在网站客户行为分析行业享有良好的口碑。
ccmedia集团于2006年成立北京启异新创信息技术有限公司，授权北京金石新创网络科技有限公司推出创新服务“精准通”智能网站分析系统。
“精准通”提供先进、完整的商业网站客户行为分析整合方案，深度分析网站浏览者属性、跟踪访客浏览动态，解析出细分客群在网站中对于不同服务与产品的偏好，进而提炼客户特征体现网站真正价值，达成提升网站流量、营收和利润等多项经营绩效目标。

发表于：2007-02-25 12:55:4155楼得分:0

可不可以用两个string型的变量，一个存储1--1000000的数字,形如：1*2*3......,还有一个存储去掉两个数的999998个数相乘的形式，写个search函数统计有多少个1，多少个2等等，可以知道去掉的两个数是由那几个数字组成，再用两个long型的变量算出两个数的差值。是不是就可以算出来呢，对了，string型的两个变量还可以利用长度的差算出两个数字的位数和等等，我觉得应该可以算出来

发表于：2007-02-25 13:06:3256楼得分:0

好像错了，会有好几个解哎，郁闷

发表于：2007-02-27 12:25:5357楼得分:0

都按1楼的思维了
有不用计算的方法:

数组中放数1-a时,下标0-（a-1),

设a[x1]=x2+1;a[x2]=x3+1;....
这样是个循环

少了2个数就是找出完成这个循环缺少的2个数.

int array[10]={9,6,4,3,1,7,5,10,0,0};

int main（int argc, char* argv[])
{
int i,p;
int x=0,y=0;
int tmp;
for（i=1;i <=10-2;++i)
{
p = i;
while（1)
{
if（p==10-1)
tmp = x;
else if（p==10)
tmp = y;
else
tmp = array[p-1];
if（tmp==0)
{
if（p==10)
y=i;
else
x=i;
break;
}
if（tmp==x)
{
x = i;
break;
}
if（tmp==y)
{
y = i;
break;
}
if（tmp <=i)break;
p=tmp;
}
}
printf（ "%d,%d\n ",x,y);
return 0;
}

发表于：2007-02-27 14:44:3858楼得分:0

楼上的，题目中告诉了你不许用数组变量。

发表于：2007-02-27 15:58:3759楼得分:0

数组变量指什么?
array[array[x]]这样不允许么?

发表于：2007-02-27 16:09:3060楼得分:0

先將999998以字符串連接起來存放到變量x中，用 ", "分割
在循環1000000次，看x中置否有這個值。
假設999998數存放在數組a[999998]中
以下是java代碼
int i=0;
int c=0;
string x= " ";
string b= " ";
for（i=0;i <999998;i++){
x=x+ ", "+a[i];
}
for（i=0;i <1000000;i++){
b=string.valueof（i);
if（x.indexof（b)==-1){
// 打印丟失的數據
system.out.println（i);
c++
if（c==2){
break;
}
}
}

发表于：2007-02-27 17:26:1261楼得分:0

用i当作循环变量，对999998长度数组遍历一次
用变量a求出999998长度数组的和
用变量b求出999998长度数组中偶数平方和-奇数平方和

然后求a = （1+1000000)*1000000/2 - a
然后求b = （1到1000000中偶数平方和-奇数平方和) - b

设两个数为x,y
if （a是偶数 && b> 0)，解
x+y=a
x^2+y^2=b
else if （a是偶数 && b <0)，解
x+y=a
x^2+y^2=-b
else if （a是奇数)，解
x+y=a
x^2-y^2=b

解方程组的时候，仍然用i作循环变量，穷举所有情况

发表于：2007-03-01 15:25:3262楼得分:0

试了一下，问题严重。一楼及类似的方法都不行，

1. 如果用浮点数精度严重不够，如果用整数，不是5个变量可以实现的；
2. 速度不是一般的慢。

这样的方法，不具有实用价值。

发表于：2007-03-01 15:29:1463楼得分:0

数组中放数1-a时,下标0-（a-1),

设a[x1]=x2+1;a[x2]=x3+1;....a[xi]=x1+1. ........
这样是n个循环

少了2个数就是找出完成这n个循环缺少的2个数.

这样可以避免计算. 5个变量也够用
上面有程序测试下

发表于：2007-03-01 22:46:4164楼得分:0

//程序已测试通过.
//核心函数为 find（int[] data) 使用两个局部变量, 均为long型
//find 核心如下.
/*
long sum = 1 + 2; // x+y
long sum2 = 1 * 1 + 2 * 2; // x^2+y^2
for （int i = 0; i < max - 2; i++) {
sum += i+3 - data[i];
sum2 += （long)（i+3) * （i+3) - （long)data[i] * data[i];
}
*/

//ps.1. 将所有平方和加起来, 依然低于64位整数的最大值.
//ps.2. 整型*整型, 注意强转成long型. 否则1e6 * 1e6 != 1e12

//完整程序如下 : 类 find.searchtwonumber

package find;

import java.util.arrays;
import java.util.random;

public class searchtwonumber {

private final int max = 1000000;

public int[] createdata（int num1, int num2) {

//检查参数
if （num1 <= 0 ¦ ¦ num1 > max ¦ ¦ num2 <= 0 ¦ ¦ num2 > max ¦ ¦ num1 == num2) {
throw new illegalargumentexception（);
}
if （num1 > num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}

// 赋值.
int[] data = new int[max - 2];
for （int i = 1; i < num1; i++) {
data[i - 1] = i;
}
for （int i = num1 + 1; i < num2; i++) {
data[i - 2] = i;
}
for （int i = num2 + 1; i <= max; i++) {
data[i - 3] = i;
}

// 打乱顺序
random rand = new random（);
for （int i = 0; i < 100000; i++) {
int x = rand.nextint（max - 2);
int y = rand.nextint（max - 2);
//system.out.println（x + " " + y);
int temp = data[x];
data[x] = data[y];
data[y] = temp;
}
return data;
}

public void find（int[] data) {
long sum = 1 + 2; // x+y
long sum2 = 1 * 1 + 2 * 2; // x^2+y^2

for （int i = 0; i < max - 2; i++) {
sum += i+3 - data[i];
sum2 += （long)（i+3) * （i+3) - （long)data[i] * data[i];
}

//打印出两数和与平方和
system.out.println（ "x+y= " + sum);
system.out.println（ "x^2+y^2= " + sum2);

//求解
//solve（sum, sum2);
//long x = （sum-（（long)math.sqrt（sum*sum-2*（sum*sum-sum2))))/2;
//long y = （sum+（（long)math.sqrt（sum*sum-2*（sum*sum-sum2))))/2;
//system.out.println（x + " " + y);
system.out.println（ "number is " +
（（sum-（（long)math.sqrt（sum*sum-2*（sum*sum-sum2))))/2) + " " +
（（sum+（（long)math.sqrt（sum*sum-2*（sum*sum-sum2))))/2)
);
}
/*
// 解二元一次方程.
private void solve（long sum, long sum2) {
// sum2=x^2+（sum-x)^2=2*x^2-2sumx+sum^2
long a = 2;
long b = -2 * sum;
long c = sum * sum - sum2;
long delt = （long) math.sqrt（b * b - 4 * a * c);
long x = （-b - delt) / 2 / a;
long y = （-b + delt) / 2 / a;
system.out.println（ "number is " + x + " " + y);
}
*/
public static void main（string[] args) {

int[] data;

searchtwonumber search = new searchtwonumber（);
data = search.createdata（1, 2);
search.find（data);
system.out.println（);

data = search.createdata（5, 7);
search.find（data);
system.out.println（);

data = search.createdata（11, 879517);
search.find（data);
system.out.println（);

data = search.createdata（12345, 67890);
search.find（data);
system.out.println（);

data = search.createdata（999998, 999999);
search.find（data);
system.out.println（);

data = search.createdata（999999, 1000000);
search.find（data);
system.out.println（);
}
}

发表于：2007-03-01 22:55:5665楼得分:0

是三个局部变量, 还有个循环变量

发表于：2007-03-02 07:53:2766楼得分:0

怎么就没人看我的思路呢....
非要计算才肯放心么.
我那个也可以证明可行正确的

发表于：2007-03-02 19:57:0867楼得分:0

经证明 sun3411（sun) 的思路确实可行正确.

sun3411（sun) 的思想如下 : 原数据中少了两个数据, 则创建两个局部变量, 用来补充. 因为每个数据是唯一的, 所有原数组必定存在x个循环（即数组中, 根据索引取值, 再用值做索引, 循环), 而取走两个数据之后, 则至少有一个循环会断环, 如果找出断环的值, 即是原始数据.

按照 sun3411（sun) 的思路写出了一段程序.

但是结果令人遗憾, 当max值为10000以下没有问题, 当max为100000时, 计算一次需175578ms, 即175s, 那当1000000时, 估计得5个小时左右才能出结果.

仔细思考之后, 发现求平方和的算法, 时间复杂度为 o（n), 而sun3411（sun)的算法时间复杂度为 o（n^2) , 而本题的n却非常大, 导致此算法无法令人满意.

可能我的计算过程不是最优化的, 希望 sun3411（sun) 能补充更好的改进算法.

ps. 计算了才肯放心

完整原程序如下. 类 find.searchtwonum2

package find;

import java.util.random;

/**
* 从1到1000000中任意拿掉两个数，把剩下的999998个数顺序打乱，并且放入数组中。
* 要求只扫描一遍数组，把这两个数找出来。可以使用最到不超过5个局部变量，不能用数组变量，并且不能改变原数组的值。
*
* ps.1. 将所有平方和加起来, 依然低于64位整数的最大值. ps.2. 整型*整型, 注意强转成long型. 否则1e6 * 1e6 != 1e12
*
* @author lhj
* @time 2007-3-1 - 下午10:51:33
*
*/
public final class searchtwonum2 {

public final int[] createdata（int max, int num1, int num2) {

// 检查参数
if （num1 <= 0 ¦ ¦ num1 > max ¦ ¦ num2 <= 0 ¦ ¦ num2 > max ¦ ¦ num1 == num2) {
throw new illegalargumentexception（);
}
if （num1 > num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}

// 赋值.
int[] data = new int[max - 2];
for （int i = 1; i < num1; i++) {
data[i - 1] = i;
}
for （int i = num1 + 1; i < num2; i++) {
data[i - 2] = i;
}
for （int i = num2 + 1; i <= max; i++) {
data[i - 3] = i;
}

// 打乱顺序
random rand = new random（);
for （int i = 0; i < 100000; i++) {
int x = rand.nextint（max - 2);
int y = rand.nextint（max - 2);
// system.out.println（x + " " + y);
int temp = data[x];
data[x] = data[y];
data[y] = temp;
}
return data;
}

public final void find（int[] data) {
final int length = data.length;
int num1 = -1;
int num2 = -1;
for （int i = 0; i < length; i++) {
int point = i;
while （true) {
// 3584169 1 -1 2,7

int current = data[point] - 1;
if （current == length) {
if （num1 == -1) {
num1 = i;
}
break;
}
if （current == length + 1) {
if （num2 == -1) {
num2 = i;
}
break;
}
if （current == num1) {
num1 = i;
break;
}

if （current == num2) {
num2 = i;
break;
}

if （current == i) {
break;
}

point = current;
}
}

if （num1 > num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}

system.out.println（ "result = " + （num1 + 1) + " " + （num2 + 1));
}

public final void calc（int max, int num1, int num2) {
system.out.println（ "data = " + max + " " + num1 + " " + num2);
long begin = system.currenttimemillis（);
find（createdata（max, num1, num2));
long end = system.currenttimemillis（);
system.out.println（ "time = " + （end-begin));
system.out.println（);
}

public static void main（string[] args) {

searchtwonum2 search = new searchtwonum2（);
search.calc（10, 1, 2);
search.calc（100, 51, 72);
search.calc（1000, 500, 758);
search.calc（1000, 500, 758);
search.calc（10000, 514, 7574);
search.calc（100000, 54321, 76543);
search.calc（1000000, 11, 879517);
search.calc（1000000, 12345, 67890);
search.calc（1000000, 999998, 999999);
search.calc（1000000, 999999, 1000000);

search.calc（1000000, 1, 2);
search.calc（1000000, 5, 7);
search.calc（1000000, 12345, 67890);
search.calc（1000000, 12545, 67290);
search.calc（1000000, 11345, 67850);
search.calc（1000000, 999998, 999999);
search.calc（1000000, 999999, 1000000);
}
}

/*
begin : max=10 num1=1 num2=2
1 2
time = 0

begin : max=100 num1=51 num2=72
51 72
time = 0

begin : max=1000 num1=500 num2=758
500 758
time = 16

begin : max=1000 num1=500 num2=758
500 758
time = 0

begin : max=10000 num1=514 num2=7574
514 7574
time = 235

begin : max=100000 num1=54321 num2=76543
54321 76543
time = 175578

begin : max=1000000 num1=11 num2=879517
*/

发表于：2007-03-05 12:31:4868楼得分:10

谢谢ls的测试
前面给的有点问题的
下面的检验没错了

乱序情况下:
效率100 '000个一般50ms内
循环步数3 '000 '000步内

最坏情况:
2,3,4,5,6,7,8,......,99999,0,0
这个100 '000*100 '000步, 没解了

限制:
如果能用数组保存访问过的元素那么算法能优化到o（n)

//不能改数组的值没办法....
#define array（x) （（x)==num-2?ret1:（x)==num-1?ret2:array[x])
//5个变量i,p,tmp,ret1,ret2
void search_data（int num, int &ret1, int &ret2)
{
int i,p;
int tmp;

for（i=1;i <=num-2;++i)
{
p = i;
while（1)
{
tmp = array（p-1);
if（tmp==ret1)
{
if（ret1!=num-1)
{
tmp = array（tmp-1);
while（array（ret1-1)!=array（tmp-1))//循环链中查p
{
if（（tmp == i) ¦ ¦（tmp == num-1) )break;

tmp = array（tmp-1);
}
if（tmp!=i)//p不存在循环中, p能导出前面的假定缺失数
ret1 = i;
}
else
{
ret1 = i;
}
break;
}
else if（tmp==ret2)//另一个位置
{
if（ret2!=num)
{
tmp = array（tmp-1);
while（array（ret2-1)!= array（tmp-1))
{
if（（tmp == i) ¦ ¦（tmp == num) )break;
tmp = array（tmp-1);
}
if（tmp!=i)
ret2 = i;
}
else
{
ret2 = i;
}
break;
}
else
{
if（tmp <=i)break;//小于i部分不用检查
}
p=tmp;
}
}
}

发表于：2007-03-05 12:34:2369楼得分:0

漏了:
ret1 ret2初始为num-1和num

下一篇：求fip多线程断点续传临时数据的存储方法。
上一篇：谁能帮我用c语言写个程序：任意长整数减法运算

其他资讯