DIV CSS 佈局教程網

JavaScript 生成不重複隨機數的多種思路總結
編輯:關於JavaScript     

「如何在一個區間內產生 n 個不重複的隨機數」是一道經典的面試題。本文記錄了從一道 jQuery 練習題出發,逐步優化、最終總結出四種實作思路的過程,非常適合理解隨機演算法的取捨。

題目來源是一道 jQuery 測試題:初始時 <ul> 只顯示 5 個 <li>(含最後一個),點擊「更多」會展開全部,點擊「簡化」又只顯示含最後一個在內的 5 個。核心難點在於——要隨機隱藏前 7 個 <li> 中的 3 個,且不重複。

思路是:① 從 0~6 中生成 3 個隨機數;② 判斷是否相等,不相等則執行隱藏;③ 若有重複則重新執行函式。完整範例如下:

 <!DOCTYPE html> <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <script language="javascript" type="text/javascript" src="https://libs.baidu.com/jquery/1.9.0/jquery.js"></script> <title>挑戰題</title> </head> <body> <ul> <li>0</li> <li>1</li> <li>2</li> <li>3</li> <li>4</li> <li>5</li> <li>6</li> <li>7</li> </ul> <a id="btn" onclick="cli()">簡化</a> </body> <script> $(function cli(){ $("#btn").css("cursor","pointer"); if($("#btn").html()=="簡化"){ var ran1=parseInt(Math.random()*7); var ran2=parseInt(Math.random()*7); var ran3=parseInt(Math.random()*7); //①從0~6中生成3個隨機數完成 if(ran1!=ran2&&ran1!=ran2&&ran2!=ran3){ //②判斷3個隨機數是否相等,不相等則執行操作。 $('li:eq('+ran1+')').css('display','none'); $('li:eq('+ran2+')').css('display','none'); $('li:eq('+ran3+')').css('display','none'); $("#btn").html("更多"); }else{ //③3隨機數有重復,則重新執行函數。 cli(); } } else{ $("li:hidden").css('display','list-item'); $("a:contains('更多')").html("簡化"); } }); </script> </html> 

收穫之一是記住了區間隨機數的通用公式:var ran=parseInt(Math.random()*(max-min+1)+min); 可生成 [min, max] 閉區間內的隨機整數。

收穫之二是進一步把它封裝成「生成 n 個不重複隨機數」的函式,並比較了四種思路:

思路一:先生成 n 個隨機數,比較是否重複,重複則重新執行整個函式。

 function my_ran(n,min,max){ var arr=[]; for(i=0;i<n;i++){ arr[i]=parseInt(Math.random()*(max-min+1)+min); } for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ if(arr[i]==arr[j]){ my_ran(n,min,max); return fault; } } } return arr; } 

思路二:生成第 i 個隨機數時與前 i-1 個比較,若重複則令 i=i-1 重新生成。

 function my_ran2(n,min,max){ var arr=[]; for(i=0;i<n;i++){ arr[i]=parseInt(Math.random()*(max-min+1)+min); for(j=0;j<i;j++){ if(arr[i]==arr[j]){ i=i-1; break; } } } return arr; } 

思路三:生成一個順序陣列,用 Fisher-Yates 洗牌演算法打乱後取前 n 個。

 function my_ran3(n,min,max){ var arr=[]; var arr2=[]; for(i=0;i<max-min+1;i++){ arr[i]=i+min; } for(var j,x,i=arr.length;i;j=parseInt(Math.random()*i),x=arr[--i],arr[i]=arr[j],arr[j]=x); for(i=0;i<n;i++){ arr2[i]=arr[i]; } return arr2; } 

思路四:生成順序陣列後,每次隨機挑一個值取出,再把它從陣列中刪除,重複 n 次。

 function my_ran4(n,min,max){ var arr=[]; var arr2=[]; for(i=0;i<max-min+1;i++){ arr[i]=i+min; } for(i=0;i<n;i++){ var x=parseInt(Math.random()*arr.length); arr2[i]=arr[x]; for(j=x;j<arr.length;j++){ arr[j]=arr[j+1]; } arr.length=arr.length-1; } return arr2; } 

這四種思路各有取捨:思路一、二靠「重試」保證不重複,當 n 接近區間大小時會頻繁碰撞、效率變差;思路三、四則從「有序陣列」出發,本質上不會重複,其中思路三的 Fisher-Yates 洗牌是公認最優雅高效的方案。透過這道題,你能清楚體會到「拒絕重複」背後不同的演算法思維。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved