前端程序員面試分類真題24

前端程序員面試分類真題24簡(jiǎn)答題1.

請(qǐng)用JavaScript實(shí)現(xiàn)桶排序。正確答案：桶排序的工作原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序，有可能再使用別的排序算法（江南博哥）或是以遞歸方式繼續(xù)使用桶排序。算法原理如下：

(1)設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶。

(2)遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去。

(3)對(duì)每個(gè)非空桶進(jìn)行排序。

(4)從非空桶里把排好序的數(shù)據(jù)合并起來(lái)。

根據(jù)以上的實(shí)現(xiàn)原理，具體的實(shí)現(xiàn)代碼如下所示。

/**

*@paramarr

數(shù)組

*@paramnum

每個(gè)桶可存放的數(shù)量

*/

functionbucketSort(arr,num){

varlen=arr.length;

if(len＜=1){

returnarr;

}

varbuckets=[0],

result=[],

min=Math.min.apply(null,arr),

max=Math.max.apply(null,arr),

space=Math.ceil((max-min+1)/num),

//桶的數(shù)量

k,index;

for(varj=0;j＜len;j++){

index=Math.floor((arr[j]-min)/space);

//需要放入的桶的下標(biāo)

if(buckets[index]){

//非空桶,執(zhí)行插入排序

k=buckets[index].length-1;

while(k＞=0&&buckets[index][k]＞arr[j]){

buckets[index][k+1]=buckets[index][k];

k--;

}

buckets[index][k+1]=arr[j];

}else{

//空桶,執(zhí)行初始化

buckets[index]=[];

buckets[index],push(arr[j]);

}

}

varn=0;

//將所有的桶合并起來(lái)

while(n＜num){

result=result.concat(buckets[n]);

n++;

}

returnresult;

}[考點(diǎn)]排序算法

2.

請(qǐng)用JavaScript實(shí)現(xiàn)快速排序。正確答案：快速排序是一種非常高效的排序算法，它采用“分而治之”的思想，把大的拆分為小的，小的再拆分為更小的。其原理如下：對(duì)于一組給定的記錄，通過(guò)一輪排序后，將原序列分為兩部分，其中前一部分的所有記錄均比后一部分的所有記錄小，然后再依次對(duì)前后兩部分的記錄進(jìn)行快速排序，遞歸該過(guò)程，直到序列中的所有記錄均有序?yàn)橹埂?/p>

具體而言，算法步驟如下：

(1)分解：將輸入的序列array[m～n]劃分成兩個(gè)非空子序列array[m～k]和array[k+1～n]，使array[m～k]中任一元素的值不大于array[k+1～n]中任一元素的值。

(2)遞歸求解：通過(guò)遞歸調(diào)用快速排序算法分別對(duì)array[m～k]和array[k+1～n]進(jìn)行排序。

(3)合并：由于對(duì)分解出的兩個(gè)子序列的排序是就地進(jìn)行的，所以在array[m～k]和array[k+1～n]都排好序后，不需要執(zhí)行任何計(jì)算就已將array[m～n]排好序。

以數(shù)組[38，65，97，76，13，27，49]為例。第一輪排序過(guò)程如下。

初始化關(guān)鍵字：[4938659776132749]

第一次交換后：[2738659776134949]

第二次交換后：[2738499776136549]

j向左掃描，位置不變，第三次交換后：[2738139776496549]

i向右掃描，位置不變，第四次交換后：[2738134976976549]

j向左掃描[2738134976976549]

整個(gè)排序過(guò)程如下所示。

初始化關(guān)鍵字：[4938659776132749]

一輪排序之后：[273813]49[76976549]

二輪排序之后：[13]27[38]49[4965]76[97]

三輪排序之后：1327384949[65]7697

最后的排序結(jié)果：1327384949657697

根據(jù)以上的實(shí)現(xiàn)原理，具體的實(shí)現(xiàn)代碼如下所示。

functionquickSort(arr){

varlength=arr,length;

if(length＜=1){

returnarr;

}

varbase_num=arr[0],

left_array=[],

//保存小于基準(zhǔn)元素的記錄

right_array=[];

//保存大于基準(zhǔn)元素的記錄

for(vari=1;i＜length;i++)

if(base_num＞arr[i]){

//放入左邊數(shù)組

left_array.push(arr[i]);

}else{

//放入右邊數(shù)組

right_array.push(arr[i]);

}

}

left_array=quickSort(left_array);

right_array=quickSort(right_array);

returnleft_array.concat([base_num],right_array);

}[考點(diǎn)]排序算法

3.

