DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> JavaScript綜合知識 >> javascript算法題:求任意一個1-9位不重復的N位數在該組合中的大小排列序號
javascript算法題:求任意一個1-9位不重復的N位數在該組合中的大小排列序號
編輯:JavaScript綜合知識     

 具體題目是這樣的:

  從1--9中選取N個數字,組成不重復的N位數,從小到大進行編號,當輸入其中任何一個數M時,能找出該數字對應

的編號。如 N=3,M=213. 輸出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2

  首先看到題目想到的是生成一個從少到大的全排列的數組,然後再遍歷數組得到對應的序號(數組下標加1),又或者想到一個個從小到大的生成push進數組,然後判斷該數是不是當前題目給的數,如果是的話要求的序號就是當前數組的長度,比前面好的一點的是不用浪費時間去計算生成後面的項。生成本身復雜度不高,如果擴展到16進制甚至36進制且給一個很大的數的話就不好了,還有需要浪費一部分空間去保存用不上的數據。或許我們可以嘗試其它不用生成的方法。

  我們先理想化下題目,如果給了一個數N,那麼,M就由1-N N位數組成(比如N=4,那M就由1234幾個數字組合,而不是其它1349等其它組合)。之所以這麼做是因為我們要簡化條件好分析出共性得到解題的方法,而且要從隨機的情況轉化成理想的情況也不難,本文就不啰嗦了。先分析下題目給的例子,[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)] 213在第三位,首數字是2,也就是說首數字是1的都在他前面(123,132),再來看第二個數字和後面的數的組合13,首字母1已經是最小的了,他前面不可能有任何數,而第三個數字3就不用看了,因為如果前面的位數都確定了,最後一位就只有一種可能了,得出來的結果就是213的前面有2(首位)+0(二位)+0(尾位)=2個數,也就是說當前數在第3位,對比一下答案確實是這樣的,其它數的分析也一樣。由此可以得出我們要一個函數(也就是下面代碼的setAll())可以算出某一位比當前數小的可能性總數,然後累加起來+1就是想要的結果,請看代碼實現:

//函數功能:得到每一位,如果是其它數的話比當前小的可能性總數
//a  當前數序號(從小到大)
//n  當前數總數
function getAll(a,n){
 var sum=1; //總數
 for(var i=n;i>1;i--)sum=sum*i; //算出n個有序的位置放n個不同的數字的可能性總數
 return sum*(a-1)/n; //算出比首位為a的比當前數小的數的可能性總數
}

//m 要計算的數序列
//a 存放當前位的數在和它後位的數而組成的數它的大小序號
//  比如 213 的 a數組為 [2,1,1];
 a[0]為2是因為 213 首位2在213三個數字中排第2小;而a[1]為1是因為13的首位1在13中排第一小
function find(m){
 m=(m+"").split(""); //把當前數拆分放在數組裡面好方便對每一位進行計算
 var a=new Array(m.length+1).join(1).split("");
 //快速生成長度為m的長度的值都為1的數組,a數組的功能說明看上面函數頭的注釋
 for(var i=0;i<m.length-1;i++){
 for(var j=i+1;j<m.length;j++){
  if(+m[i]>+m[j])a[i]++;
 }
 } //生成a數組
 console.log("a數組:",a);
 for(i=1,sum=1;i<m.length;i++){
 sum+=getAll(+a[i-1],m.length-i+1); //循環調用getAll計算每一位與其後面的數成的組合比當前組合小的可能性總數
 }
 return m+" 排在全排列的第"+sum+"位";
}
console.log(find(213)); //輸出3
console.log(find(123)); //輸出1
console.log(find(231)); //輸出4
console.log(find(312)); //輸出5
console.log(find(4321)); //輸出24
console.log(find(21)); //輸出2
console.log(find(1)); //輸出1
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved