Go程序员面试分类模拟题17

Go程序员面试分类模拟题17论述题1.

题目描述：

设计一个算法，判断给定的一个数n是否是某个数的平方，不能使用开方运算。例如16就满足条件，因为它是4的平方；而15则不满足条件，因为不存在一个数（江南博哥）使得其平方值为15。正确答案：方法一：直接计算法

由于不能使用开方运算，因此最直接的方法就是计算平方。主要思路为：对1到n的每个数i，计算它的平方m，如果m＜n，则继续遍历下一个值(i+1)，如果m==n，那么说明n是m的平方，如果m＞n，那么说明n不能表示成某个数的平方。实现代码如下：

packagemain

import(

"fmt"

)

//判断一个自然数是否是某个数的平方

funcisPower1(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然数")

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,"是某个自然数的平方")

}else{

fmt.Println(n1,"不是某个自然数的平方")

}

if(isPower1(n2)){

fmt.Println(n2,"是某个自然数的平方")

}else{

fmt.Println(n2,"不是某个自然数的平方")

}

}

程序的运行结果为

15不是某个自然数的平方

16是某个自然数的平方

由于这种方法只需要从1遍历到n^0.5就可以得出结果，因此算法的时间复杂度为O(n^0.5)。

方法二：二分查找法

与方法一类似，这种方法的主要思路还是查找从1～n的数字中，是否存在一个数m，使得m的平方为n。只不过在查找的过程中使用的是二分查找的方法。具体思路为：首先判断mid=(1+n)/2的平方power与m的大小，如果power＞m，那么说明在[1，mid-1]区间继续查找，否则在[mid+1，n]区间继续查找。

实现代码如下：

funcisPower2(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然数")

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

}

算法性能分析

由于这种方法使用了二分查找的方法，因此，时间复杂度为O(logn)，其中，n为数的大小。

方法三：减法运算法

通过对平方数进行分析发现有如下规律：

(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)。通过上述公式可以发现，这些项构成了一个公差为2的等差数列的和。由此可以得到如下的解决方法：对n依次减1，3，5，7…，如果相减后的值大于0，则继续减下一项；如果相减的后的值等于0，则说明n是某个数的平方；如果相减的值小于0，则说明n不是某个数的平方。根据这个思路，代码实现如下：

funcisPower3(nint)bool{

if(n＜=0){

fmt.Println(n,"不是自然数")

returnfalse

}

minus:=1

forn＞0{

n=n-minus

//n是某个数的平方

if(n==0){

returntrue

//n不是某个数的平方

}elseifn＜0{

returnfalse

//每次减数都加2

}else{

minus+=2

}

}

returnfalse

}

算法性能分析

这种方法的时间复杂度仍然为O(n^0.5)。由于方法一使用的是乘法操作，这种方法采用的是减法操作，因此，这种方法的执行效率比方法一更高。[考点]如何判断一个自然数是否是某个数的平方

2.

题目描述：

何判断一个数是否为2的n次方?正确答案：方法一：构造法

2的n次方可以表示为：2^0，2^1，2^2…，2^n，如果一个数是2的n次方，那么最直观的想法是对1执行了移位操作(每次左移一位)，即通过移位得到的值必定是2的n次方(针对n的所有取值构造出所有可能的值)。所以，要想判断一个数是否为2的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次方")

}

}

程序的运行结果为

8能表示成2的n次方

9不能表示成2的n次方

算法性能分析：

上述算法的时间复杂度为O(logn)。

方法二：与操作法

那么是否存在效率更高的算法呢?通过对2^0，2^1，2^2，…，2^n进行分析，发现这些数字的二进制形式分别为：1，10，100，…。从二进制的表示可以看出，如果一个数是2的n次方，那么这个数对应的二进制表示中有且只有一位是1，其余位都为0。因此，判断一个数是否为2的n次方可以转换为这个数对应的二进制表示中是否只有一位为1。如果一个数的二进制表示中只有一位是1，例如num=00010000，那么num-1的二进制表示为num-1=00001111，由于num与num-1二进制表示中每一位都不相同，因此，num&(num-1)的运算结果为0。可以利用这种方法来判断一个数是否为2的n次方。实现代码如下：

funcisPower2(nint)bool{

if(n＜1){

returnfalse

}

returnn&(n-1)==0

}

算法性能分析：

这种方法的时间复杂度为O(1)。[考点]何判断一个数是否为2的n次方

3.

题目描述：

如何不使用除法操作符实现两个正整数的除法?正确答案：方法一：减法

主要思路为：使被除数不断减去除数，直到相减的结果小于除数为止，此时，商就为相减的次数，余数为最后相减的差。例如在计算14除以4的时候，首先计算14-4=10，由于10＞4，继续做减法运算：10-4=6，6-4=2，此时2＜4。由于总共进行了3次减法操作，最终相减的结果为2，因此，15除以4的商为3，余数为2。如果被除数比除数都小，那么商为0，余数为被除数。根据这个思路的实现代码如下：

packagemain

import(

"fmt"

)

//方法功能：计算两个自然数的除法

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

res=0

remain=m

//被除数减除数，直到相减结果小于除数为止

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,"余数:",remain)

}

程序的运行结果为

14除以4商为：3余数为：2

算法性能分析

这种方法循环的次数为m/n，因此，算法的时间复杂度为O(m/n)。需要注意的是，这种方法也实现了不用除法操作符实现除法运算的目的。

方法二：移位法

方法一所采用的减法操作，还可以用等价的加法操作来实现。例如在计算17除以4的时候，可以尝试4*1，4*2(4+4)，4*3(4+4+4)依次进行计算，直到计算的结果大于14的时候就可以很容易求出商与余数。但是这种方法每次都递增4，效率较低。下面给出另外一种增加递增速度的方法：以2的指数进行递增(取2的指数的原因是，2的指数操作可以通过移位操作来实现，有更高的效率)，计算4*1，4*2，4*4，4*8，由于4*8＞17，然后接着对17-4*4=1进入下一次循环用相同的方法进行计算。实现代码如下：

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

res=0

form＞=n{

multi:=1

//multi*n＞m/2(即2*multi*n＞m)时结束循环

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

multi＜＜=1

}

res+=multi

//相减的结果进入下次循环

m-=multi*n

}

remain=m

return

}

算法性能分析：

由于这种方法采用指数级的增长方式不断逼近m/n，因此，算法的时间复杂度为O(log(m/n))。[考点]如何不使用除法操作符实现两个正整数的除法

4.

题目描述：

如何只使用++操作符实现加减乘除运算正确答案：本题要求只能使用++操作来实现加减乘除运算，下面重点介绍用++操作来实现加减乘除运算的方法：

(1)加法操作：实现a+b的基本思路为对a执行b次++操作即可。

(2)减法操作：实现a-b(a＞=b)的基本思路为：不断对b执行++操作，直到等于a为止，在这个过程中记录执行++操作的次数。

(3)乘法操作：实现a*b的基本思路为：利用已经实现的加法操作把a相加b次，就得到了a*b的值。

(4)除法操作：实现a/b的基本思路为：利用乘法操作，使b不断乘以1，2，…，n，直到b*n＞b时，就可以得到商为n-1。

根据以上思路，实现代码如下：

packagemain

import(

"fmt"

)

//用++实现加法操作(限制条件：至少有一个非负数)

funcadd(a,bint)int{

ifa＜0&&b＜0{

fmt.Println("无法用++操作实现")

return-1

}

ifb＞=0{

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

a++

}

returna

}else{

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

b++

}

returnb

}

}

//用++实现加减法操作(限制条件：被减数大于减数)

funcminus(a,bint)int{

if(a＜b){

fmt.Println("无法用++操作实现")

return-1

}

result:=0

for;b!=a;b++{

result++

}

returnresult

}

//用++实现加乘法操作(限制条件：两个数都为整数)

funcmulti(a,bint)int{

ifa＜=0||b＜=0{

fmt.Println("无法用++操作实现")

return-1

}

result:=0

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

result=add(result,a)

}

returnresult

}

//用++实现加法除法操作(限制条件：两个数都为整数)

funcdivide(a,bint)int{

ifa＜=0||b＜=0{

fmt.Println("无法用++操作实现")

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

}

程序的运行结果为

-2

6

8

2

此处，在实现加法操作的时候，如果a与b都是整数，那么可以选择比较小的数进行循环，从而可以提高算法的性能。[考点]如何只使用++操作符实现加减乘除运算

5.

题目描述：

已知随机数生成函数rand7()能产生的随机数是整数1～7的均匀分布，如何构造rand10()函数，使其产生的随机数是整数1～10的均匀分布。正确答案：要保证rand10()产生的随机数是整数1～10的均匀分布，可以构造一个1～10*n的均匀分布的随机整数区间(n为任何正整数)。假设x是这个1～10*n区间上的一个随机数，那么x%10+1就是均匀分布在1～10区间上的整数。

根据题意，rand7()函数返回1到7的随机数，那么rand7()-1则得到一个离散整数集合，该集合为{0，1，2，3，4，5，6}，该集合中每个整数的出现概率都为1/7。那么(rand7()-1)*7得到另一个离散整数集合A，该集合元素为7的整数倍，即A={0，7，14，21，28，35，42}，其中，每个整数的出现概率也都为1/7。而由于rand7()得到的集合B={1，2，3，4，5，6，7}，其中每个整数出现的概率也为1/7。显然集合A与集合B中任何两个元素和组合可以与1～49之间的一个整数一一对应，即1～49之间的任何一个数，可以唯一地确定A和B中两个元素的一种组合方式，这个结论反过来也成立。由于集合A和集合B中元素可以看成是独立事件，根据独立事件的概率公式