问题是这样的:从1到100000中任意拿掉两个数字,把剩下99998个数的顺序打乱并且放到数组中,要求只扫描一遍,把这个两个数找出来,可以使用最多不超过5个局部变量,不能使用数组变量并且不能改变数组的值。
开始老担心溢出问题,最简单的方法不敢用,老想另辟蹊径。最后发现担心是多余的,这里需要用到的数只是稍微超过32位而已,大多数高级语言都能很轻松的处理64位大整数,连javascript也可以处理54位的大整数而不丢失精度,远远超过了这个问题的规模。
这里特地把计算范围扩大了5倍来检验溢出问题。规模再大的时候我的IE计算时间超过5秒开始要警告了。为了代码简洁,打乱次序使用了效率很低的sort方法,大量的时间都消耗在这一步。把排序参数调整为0.8(而不是0.5)主要是为了减少排序计算量。
<HTML>
<BODY>
<SCRIPT LANGUAGE="JavaScript">
<!--
var n=500000;//n是常数,不算临时变量。
var ar=[];//这是输入数据,不算临时变量
for(var i=0;i<n;i++){
ar.push(i+1)
}
//i是生成输入数据使用的,不算临时变量
//随机抽取掉两个数
document.write("抽掉的第1个数是:"+ar.splice(Math.floor(Math.random()*ar.length),1))
document.write("<br>抽掉的第2个数是:"+ar.splice(Math.floor(Math.random()*ar.length),1))
//打乱顺序
ar.sort(function(){return Math.random()-.8})
//使用了3个临时变量
var t1=0,t2=0,t3;
for(t3=ar.length-1;t3>=0;t3--){
t1=t1+ar[t3];
t2=t2+(t3+1)*(t3+1)-ar[t3]*ar[t3];
}
t2=t2+n*n*2-n*2+1;
document.write("<br>计算得到两个数是:<br>"+(((n+1)*n/2-t1)+Math.sqrt(2*(t2)-((n+1)*n/2-t1)*((n+1)*n/2-t1)))/2+"<br>"+(((n+1)*n/2-t1)-Math.sqrt(2*(t2)-((n+1)*n/2-t1)*((n+1)*n/2-t1)))/2)
//-->
</SCRIPT>
</BODY>
</HTML>