請(qǐng)用JavaScript實(shí)現(xiàn)希爾排序。正確答案：希爾排序也稱為“縮小增量排序”，它的基本原理如下：首先將待排序的數(shù)組分成多個(gè)子序列，使得每個(gè)子序列的元素個(gè)數(shù)相對(duì)較少，然后對(duì)各個(gè)子序列分別進(jìn)行直接插入排序，等整個(gè)待排序序列“基本有序”后，最后再對(duì)所有元素進(jìn)行一次直接插入排序。具體步驟如下：

(1)選擇一個(gè)步長(zhǎng)序列t1，t2，…，tk，滿足ti＞tj(i＜j)，并且tk=1。

(2)對(duì)待排序序列進(jìn)行k輪排序，其中k是步長(zhǎng)序列個(gè)數(shù)。

(3)每輪排序，根據(jù)對(duì)應(yīng)的步長(zhǎng)ti，將待排序序列分割成ti個(gè)子序列，并分別對(duì)各個(gè)子序列進(jìn)行直接插入排序。

注意，當(dāng)步長(zhǎng)因子為1時(shí)，所有元素作為一個(gè)序列來(lái)處理，其長(zhǎng)度為n。以數(shù)組[26，53，67，48，57，13，48，32，60，50]，步長(zhǎng)序列{5，3，1}為例，排序步驟如下。

根據(jù)以上的實(shí)現(xiàn)原理，具體的實(shí)現(xiàn)代碼如下所示。

functionshellSort(arr){

varlen=arr.length,

gap=0,

temp;

while(gap＜len/5){

//動(dòng)態(tài)定義步長(zhǎng)序列

gap=gap*5+1;

}

for(;gap＞0;gap=Math.floor(gap/5)){

for(vari=gap;i＜len;i++){

temp=arr[i];

for(varj=i-gap;j＞=0&&arr[j]＞temp;j-=gap){

arr[j+gap]=arr[j];

}

arr[j+gap]=temp;

}

}

returnarr;

}[考點(diǎn)]排序算法

4.

設(shè)計(jì)一個(gè)算法，判斷給定的一個(gè)數(shù)n是否是某個(gè)數(shù)的平方，不能使用開(kāi)方運(yùn)算。例如16就滿足條件，因?yàn)樗?的平方；而15則不滿足條件，因?yàn)椴淮嬖谝粋€(gè)數(shù)使得其平方值為15。正確答案：通過(guò)對(duì)平方數(shù)進(jìn)行分析發(fā)現(xiàn)有如下規(guī)律：

(n+1)^2=n^2+2n+1=(n-1)^2+(2×(n-1)+1)+2×n+1=…=1+(2×1+1)+(2×2+1)+…+(2×n+1)

通過(guò)上述公式可以發(fā)現(xiàn)，這些項(xiàng)構(gòu)成了一個(gè)公差為2的等差數(shù)列的和。由此可以得到如下解決方法：對(duì)n依次減1，3，5，7，…，如果相減后的值大于0，則繼續(xù)減下一項(xiàng)；如果相減后的值等于0，則說(shuō)明n是某個(gè)數(shù)的平方；如果相減后的值小于0，則說(shuō)明n不是某個(gè)數(shù)的平方。根據(jù)這個(gè)思路實(shí)現(xiàn)的代碼如下所示。

functionisPower(n){

if(n＜=0){

returnfalse;

}

varminus=1;

while(n＞0){

n=n-minus;

if(n==0)

//n是某個(gè)數(shù)的平方

returntrue;

elseif(n＜0)

//n不是某個(gè)數(shù)的平方

returnfalse;

else

//每次減數(shù)都加2

minus+=2;

}

returnfalse;

}[考點(diǎn)]基本數(shù)字運(yùn)算

5.

如何判斷一個(gè)數(shù)是否為2的n次方?正確答案：通過(guò)對(duì)2^0，2^1，2^2，…，2^n進(jìn)行分析，發(fā)現(xiàn)這些數(shù)字的二進(jìn)制形式分別為：1、10、100…。從中可以看出，如果一個(gè)數(shù)是2的n次方，那么這個(gè)數(shù)對(duì)應(yīng)的二進(jìn)制表示中有且只有一位是1，其余位都為0。因此，判斷一個(gè)數(shù)是否為2的n次方可以轉(zhuǎn)換為這個(gè)數(shù)對(duì)應(yīng)的二進(jìn)制表示中是否只有一位為1。如果一個(gè)數(shù)的二進(jìn)制表示中只有一位是1，例如num=00010000，那么num-1的二進(jìn)制表示為(num-1)=00001111，由于num與num-1的二進(jìn)制表示中每一位都不相同，所以，num&(num-1)的運(yùn)算結(jié)果為0?？梢岳眠@種方法來(lái)判斷一個(gè)數(shù)是否為2的n次方。實(shí)現(xiàn)代碼如下所示。

