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

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

題目描述：

設(shè)計(jì)一個算法，判斷給定的一個數(shù)n是否是某個數(shù)的平方，不能使用開方運(yùn)算。例如16就滿足條件，因?yàn)樗?的平方；而15則不滿足條件，因?yàn)椴淮嬖谝粋€數(shù)（江南博哥）使得其平方值為15。正確答案：方法一：直接計(jì)算法

由于不能使用開方運(yùn)算，因此最直接的方法就是計(jì)算平方。主要思路為：對1到n的每個數(shù)i，計(jì)算它的平方m，如果m＜n，則繼續(xù)遍歷下一個值(i+1)，如果m==n，那么說明n是m的平方，如果m＞n，那么說明n不能表示成某個數(shù)的平方。實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//判斷一個自然數(shù)是否是某個數(shù)的平方

funcisPower1(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然數(shù)")

returnfalse

}

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

m:=i*i

if(m==n){

returntrue

}elseif(m＞n){

returnfalse

}

}

returnfalse

}

funcmain(){

n1:=15

n2:=16

fret.Println("方法一")

ifisPower1(n1){

fmt.Println(n1,"是某個自然數(shù)的平方")

}else{

fmt.Println(n1,"不是某個自然數(shù)的平方")

}

if(isPower1(n2)){

fmt.Println(n2,"是某個自然數(shù)的平方")

}else{

fmt.Println(n2,"不是某個自然數(shù)的平方")

}

}

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

15不是某個自然數(shù)的平方

16是某個自然數(shù)的平方

由于這種方法只需要從1遍歷到n^0.5就可以得出結(jié)果，因此算法的時間復(fù)雜度為O(n^0.5)。

方法二：二分查找法

與方法一類似，這種方法的主要思路還是查找從1～n的數(shù)字中，是否存在一個數(shù)m，使得m的平方為n。只不過在查找的過程中使用的是二分查找的方法。具體思路為：首先判斷mid=(1+n)/2的平方power與m的大小，如果power＞m，那么說明在[1，mid-1]區(qū)間繼續(xù)查找，否則在[mid+1，n]區(qū)間繼續(xù)查找。

實(shí)現(xiàn)代碼如下：

funcisPower2(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然數(shù)")

returnfalse

}

low:=0

high:=n

forlow＜high{

mid:=(low+high)

power:=mid*mid

ifpower＞n{//大于則在小的范圍找

high=mid-1

}elseifpower＜n{//小于則在大的范圍找

low=mid+1

}else{

returntrue

}

}

returnfalse

}

算法性能分析

由于這種方法使用了二分查找的方法，因此，時間復(fù)雜度為O(logn)，其中，n為數(shù)的大小。

方法三：減法運(yùn)算法

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

funcisPower3(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然數(shù)")

returnfalse

}

minus:=1

forn＞0{

n=n-minus

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

if(n==0){

returntrue

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

}elseifn＜0{

returnfalse

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

}else{

minus+=2

}

}

returnfalse

}

算法性能分析

這種方法的時間復(fù)雜度仍然為O(n^0.5)。由于方法一使用的是乘法操作，這種方法采用的是減法操作，因此，這種方法的執(zhí)行效率比方法一更高。[考點(diǎn)]如何判斷一個自然數(shù)是否是某個數(shù)的平方

2.

題目描述：

何判斷一個數(shù)是否為2的n次方?正確答案：方法一：構(gòu)造法

2的n次方可以表示為：2^0，2^1，2^2…，2^n，如果一個數(shù)是2的n次方，那么最直觀的想法是對1執(zhí)行了移位操作(每次左移一位)，即通過移位得到的值必定是2的n次方(針對n的所有取值構(gòu)造出所有可能的值)。所以，要想判斷一個數(shù)是否為2的n次方，只需要判斷該數(shù)移位后的值是否與給定的數(shù)相等，實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//判斷n能否表示成2的n次方

funcisPower1(nint)bool{

if(n＜1){

returnfalse

}

fori:=1;i＜n;{

if(i==n){

returntrue

}

i＜＜=1

}

returnfalse

}

funcmain(){

fmt.Println("方法一")

ifisPower1(8){

fmt.Println("8能表示成2的n次方")

}else{

fmt.Println("8不能表示成2的n次方")

}

ifisPower1(9){

fmt.Println("9能表示成2的n次方")

}else{

fmt.Println("9不能表示成2的n次方")

}

}

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

