Go程序員面試分類模擬題21

Go程序員面試分類模擬題21論述題1.

題目描述：

求出用1，2，5這三個(gè)數(shù)不同個(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。正確答案：方法一：蠻力法

最簡單的方法就是對所有的組合進(jìn)行嘗試，然后判斷組合的結(jié)果是否滿足和為100，這些組合有如下限制：1的個(gè)數(shù)最多為100個(gè)，2的個(gè)數(shù)最多為50個(gè)，5的個(gè)數(shù)最多為20個(gè)。實(shí)現(xiàn)思路為：遍歷所有可能的組合1的個(gè)數(shù)x(0＜=x＜=100)，2的個(gè)數(shù)y(0=＜y＜=50)，5的個(gè)數(shù)z(0＜=z＜=20)，判斷x+2y+5z是否等于100，如果相等，則滿足條件，實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

funccombinationCount(nint)int{

count:=0

num1:=n

//1最多的個(gè)數(shù)

num2:=n/2

//2最多的個(gè)數(shù)

num5:=n/5

//5最多的個(gè)數(shù)

forx:=0;x＜=num1;x++{

fory:=0;y＜=num2;y++{

forz:=0;z＜=num5;z++{

if(x+2*y+5*z==n){//滿足條件

count++

}

}

}

}

returncount

}

funcmain(){

fmt.Println(combinationCount(100))

}

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

541

算法性能分析：

這種方法循環(huán)的次數(shù)為101*51*21。

方法二：數(shù)字規(guī)律法

針對這種數(shù)學(xué)公式的運(yùn)算，一般都可以通過找出運(yùn)算的規(guī)律進(jìn)而簡化運(yùn)算的過程，對于本題而言，對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)換為求滿足“x+5z是偶數(shù)且x+5z＜=100”的個(gè)數(shù)?？梢酝ㄟ^對z的所有可能的取值(0＜=z＜=20)進(jìn)行遍歷從而計(jì)算滿足條件的x的值。

當(dāng)z=0時(shí)，x的取值為0，2，4，…，100(100以內(nèi)所有的偶數(shù))，個(gè)數(shù)為(100+2)/2

當(dāng)z=1時(shí)，x的取值為1，3，5，…，95(95以內(nèi)所有的奇數(shù))，個(gè)數(shù)為(95+2)/2

當(dāng)z=2時(shí)，x的取值為0，2，4，…，90(90以內(nèi)所有的偶數(shù))，個(gè)數(shù)為(90+2)/2

當(dāng)z=3時(shí)，x的取值為1，3，5，…，85(85以內(nèi)所有的奇數(shù))，個(gè)數(shù)為(85+2)/2

當(dāng)z=19時(shí)，x的取值為5，3，1(5以內(nèi)所有的奇數(shù))，個(gè)數(shù)為(5+2)/2

當(dāng)z=20時(shí)，x的取值為0(0以內(nèi)所有的偶數(shù))，個(gè)數(shù)為(0+2)/2

根據(jù)這個(gè)思路，實(shí)現(xiàn)代碼如下：

funccombinationCount2(nint)int{

count:=0

form:=0;m＜=n;m+=5{

count+=(m+2)/2=

}

returncount

}

算法性能分析：

這種方法循環(huán)的次數(shù)為21。[考點(diǎn)]如何組合1，2，5這三個(gè)數(shù)使其和為100

2.

題目描述：

100個(gè)燈泡排成一排，第一輪將所有燈泡打開；第二輪每隔一個(gè)燈泡關(guān)掉一個(gè)，即排在偶數(shù)的燈泡被關(guān)掉，第三輪每隔兩個(gè)燈泡，將開著的燈泡關(guān)掉，關(guān)掉的燈泡打開。依次類推，第100輪結(jié)束的時(shí)候，還有幾盞燈泡亮著?正確答案：對于每盞燈，當(dāng)拉動(dòng)的次數(shù)是奇數(shù)時(shí)，燈就是亮著的，當(dāng)拉動(dòng)的次數(shù)是偶數(shù)時(shí)，燈就是關(guān)著的。

(2)每盞燈拉動(dòng)的次數(shù)與它的編號所含約數(shù)的個(gè)數(shù)有關(guān)，它的編號有幾個(gè)約數(shù)，這盞燈就被拉動(dòng)幾次。

(3)1～100這100個(gè)數(shù)中有哪幾個(gè)數(shù)，約數(shù)的個(gè)數(shù)是奇數(shù)?

我們知道，一個(gè)數(shù)的約數(shù)都是成對出現(xiàn)的，只有完全平方數(shù)約數(shù)的個(gè)數(shù)才。是奇數(shù)個(gè)。

所以，這100盞燈中有10盞燈是亮著的，它們的編號分別是：1、4、9、16、25、36、49、64、81、100。

下面是程序的實(shí)現(xiàn)：

packagemain

import(

"fmt"

)

funcfactorIsOdd(aint)int{

vartotalint

fori:=1;i＜=a;i++{

ifa%i==0{total++)

}

iftotal%2==1{return1)else{return0}

}

functotalCount(num[]int,nint)int{

varcoumint

fori:=0;i＜n;i++{

//判斷因子數(shù)是否為奇數(shù)，如果是奇數(shù)(燈亮)則加1

iffactorIsOdd(num[i])==1{

fmt.Println("亮著的燈的編號是:",num[i])

count++

}

}

returncount

}

funcmain(){

num:=make([]int,100)

fori:=0;i＜100;i++{num[i]=i+1}

count:=totalCount(num,100)

fmt.Println("最后總共有",count,"盞燈亮著")

}

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

亮著的燈的編號是：1

亮著的燈的編號是：4

亮著的燈的編號是：9

亮著的燈的編號是：16

亮著的燈的編號是：25

亮著的燈的編號是：36

亮著的燈的編號是：49

亮著的燈的編號是：64

亮著的燈的編號是：81

亮著的燈的編號是：100

最后總共有10盞燈亮著。[考點(diǎn)]如何判斷還有幾盞燈泡還亮著

3.

如何進(jìn)行選擇排序?正確答案：選擇排序是一種簡單直觀的排序算法，它的基本原理如下：對于給定的一組記錄，經(jīng)過第一輪比較后得到最小記錄，然后將該記錄與第一個(gè)記錄的位置進(jìn)行交換；接著對不包括第一個(gè)記錄以外的其他記錄進(jìn)行第二輪比較，得到最小記錄并與第二個(gè)記錄進(jìn)行位置交換；重復(fù)該過程，直到進(jìn)行比較的記錄只有一個(gè)時(shí)為止。以數(shù)組{38，65，97，76，13，27，49}為例，具體步驟如下：

第一趟排序后：13[659776382749]

第二趟排序后：1327[9776386549]

第三趟排序后：132738[76976549]

第四趟排序后：13273849[976576]

第五趟排序后：1327384965[9776]

第六趟排序后：132738496576[97]

最后排序結(jié)果：13273849657697

程序示例如下：

packagemain

import(

"fmt"

)

funcSelectSort(data[]int){

llen:=len(data)

fori:=0;i＜llen;i++{

tmp:=data[i]

flag:=i

forj:=i+1;j＜llen;j++{

ifdata[j]＜tmp{

tmp=data[j]

flag=j

}

}

ifflag!=i{

data[flag]=data[i]

data[i]=tmp

}

}

}

funcmain(){

data:=[]int{5,4,9,8,7,6,0,1,3,2}

SelectSort(data)

fmt.Println(data)

}

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

0123456789[考點(diǎn)]如何進(jìn)行選擇排序

4.

題目描述：

如何進(jìn)行插入排序?正確答案：對于給定的一組記錄，初始時(shí)假設(shè)第一個(gè)記錄自成一個(gè)有序序列，其余的記錄為無序序列。接著從第二個(gè)記錄開始，按照記錄的大小依次將當(dāng)前處理的記錄插入到其之前的有序序列中，直至最后一個(gè)記錄插入到有序序列中為止。以數(shù)組{38，65，97，76，13，27，49}為例，直接插入排序具體步驟如下：

第一步插入38以后：[38]659776132749

第二步插入65以后：[3865]9776132749

第三步插入97以后：[386597]76132749

第四步插入76以后：[38657697]132749

第五步插入13以后：[1338657697]2749

第六步插入27以后：[132738657697]49

第七步插入49以后：[13273849657697]

程序示例如下：

packagemain

import(

"fmt"

)

funcInsertSort(array[]int){

ifarray==nil{return}

fori:=1;i＜len(array);i++{

trap,j:=array[i],i

ifarray[j-1]＞tmp{

forj＞=1&&array[j-1]＞tmp{

array[j]=array[j-1]

j--

}

}

array[j]=tmp

}

}

funcmain(){

array:=[]int{7,3,19,40,4,7,1};

InsenSort(array);

fmt.Println(array)

}

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

134771940[考點(diǎn)]如何進(jìn)行插入排序

5.

題目描述：

如進(jìn)行冒泡排序?正確答案：冒泡排序顧名思義就是整個(gè)過程就像氣泡一樣往上升，單向冒泡排序的基本思想是(假設(shè)由小到大排序)：對于給定的n個(gè)記錄，從第一個(gè)記錄開始依次對相鄰的兩個(gè)記錄進(jìn)行比較，當(dāng)前面的記錄大于后面的記錄時(shí)，交換其位置，進(jìn)行一輪比較和換位后，n個(gè)記錄中的最大記錄將位于第n位；然后對前(n-1)個(gè)記錄進(jìn)行第二輪比較；重復(fù)該過程直到進(jìn)行比較的記錄只剩下一個(gè)時(shí)為止。

以數(shù)組{36，25，48，12，25，65，43，57}為例，具體排序過程如下：

一趟排序的過程如下：

R[1]3625252525252525

R[2]2536363636363636

R[3]4848481212121212

R[4]1212124825252525

R[5]2525252548484848

R[6]6565656565654343

R[7]4343434343436557

R[8]5757575757575765

則經(jīng)過多趟排序后的結(jié)果如下：

初始狀態(tài)：[3625481225654357]

1趟排序：[2536122548435765]

2趟排序：[251225364348]5765

3趟排序：[1225253643]485765

4趟排序：[12252536]43485765

5趟排序：[122525]3643485765

6趟排序：[1225]253643485765

7趟排序：[12]25253643485765

程序示例如下：

packagemain

import(

"fmt"

)

funcBubbleSort(array[]jnt){

llen:=len(array)

fori:=0;i＜llen-1;i++{

forj