functionisPower(n){

if(n＜1)

returnfalse;

varm=n&(n-1);

returnm==0;

}[考點(diǎn)]基本數(shù)字運(yùn)算

6.

如何不使用除法操作符實(shí)現(xiàn)兩個(gè)正整數(shù)的除法?正確答案：可以用加法操作來(lái)實(shí)現(xiàn)。例如在計(jì)算17除以4的時(shí)候，可以嘗試4×1、4×2(即4+4)和4×3(即4+4+4)依次進(jìn)行計(jì)算，直到計(jì)算結(jié)果大于17的時(shí)候就可以很容易地求出商與余數(shù)。但是這種算法每次都遞增4，效率較低。下面給出另外一種增加遞增速度的方法：以2的指數(shù)進(jìn)行遞增(之所以取2的指數(shù)是因?yàn)樵摬僮骺梢酝ㄟ^(guò)移位來(lái)實(shí)現(xiàn)，效率更高)，計(jì)算4×1、4×2、4×4和4×8，由于4×8＞17，所以結(jié)束指數(shù)遞增，計(jì)算17-4×4，再進(jìn)入下一次循環(huán)。實(shí)現(xiàn)代碼如下所示。

functiondevide(m,n){

varresult=0,

multi,

remain;

while(m＞=n){

multi=1;

//multi*n＞m/2(即2*multi*n＞m)時(shí)結(jié)束循環(huán)

while(multi*n＜=(m＞＞1)){

multi＜＜=1;

}

result+=multi;

//相減的結(jié)果進(jìn)入下次循環(huán)

m-=multi*n;

}

remain=m;

return{

res:result,

remain:remain

};

}[考點(diǎn)]基本數(shù)字運(yùn)算

7.

如何只使用遞增運(yùn)算符(++)實(shí)現(xiàn)加減乘除運(yùn)算?正確答案：本題要求只能使用遞增操作(++)來(lái)實(shí)現(xiàn)加減乘除運(yùn)算，下面重點(diǎn)介紹該操作的計(jì)算過(guò)程。

(1)加法操作：實(shí)現(xiàn)a+b的基本思路是對(duì)a執(zhí)行b次遞增操作。

(2)減法操作：實(shí)現(xiàn)a-b(a≥b)的基本思路是不斷地對(duì)b執(zhí)行遞增操作，直到等于a為止，在這個(gè)過(guò)程中記錄執(zhí)行遞增操作的次數(shù)。

(3)乘法操作：實(shí)現(xiàn)a×b的基本思路是利用已經(jīng)實(shí)現(xiàn)的加法操作把a(bǔ)相加b次，就得到了a和b的積。

(4)除法操作：實(shí)現(xiàn)a/b的基本思路是利用乘法操作，使b不斷乘以1，2，…，n，直到b×n＞a時(shí)，就可以得到商n-1。

根據(jù)以上思路實(shí)現(xiàn)的代碼如下所示。

/*

**函數(shù)功能:用遞增實(shí)現(xiàn)加法運(yùn)算(限制條件:至少有一個(gè)非負(fù)數(shù))

**輸入?yún)?shù):a和b都是整數(shù),且有一個(gè)非負(fù)數(shù)

*/

functionadd(a,b){

if(a＜0&&b＜0){

return-1;

}

if(b＞=0){

for(vari=0;i＜b;i++){

a++;

}

returna;

}

for(i=0;i＜a;i++){

b++;

}

returnb;

}

/*

**函數(shù)功能:用遞增實(shí)現(xiàn)減法運(yùn)算(限制條件:被減數(shù)大于減數(shù))

**輸入?yún)?shù):a和b都是整數(shù)且a＞=b

*/

functionsub(a,b){

if(a＜b){

return-1;

}

for(varresult=0;b!=a;b++,result++){}

returnresult;

}

/*

**函數(shù)功能:用遞增實(shí)現(xiàn)乘法運(yùn)算(限制條件:兩個(gè)數(shù)都為整數(shù))

**輸入?yún)?shù):a和b都是正整數(shù)

*/

functionmulti(a,b){

if(a＜=0||b＜=0){

return-1;

}

varresult=0;

for(vari=0;i＜b;i++){

result=add(result,a);

}

returnresult;

}

