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

題目描述：

求出用1，2，5這三個數不同個數組合的和為100的組合個數。為了更好地理解題目的意思，下面給出幾組可能的組合：100個1，0個2和0個5，它們的（江南博哥）和為100；50個1，25個2，0個5的和也是100；50個1，20個2，2個5的和也為100。正確答案：方法一：蠻力法

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

packagemain

import(

"fmt"

)

funccombinationCount(nint)int{

count:=0

num1:=n

//1最多的個數

num2:=n/2

//2最多的個數

num5:=n/5

//5最多的個數

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))

}

程序的運行結果為

541

算法性能分析：

這種方法循環的次數為101*51*21。

方法二：數字規律法

針對這種數學公式的運算，一般都可以通過找出運算的規律進而簡化運算的過程，對于本題而言，對x+2y+5z=100進行變換可以得到x+5z=100-2y。從這個表達式可以看出，x+5z是偶數且x+5z＜=100。因此，求滿足x+2y+5z=100組合的個數就可以轉換為求滿足“x+5z是偶數且x+5z＜=100”的個數。可以通過對z的所有可能的取值(0＜=z＜=20)進行遍歷從而計算滿足條件的x的值。

當z=0時，x的取值為0，2，4，…，100(100以內所有的偶數)，個數為(100+2)/2

當z=1時，x的取值為1，3，5，…，95(95以內所有的奇數)，個數為(95+2)/2

當z=2時，x的取值為0，2，4，…，90(90以內所有的偶數)，個數為(90+2)/2

當z=3時，x的取值為1，3，5，…，85(85以內所有的奇數)，個數為(85+2)/2

當z=19時，x的取值為5，3，1(5以內所有的奇數)，個數為(5+2)/2

當z=20時，x的取值為0(0以內所有的偶數)，個數為(0+2)/2

根據這個思路，實現代碼如下：

funccombinationCount2(nint)int{

count:=0

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

count+=(m+2)/2=

}

returncount

}

算法性能分析：

這種方法循環的次數為21。[考點]如何組合1，2，5這三個數使其和為100

2.

題目描述：

100個燈泡排成一排，第一輪將所有燈泡打開；第二輪每隔一個燈泡關掉一個，即排在偶數的燈泡被關掉，第三輪每隔兩個燈泡，將開著的燈泡關掉，關掉的燈泡打開。依次類推，第100輪結束的時候，還有幾盞燈泡亮著?正確答案：對于每盞燈，當拉動的次數是奇數時，燈就是亮著的，當拉動的次數是偶數時，燈就是關著的。

(2)每盞燈拉動的次數與它的編號所含約數的個數有關，它的編號有幾個約數，這盞燈就被拉動幾次。

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

我們知道，一個數的約數都是成對出現的，只有完全平方數約數的個數才。是奇數個。

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

下面是程序的實現：

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++{

//判斷因子數是否為奇數，如果是奇數(燈亮)則加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,"盞燈亮著")

}

程序的運行結果為

亮著的燈的編號是：1

亮著的燈的編號是：4

亮著的燈的編號是：9

亮著的燈的編號是：16

亮著的燈的編號是：25

亮著的燈的編號是：36

亮著的燈的編號是：49

亮著的燈的編號是：64

亮著的燈的編號是：81

亮著的燈的編號是：100

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

3.

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

第一趟排序后：13[659776382749]

第二趟排序后：1327[9776386549]

第三趟排序后：132738[76976549]

第四趟排序后：13273849[976576]

第五趟排序后：1327384965[9776]

第六趟排序后：132738496576[97]

最后排序結果：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)

}

程序運行結果為：

0123456789[考點]如何進行選擇排序

4.

題目描述：

如何進行插入排序?正確答案：對于給定的一組記錄，初始時假設第一個記錄自成一個有序序列，其余的記錄為無序序列。接著從第二個記錄開始，按照記錄的大小依次將當前處理的記錄插入到其之前的有序序列中，直至最后一個記錄插入到有序序列中為止。以數組{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)

}

程序運行結果為：

134771940[考點]如何進行插入排序

5.

題目描述：

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

以數組{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

則經過多趟排序后的結果如下：

初始狀態：[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