8能表示成2的n次方

9不能表示成2的n次方

算法性能分析：

上述算法的時間復(fù)雜度為O(logn)。

方法二：與操作法

那么是否存在效率更高的算法呢?通過對2^0，2^1，2^2，…，2^n進(jìn)行分析，發(fā)現(xiàn)這些數(shù)字的二進(jìn)制形式分別為：1，10，100，…。從二進(jìn)制的表示可以看出，如果一個數(shù)是2的n次方，那么這個數(shù)對應(yīng)的二進(jìn)制表示中有且只有一位是1，其余位都為0。因此，判斷一個數(shù)是否為2的n次方可以轉(zhuǎn)換為這個數(shù)對應(yīng)的二進(jìn)制表示中是否只有一位為1。如果一個數(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?？梢岳眠@種方法來判斷一個數(shù)是否為2的n次方。實(shí)現(xiàn)代碼如下：

funcisPower2(nint)bool{

if(n＜1){

returnfalse

}

returnn&(n-1)==0

}

算法性能分析：

這種方法的時間復(fù)雜度為O(1)。[考點(diǎn)]何判斷一個數(shù)是否為2的n次方

3.

題目描述：

如何不使用除法操作符實(shí)現(xiàn)兩個正整數(shù)的除法?正確答案：方法一：減法

主要思路為：使被除數(shù)不斷減去除數(shù)，直到相減的結(jié)果小于除數(shù)為止，此時，商就為相減的次數(shù)，余數(shù)為最后相減的差。例如在計(jì)算14除以4的時候，首先計(jì)算14-4=10，由于10＞4，繼續(xù)做減法運(yùn)算：10-4=6，6-4=2，此時2＜4。由于總共進(jìn)行了3次減法操作，最終相減的結(jié)果為2，因此，15除以4的商為3，余數(shù)為2。如果被除數(shù)比除數(shù)都小，那么商為0，余數(shù)為被除數(shù)。根據(jù)這個思路的實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//方法功能：計(jì)算兩個自然數(shù)的除法

funcdivide1(m,nint)(res,remainint){

res=0

remain=m

//被除數(shù)減除數(shù)，直到相減結(jié)果小于除數(shù)為止

form＞n{

m=m-n

res++

}

remain=m

return

}

funcmain(){

m:=14

n:=4

fmt.Println("減法")

fmt.Println(m,"除以",n)

res,remain:=dividel(m,n)

fmt.Println("商為:",res,"余數(shù):",remain)

}

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

14除以4商為：3余數(shù)為：2

算法性能分析

這種方法循環(huán)的次數(shù)為m/n，因此，算法的時間復(fù)雜度為O(m/n)。需要注意的是，這種方法也實(shí)現(xiàn)了不用除法操作符實(shí)現(xiàn)除法運(yùn)算的目的。

方法二：移位法

方法一所采用的減法操作，還可以用等價的加法操作來實(shí)現(xiàn)。例如在計(jì)算17除以4的時候，可以嘗試4*1，4*2(4+4)，4*3(4+4+4)依次進(jìn)行計(jì)算，直到計(jì)算的結(jié)果大于14的時候就可以很容易求出商與余數(shù)。但是這種方法每次都遞增4，效率較低。下面給出另外一種增加遞增速度的方法：以2的指數(shù)進(jìn)行遞增(取2的指數(shù)的原因是，2的指數(shù)操作可以通過移位操作來實(shí)現(xiàn)，有更高的效率)，計(jì)算4*1，4*2，4*4，4*8，由于4*8＞17，然后接著對17-4*4=1進(jìn)入下一次循環(huán)用相同的方法進(jìn)行計(jì)算。實(shí)現(xiàn)代碼如下：

funcdivide2(m,nint)(res,remainint){

res=0

form＞=n{

multi:=1

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

formulti*n＜=(m＞＞1){

multi＜＜=1

}

res+=multi

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

m-=multi*n

}

remain=m

return

}

算法性能分析：

由于這種方法采用指數(shù)級的增長方式不斷逼近m/n，因此，算法的時間復(fù)雜度為O(log(m/n))。[考點(diǎn)]如何不使用除法操作符實(shí)現(xiàn)兩個正整數(shù)的除法

4.

題目描述：

如何只使用++操作符實(shí)現(xiàn)加減乘除運(yùn)算正確答案：本題要求只能使用++操作來實(shí)現(xiàn)加減乘除運(yùn)算，下面重點(diǎn)介紹用++操作來實(shí)現(xiàn)加減乘除運(yùn)算的方法：

(1)加法操作：實(shí)現(xiàn)a+b的基本思路為對a執(zhí)行b次++操作即可。

(2)減法操作：實(shí)現(xiàn)a-b(a＞=b)的基本思路為：不斷對b執(zhí)行++操作，直到等于a為止，在這個過程中記錄執(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＞b時，就可以得到商為n-1。

根據(jù)以上思路，實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//用++實(shí)現(xiàn)加法操作(限制條件：至少有一個非負(fù)數(shù))

funcadd(a,bint)int{

ifa＜0&&b＜0{

fmt.Println("無法用++操作實(shí)現(xiàn)")

return-1

}

ifb＞=0{

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

a++

}

returna

}else{

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

b++

}

returnb

}

}

