emu in blogjava

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
问题是这样的:从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>
posted on 2010-08-02 16:49 emu 阅读(1982) 评论(3)  编辑  收藏 所属分类: DHTML和JAVASCRIPT 技术google编程大赛模拟题及入围赛真题

评论

# re: 差点被燕潘考倒了 2011-05-08 14:09 程良
我先没看懂你的算法
我先想到得是积x*y,
应该也行的哈。要多用个变量就。  回复  更多评论
  

# re: 差点被燕潘考倒了 2012-08-02 10:41 emu
http://www.closetou.com/find.html

整掉3个数的解法  回复  更多评论
  

# re: 差点被燕潘考倒了 2013-09-10 11:21 meteoric_cry
@emu

http://www.closetou.com/find.html 这个网址打不开了..  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: