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 閱讀(2047) 評論(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 這個網址打不開了..  回復  更多評論
            

          主站蜘蛛池模板: 那曲县| 逊克县| 婺源县| 甘谷县| 武隆县| 广德县| 嫩江县| 石棉县| 丽水市| 汉寿县| 东城区| 安福县| 孟州市| 澄迈县| 铜川市| 东乌珠穆沁旗| 丹江口市| 塔城市| 峨眉山市| 福海县| 荔波县| 南漳县| 鹤山市| 白山市| 哈巴河县| 扶余县| 鸡泽县| 昆明市| 响水县| 肃北| 望城县| 察雅县| 五寨县| 榕江县| 贵德县| 柳林县| 泗阳县| 颍上县| 富顺县| 香格里拉县| 建阳市|