//用++實(shí)現(xiàn)加減法操作(限制條件：被減數(shù)大于減數(shù))

funcminus(a,bint)int{

if(a＜b){

fmt.Println("無法用++操作實(shí)現(xiàn)")

return-1

}

result:=0

for;b!=a;b++{

result++

}

returnresult

}

//用++實(shí)現(xiàn)加乘法操作(限制條件：兩個數(shù)都為整數(shù))

funcmulti(a,bint)int{

ifa＜=0||b＜=0{

fmt.Println("無法用++操作實(shí)現(xiàn)")

return-1

}

result:=0

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

result=add(result,a)

}

returnresult

}

//用++實(shí)現(xiàn)加法除法操作(限制條件：兩個數(shù)都為整數(shù))

funcdivide(a,bint)int{

ifa＜=0||b＜=0{

fmt.Println("無法用++操作實(shí)現(xiàn)")

return-1

}

result:=1

tmpMulti:=0

fortrue{

tmpMulti=multi(b,result)

iftmpMulti＜=a{

result++

}else{

break

}

}

returnresult-1

}

funcmain(){

fmt.Println(add(2,-4))

fmt.Println(minus(2,-4))

fmt.Println(multi(2,4))

fmt.Println(divide(9,4))

}

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

-2

6

8

2

此處，在實(shí)現(xiàn)加法操作的時候，如果a與b都是整數(shù)，那么可以選擇比較小的數(shù)進(jìn)行循環(huán)，從而可以提高算法的性能。[考點(diǎn)]如何只使用++操作符實(shí)現(xiàn)加減乘除運(yùn)算

5.

題目描述：

已知隨機(jī)數(shù)生成函數(shù)rand7()能產(chǎn)生的隨機(jī)數(shù)是整數(shù)1～7的均勻分布，如何構(gòu)造rand10()函數(shù)，使其產(chǎn)生的隨機(jī)數(shù)是整數(shù)1～10的均勻分布。正確答案：要保證rand10()產(chǎn)生的隨機(jī)數(shù)是整數(shù)1～10的均勻分布，可以構(gòu)造一個1～10*n的均勻分布的隨機(jī)整數(shù)區(qū)間(n為任何正整數(shù))。假設(shè)x是這個1～10*n區(qū)間上的一個隨機(jī)數(shù)，那么x%10+1就是均勻分布在1～10區(qū)間上的整數(shù)。

根據(jù)題意，rand7()函數(shù)返回1到7的隨機(jī)數(shù)，那么rand7()-1則得到一個離散整數(shù)集合，該集合為{0，1，2，3，4，5，6}，該集合中每個整數(shù)的出現(xiàn)概率都為1/7。那么(rand7()-1)*7得到另一個離散整數(shù)集合A，該集合元素為7的整數(shù)倍，即A={0，7，14，21，28，35，42}，其中，每個整數(shù)的出現(xiàn)概率也都為1/7。而由于rand7()得到的集合B={1，2，3，4，5，6，7}，其中每個整數(shù)出現(xiàn)的概率也為1/7。顯然集合A與集合B中任何兩個元素和組合可以與1～49之間的一個整數(shù)一一對應(yīng)，即1～49之間的任何一個數(shù)，可以唯一地確定A和B中兩個元素的一種組合方式，這個結(jié)論反過來也成立。由于集合A和集合B中元素可以看成是獨(dú)立事件，根據(jù)獨(dú)立事件的概率公式