/*

**函數(shù)功能:用遞增實(shí)現(xiàn)除法運(yùn)算(限制條件:兩個(gè)數(shù)都為整數(shù))

**輸入?yún)?shù):a和b都是正整數(shù)

*/

functiondivid(a,b){

if(a＜=0||b＜=0){

return-1;

}

varresult=1,

tmpMulti=0;

while(1){

tmpMulti=multi(b,result);

if(tmpMulti＜=a){

result++;

}else{

break;

}

}

returnresult-1;

}[考點(diǎn)]基本數(shù)字運(yùn)算

8.

如何判斷1024!末尾有多少個(gè)0?正確答案：最簡(jiǎn)單的方法就是計(jì)算出1024!(即1024的階乘)的值，然后判斷末尾有多少個(gè)0，但是這種方法有兩個(gè)非常大的缺點(diǎn)：第一，算法的效率非常低下；第二，當(dāng)這個(gè)數(shù)字比較大的時(shí)候直接計(jì)算階乘可能會(huì)導(dǎo)致數(shù)據(jù)溢出，從而導(dǎo)致計(jì)算結(jié)果出現(xiàn)偏差。因此，下面給出一種比較巧妙的方法。

5與任何一個(gè)偶數(shù)相乘都會(huì)增加末尾0的個(gè)數(shù)，由于偶數(shù)的個(gè)數(shù)肯定比5的個(gè)數(shù)多，因此，1～1024之間所有數(shù)字中有因子5的數(shù)字個(gè)數(shù)決定了1024!末尾0的個(gè)數(shù)，所以只需要統(tǒng)計(jì)因子5的個(gè)數(shù)即可。此外5與偶數(shù)相乘會(huì)使末尾增加一個(gè)0，25(有兩個(gè)因子5)與偶數(shù)相乘會(huì)使末尾增加兩個(gè)0，125(有三個(gè)因子5)與偶數(shù)相乘會(huì)使末尾增加三個(gè)0，625(有四個(gè)因子5)與偶數(shù)相乘會(huì)使末尾增加四個(gè)0。對(duì)于本題而言：

(1)是5的倍數(shù)的數(shù)有：a1=1024/5=204個(gè)。

(2)是25的倍數(shù)的數(shù)有：a2=1024/25=40個(gè)(a1計(jì)算了25中的一個(gè)因子5)。

(3)是125的倍數(shù)的數(shù)有：a3=1024/125=8個(gè)(a1，a2分別計(jì)算了125中的一個(gè)因子5)。

(4)是625盼倍數(shù)的數(shù)有：a4=1024/625=1個(gè)(a1，a2，a3分別計(jì)算了625中的一個(gè)因子5)。

由此可知，1024!中總共有a1+a2+a3+a4=204+40+8+1=253個(gè)因子5，末尾總共有253個(gè)0。根據(jù)以上思路實(shí)現(xiàn)的代碼如下所示。

functionzeroCount(n){

varcount=0;

while(n＞0){

n=Math.floor(n/5);

count+=n;

}

returncount;

}

console.log("1024!末尾O的個(gè)數(shù)為:",zeroCount(1024));

//253[考點(diǎn)]基本數(shù)字運(yùn)算

9.

請(qǐng)定義一個(gè)函數(shù)，比較a、b兩個(gè)數(shù)的大小，不能使用大于和小于兩個(gè)比較運(yùn)算符以及if條件語(yǔ)句。正確答案：根據(jù)絕對(duì)值的性質(zhì)可知，如果|a-b|=a-b，那么max(a,b)=a，否則max(a,b)=b，根據(jù)這個(gè)思路實(shí)現(xiàn)的代碼如下所示。

functionmaxNum(a,b){

returnMath.abs(a-b)==(a-b)?a:b;

}[考點(diǎn)]基本數(shù)字運(yùn)算

10.

有一個(gè)有序數(shù)列，序列中的每一個(gè)值都能夠被2或者3或者5所整除，1是這個(gè)序列的第一個(gè)元素，求第1500個(gè)值是多少?正確答案：首先可以很容易得到2、3和5的最小公倍數(shù)為30，此外，1～30這個(gè)區(qū)間內(nèi)滿足條件的數(shù)有22個(gè)，即{2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30}。由于最小公倍數(shù)為30，我們可以猜想，滿足條件的數(shù)字是否具有周期性(周期為30)呢?通過(guò)計(jì)算可以發(fā)現(xiàn)，31～60這個(gè)區(qū)間內(nèi)滿足條件的數(shù)也恰好有22個(gè)，即{32,33,34,35,36,38,39,40,42,44,45,46,48,50,51,52,54,55,56,57,58,60}，從而發(fā)現(xiàn)這些滿足條件的數(shù)確實(shí)具有周期性(周期為30)。由于1500/22=68，1500%68=4，所以可以得出第1500個(gè)數(shù)經(jīng)過(guò)了68個(gè)周期，然后在第69個(gè)周期中取第4個(gè)滿足條件的數(shù)(即1～30這個(gè)區(qū)間內(nèi)滿足條件的第4個(gè)數(shù))，即第1500個(gè)數(shù)為68×30+5=2045。根據(jù)這個(gè)思路實(shí)現(xiàn)的代碼如下所示。

functionsearch(n){

vara=[0,2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30

];

varret=Math.floor(n/22)*30+a[n%22];

returnret;

}

console.log(search(1500));

//2045[考點(diǎn)]基本數(shù)字運(yùn)算

11.

給定一個(gè)整數(shù)，輸出這個(gè)整數(shù)的二進(jìn)制表示中1的個(gè)數(shù)。例如給定整數(shù)7，其二進(jìn)制表示為111，因此，輸出結(jié)果為3。正確答案：可以采用位操作來(lái)完成。具體思路如下：首先判斷這個(gè)數(shù)的最后一位是否為1，如果為1，則計(jì)數(shù)器加1，然后通過(guò)右移棄掉最后一位，循環(huán)執(zhí)行該操作直到這個(gè)數(shù)等于0為止。在判斷二進(jìn)制表示的最后一位是否為1時(shí)，可以采用與運(yùn)算來(lái)達(dá)到這個(gè)目的。具體實(shí)現(xiàn)代碼如下所示。

functioncountOne(n){

varcount=0;//計(jì)數(shù)

while(n＞0){

if((n&1)==1)

//判斷最后一位是否為1

count++;

n＞＞=1;

//通過(guò)移位丟掉最后一位

}

returncount;

}[考點(diǎn)]基本數(shù)字運(yùn)算

12.

給定一個(gè)數(shù)d，如何計(jì)算d的n次方?例如：d=2，n=3，d的n次方為2^3=8。正確答案：在計(jì)算過(guò)程中可以充分利用中間的計(jì)算結(jié)果，提升算法效率。例如在計(jì)算2的100次方的時(shí)候，假如已經(jīng)計(jì)算出了2的50次方tmp=2^50，那就沒(méi)必要將tmp再乘以50次2，而是直接利用tmp×tmp就能得到2^100的值。通過(guò)這個(gè)特點(diǎn)可以用遞歸的方式實(shí)現(xiàn)n次方計(jì)算，具體過(guò)程如下：

(1)當(dāng)n=0時(shí)，計(jì)算結(jié)果肯定為1。

(2)當(dāng)n=1時(shí)，計(jì)算結(jié)果肯定為d。

(3)當(dāng)n＞0時(shí)，首先計(jì)算2^(n/2)的值tmp，如果n為奇數(shù)，那么計(jì)算結(jié)果result=tmp×tmp×d，如果n為偶數(shù)，那么計(jì)算結(jié)果result=tmp×tmp。

(4)當(dāng)n＜0時(shí)，首先計(jì)算2^(|n/2|)的值tmp，如果n為奇數(shù)，那么計(jì)算結(jié)果result=1/(tmp×tmp×d)，如果n為偶數(shù)，那么計(jì)算結(jié)果result=1/(tmp×tmp)。

根據(jù)以上思路實(shí)現(xiàn)的代碼如下所示。

functionpower(d,n){

if(n==0)return1;

if(n==1)returnd;

vartmp=power(d,Math.floor(Math.abs(n/2)));

if(n＞0){

if(n%2==1)

returntmp*tmp*d;

//n為奇數(shù)

returntmp*tmp;

//n為偶數(shù)

}

if(n%2==1)

return1/(tmp*tmp*d);

return1/(tmp*tmp);

}[考點(diǎn)]基本數(shù)字運(yùn)算

13.

給定一個(gè)數(shù)n，求出它的平方根，比如16的算術(shù)平方根為4。要求不能使用庫(kù)函數(shù)。正確答案：正數(shù)n的平方根可以通過(guò)計(jì)算一系列近似值來(lái)獲得，每個(gè)近似值都比前一個(gè)更加接近準(zhǔn)確值，直到找出滿足精度要求的那個(gè)數(shù)為止。具體而言，可以找出的第一個(gè)近似值是1，接下來(lái)的近似值則可以通過(guò)一個(gè)公式來(lái)獲得，即ai+1=(ai+n/ai)/2。實(shí)現(xiàn)代碼如下所示。

//獲取n的平方根,e為精度要求

functionsquareRoot(n,e){

varnew_one=n,

last_one=1;

//第一個(gè)近似值為1

while(new_one-last_one＞e){

//直到滿足精度要求為止

new_one=(new_one+last_one)/2;

//求下一個(gè)近似值

last_one=n/new_one;

}

varprecision=e.toString().split(".");

//計(jì)算小數(shù)的位數(shù)

if(precision.length＞1)

returnnew_one.toFixed(precision[i].length);

returnnew_one.toFixed(0);

}

varn=50,

e=0.000001;

console.log("50的算術(shù)平方根為",squareRoot(n,e));

//7.071068

n=4;

console.log("4的算術(shù)平方根為",squareRoot(n,e));

//2.000000[考點(diǎn)]基本數(shù)字運(yùn)算

14.

如何不使用“^”符號(hào)實(shí)現(xiàn)異或運(yùn)算?正確答案：下面介紹一種簡(jiǎn)單的實(shí)現(xiàn)方法：x^y=(x|y)&(～x|～y)，其中x|y表示如果在x或y中的位值是1，那么結(jié)果中的這個(gè)位值也為1，顯然這個(gè)結(jié)果包括三種情況，即這個(gè)位只有在x中為1，或只有在y中為1，或在x和y中都為1。要在這個(gè)基礎(chǔ)上計(jì)算出異或的結(jié)果，顯然要去掉第三種情況，也就是說(shuō)去掉在x和y中都為1的情況，而當(dāng)一個(gè)位在x和y中都為1的時(shí)候“～x|～y”的值為0，因此(x|y)&(～x|～y)的值等于x^y。實(shí)現(xiàn)代碼如下所示。

functionmyXOR(x,y){

return(x|y)&(～x|～y);

}[考點(diǎn)]基本數(shù)字運(yùn)算

15.

實(shí)現(xiàn)一個(gè)函數(shù)，要求在不使用循環(huán)的前提下輸出1～100。正確答案：很多情況下，循環(huán)都可以使用遞歸來(lái)給出等價(jià)的實(shí)現(xiàn)，具體代碼如下所示。

functionprint_num(n){

if(n＞0){

print_num(n-1);

console.log(n);

}

}

print_num(100);[考點(diǎn)]基本數(shù)字運(yùn)算

16.

10個(gè)房間里放著隨機(jī)數(shù)量的金幣，每個(gè)房間只能進(jìn)入一次，并只能在一個(gè)房間中拿金幣。一個(gè)人采取如下策略：前4個(gè)房間只看不拿，隨后的房間只要看到比前4個(gè)房間都多的金幣數(shù)就拿，否則就拿最后一個(gè)房間的金幣。編程計(jì)算這種策略拿到最多金幣的概率。正確答案：這道題是求一個(gè)概率的問(wèn)題。由于10個(gè)房間里放的金幣數(shù)量是隨機(jī)的，因此，在編程實(shí)現(xiàn)的時(shí)候首先需要生成10個(gè)隨機(jī)數(shù)來(lái)模擬10個(gè)房間里的金幣數(shù)量，然后再判斷通過(guò)這種策略是否能拿到最多的金幣。如果僅僅通過(guò)一次模擬來(lái)求拿到最多金幣的概率顯然是不準(zhǔn)確的，那么就需要進(jìn)行多次模擬，通過(guò)記錄模擬的次數(shù)m，以及拿到最多金幣的次數(shù)n，就可以計(jì)算出拿到最多金幣的概率n/m。顯然這個(gè)概率與金幣的數(shù)量以及模擬的次數(shù)有關(guān)系。模擬的次數(shù)越多越能接近真實(shí)值。下面以金幣數(shù)為1～10的隨機(jī)數(shù)，模擬次數(shù)為1000次為例給出實(shí)現(xiàn)代碼。

/*

**函數(shù)功能:判斷用指定的策略是否能拿到最多金幣

**函數(shù)參數(shù):把數(shù)組a看成房間,總共n個(gè)房間

**返回值:如果能拿到最多金幣返回1,否則返回0

*/

functiongetMaxNum(a,n){

//隨機(jī)生成10個(gè)房間里的金幣個(gè)數(shù)

varrand;

for(vari=0;i＜n;i++){

rand=Math.floor(Math.random()*10);

a[i]=rand%10+1;

//生成1～10的隨機(jī)數(shù)

}

//找出前4個(gè)房間中最多的金幣個(gè)數(shù)

varmax4=0;

for(i=0;i＜4;i++){

if(a[i]＞max4)

max4=a[i];

}

for(i=4;i＜n-1;i++){

if(a[i]＞max4)

return1;

//能拿到最多的金幣

}

return0;

//不能拿到最多的金幣

}

vara=[],

monitorCount=1000,

success=0;

for(vari=0;i＜monitorCount;i+){

if(getMaxNum(a,10))

success++;

}

console.log(success/monitorCount);

//返回的是隨機(jī)數(shù),例如0.421[考點(diǎn)]排列組合與概率

17.

給定一個(gè)正整數(shù)n，求所有和為n的整數(shù)組合，要求組合按照遞增方式展示，而且唯一。例如，4=1+1+1+1、1+1+2、1+3、2+2、4(4+0)。正確答案：以數(shù)值4為例，和為4的所有整數(shù)組合一定都小于或等于4(1,2,3,4)。首先選擇數(shù)字1，然后用遞歸的方法求和為3(4-1)的組合，一直遞歸下去直到用遞歸求和為0的組合，這時(shí)所選的數(shù)字序列就是一個(gè)和為4的數(shù)字組合；然后第二次選擇2，接著用遞歸方法求和為2(4-2)的組合；同理下一次選3，然后用遞歸求和為1(4-3)的所有組合。以此類推，直到找出所有的組合為止，實(shí)現(xiàn)代碼如下所示。

/*

**函數(shù)功能:求和為n的所有整數(shù)組合

**輸入?yún)?shù):sum為正整數(shù),result為組合結(jié)果,count記錄組合中的數(shù)字個(gè)數(shù)

*/

functiongetAllCombination(sum,result,count){

if(sum＜0)

return;

vartxt="";

//數(shù)字的組合滿足和為sum的條件,打印出所有組合

if(sum==0){

for(vari=0;i＜count;i++)

txt+=result[i]+"";

console.log("滿足條件的組合:",txt);

return;

}

txt="";

for(i=0;i＜count;i++)

txt+=result[i]+"";

console.log("----當(dāng)前組合:",txt,"----");

//打印debug信息,以便理解代碼

i=(count==0?1:result[count-1]);

//確定組合中下一個(gè)取值

console.log("---i=",i,"count=",count,"---");

//打印debug信息,以便理解代碼

for(;i＜=sum;){

result[count++]=i;

getAllCombination(sum-i,result,count),

//求和為sum-i的組合

count--;

//遞歸完成后,去掉最后一個(gè)組合的數(shù)字

i++;

//找下一個(gè)數(shù)字作為組合中的數(shù)字

}

}

varn=4,

result=[];

//存儲(chǔ)和為n的組合方式

//找出和為4的所有整數(shù)組合

getAllCombination(n,result,0);

程序的運(yùn)行結(jié)果為：

----當(dāng)前組合:----

---i=1count=0---

----當(dāng)前組合:1----

----i=1count=1---

-----當(dāng)前組合:11----

----i=1count=2---

----當(dāng)前組合:111----

--i=1count=3---

滿足條件的組合:1111

滿足條件的組合:112

----當(dāng)前組合:12----

---i=2count=2---

滿足條件的組合:13

----當(dāng)前組合:2----

---i=2count=1---

滿足條件的組合:22

----當(dāng)前組合:3----

----i=3count1---

滿足條件的組合:4

從上面的運(yùn)行結(jié)果可以看出，滿足條件的組合為：{1,1,1,1}，{1,1,2}，{1,3}，{2,2}，{4}。其他為調(diào)試信息。從打印出的信息可以看出，在求和為4的組合時(shí)，第一步選擇了1，然后求3(4-1)的組合時(shí)也選了1，求2(3-1)的組合的第一步也選擇了1，依次類推，找出第一個(gè)組合為{1,1,1,1}；再通過(guò)count--和i++找出最后兩個(gè)數(shù)字1與1的另外一種組合2，最后三個(gè)數(shù)字的另外一種組合3；接下來(lái)用同樣的方法分別選擇2和3作為組合的第一個(gè)數(shù)字，就可以得到以上結(jié)果。

代碼i=(count==0?1:result[count-1])用來(lái)控制組合中的下一個(gè)數(shù)字一定不會(huì)小于前一個(gè)數(shù)字，從而保證了組合的遞增性。如果不要求遞增(例如把{1,1,2}和{2,1,1}看作兩種組合)，那么把上面一行代碼改成i=1即可。[考點(diǎn)]排列組合與概率

18.

有一個(gè)函數(shù)fun()能返回0和1兩個(gè)值，并且返回0和1的概率都是1/2。怎么利用這個(gè)函數(shù)得到另一個(gè)函數(shù)fun2()，使fun2()也只能返回0和1，且返回0的概率為1/4，返回1的概率為3/47正確答案：函數(shù)func1()得到1與0的概率都為1/2，因此，可以調(diào)用兩次func1()，分別生成兩個(gè)值a1與a2，用這兩個(gè)數(shù)組成一個(gè)二進(jìn)制數(shù)a2a1，它可能的取值為00、01、10或11，并且得到每個(gè)值的概率都為(1/2)×(1/2)=1/4。因此，如果得到的結(jié)果為00，則返回0(概率為1/4)，其他情況則返回1(概率為3/4)。具體的實(shí)現(xiàn)代碼如下所示。

//返回0和1的概率都為1/2

functionfunc1(){

returnMath.floor(Math.random()*2)%2;

}

//返回0的概率為1/4,返回1的概率為3/4

functionfunc2(){

vara1=func1(),

a2=func1(),

tmp=a1;

tmp|=(a2＜＜1);

if(tmp==0)

return0;

return1;

}

vararr=[];

for(vari=0;i＜16;i++)

arr.push(func2());

console.log(arr.join(""));

arr=[];

for(i=0;i＜16;i++)

arr.push(func2());

console.log(arr.join(""));

程序的運(yùn)行結(jié)果為：

1110110110111101

1111111111000010

由于結(jié)果是隨機(jī)的，調(diào)用的次數(shù)越大，返回的結(jié)果越接近1/4與3/4。[考點(diǎn)]排列組合與概率

19.

隨機(jī)地從大小為n的數(shù)組中選取m個(gè)整數(shù)，要求每個(gè)元素被選中的概率相等。正確答案：從n個(gè)數(shù)中隨機(jī)選出一個(gè)數(shù)的概率為1/n，然后在剩下的n-1個(gè)數(shù)中再隨機(jī)找出一個(gè)數(shù)的概率也為1/n(第一次沒(méi)選中這個(gè)數(shù)的概率為(n-1)/n，第二次選中這個(gè)數(shù)的概率為1/(n-1)，因此，隨機(jī)選出第二個(gè)數(shù)的概率為((n-1)/n)×(1/(n-1))=1/n)，依次類推，在剩下的k個(gè)數(shù)中隨機(jī)選出一個(gè)元素的概率都為1/n。所以，這個(gè)算法的思路為：首先從包含n個(gè)元素的數(shù)組中隨機(jī)選出一個(gè)元素，然后把這個(gè)選中的數(shù)字與數(shù)組第一個(gè)元素交換，接著從數(shù)組后面的n-1個(gè)數(shù)字中隨機(jī)選出1個(gè)數(shù)字與數(shù)組第二個(gè)元素交換，依次類推，直到選出m個(gè)數(shù)字為止，數(shù)組前m個(gè)數(shù)字就是隨機(jī)選出來(lái)的m個(gè)數(shù)字，且它們被選中的概率相等。實(shí)現(xiàn)代碼如下所示。

functiongetRandomM(a,n,m){

if(n＜=0||n＜m){

return;

}

varj,rand,tmp;

for(vari=0;i＜m;++i){

rand=Math.floor(Math.random()*(n-i));

j=i+rand;

//獲取i到n-1之間的隨機(jī)數(shù)

//隨機(jī)選出的元素放到數(shù)組的前面

tmp=a[i];

a[i]=a[i];

a[j]=tmp;

}

}

vara=[1,2,3,4,5,6,7,8,9,10],

n=a.length,

m=6,

txt="";

getRandomM(a,n,m);

for(i=0;i＜m;++i)

txt+=a[i]+"";

console.log(txt);

//結(jié)果是隨機(jī)的,可能是189724[考點(diǎn)]排列組合與概率

20.

求出用1，2，5這三個(gè)數(shù)組合的和為100的組合個(gè)數(shù)。為了更好地理解題目的意思，下面給出幾組可能的組合：100個(gè)1，0個(gè)2和0個(gè)5，它們的和為100；50個(gè)1，25個(gè)2，0個(gè)5的和也是100；50個(gè)1，20個(gè)2，2個(gè)5的和也為100。正確答案：針對(duì)這種數(shù)學(xué)公式的運(yùn)算，一般都可以通過(guò)找出運(yùn)算規(guī)律來(lái)簡(jiǎn)化運(yùn)算過(guò)程。對(duì)于本題而言，對(duì)x+2y+5z=100進(jìn)行變換可以得到x+5z=100-2y。從這個(gè)表達(dá)式可以看出，x+5z是偶數(shù)且x+5z≤100。因此，求滿足x+2y+5z=100的組合個(gè)數(shù)就可以轉(zhuǎn)