论述题1. 题目描述:
如何判断1024!末尾有多少个0
方法一:蛮力法
最简单的方法就是计算出1024!的值,然后判断末尾有多少个0,但是这种方法有两个非常大的缺点:第一,算法的效率非常低下;第二,当这个数字比较大的时候直接计算阶乘可能会导致数据溢出,从而导致计算结果出现偏差。因此,下面给出一种比较巧妙的方法。
方法二:因子法
5与任何一个偶数相乘都会增加末尾0的个数,由于偶数的个数肯定比5的个数多,因此,1~1024所有数字中有5的因子的数字的个数决定了1024!末尾0的个数。因此,只需要统计因子5的个数即可。此外5与偶数相乘会使末尾增加一个0,25(有两个因子5)与偶数相乘会使末尾增加两个0,125(有三个因子5)与偶数相乘会使末尾增加3个0,625(有四个因子5)与偶数相乘会使末尾增加四个0。对于本题而言:
是5的倍数的数有:a1=1024/5=204个
是25的倍数的数有:a2=1024/25=40个(a1计算了25中的一个因子5)
是125的倍数的数有:a3=1024/125=8个(a1,a2分别计算了125中的一个因子5)
是625的倍数的数有:a4=1024/625=1个(a1,a2,a3分别计算了625中的一个因子5)
所以,1024!中总共有a1+a2+a3+a4=204+40+8+1=253个因子5。因此,末尾总共有253个0。根据以上思路实现代码如下:
package main
import(
"fmt"
)
func zeroCount(n int)int{
count:=0
for n>0{
n=n/5
count+=n
}
return count
}
func main(){
fmt.Println("1024!末尾0的个数为:", zeroCount(1024))
}
程序的运行结果为
1024!末尾0的个数为:253
算法性能分析:
由于这种方法循环的次数为n/5,因此,算法时间复杂度为O(n)。
[考点] 如何判断1024!末尾有多少个0
2. 题目描述:
如何比较a、b两个数的大小,不能使用大于、小于以及if语句。
方法一:绝对值法
根据绝对值的性质可知,如果|a-b|==a-b,那么max(a,b)=a,否则max(a,b)=b,根据这个思路实现代码如下:
package main
import(
"fmt"
."github.com/isdamir/gotype"//引入定义的数据结构
)
func max1(a, b int)int{
ifAbs(a-b)==a-b{
return a
}else{
return b
}
}
func main(){
fmt.Println("绝对值法")
fmt.Println(max1(5, 6))
}
程序的运行结果为
6
需要注意的是,由于宏定义不同于函数定义,在上述宏定义中,a,b必须要有括号,否则当a,b的值为表达式的时候会出现意想不到的错误。
方法二:二进制法
如果a>b,那么a-b的二进制最高位为0,与任何数的与操作的结果还是0;如果a-b为负数,那么a-b的二进制最高位为1,与0x80000000(最高位为1,其他位为0,假设a与b都占4个字节)执行与操作之后为结果为1。由此根据两个数的差的二进制最高位的值就可以比较两个数的大小,实现代码如下:
func max2(a, b int)int{
if(a-b)&(1<<31)!=0{
return b
}else{
return a
}
}
[考点] 如何按要求比较两个数的大小
3. 题目描述:
一个有序数列,序列中的每一个值都能够被2或者3或者5所整除,1是这个序列的第一个元素。求第1500个值是多少。
方法一:蛮力法
最简单的方法就是用一个计数器来记录满足条件的整数的个数,然后从1开始遍历整数,如果当前遍历的数能被2或者3或者5整除,则计数器的值加1,当计数器的值为1500时,当前遍历到的值就是所要求的值。根据这个思路实现代码如下:
package main
import(
"fmt"
)
func searth1(n int)int{
i, count:=0, 0
fortrue{
i++
if(i%2==0 ||i%3==0 || i%5==0){
count++
}
if count==n{
break
}
}
return i
}
func main(){
fmt.Println("方法一")
fmt.Println(searthl(1500))
}
程序的运行结果为
2045
方法二:数字规律法
首先可以很容易得到2,3和5的最小公倍数为30,此外,1~30这个区间内满足条件的数有22个{2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30},由于最小公倍数为30,我们可以猜想,满足条件的数字是否具有周期性(周期为30)呢?通过计算可以发现,31~60这个区间内满足条件的数也恰好有22个{32,33,34,35,36,38,39,40,42,44,45,46,48,50,51,52,54,55,56,57,58,60},从而发现这些满足条件的数具有周期性(周期为30)。由于1500/22=68,1500%68=4,从而可以得出第1500个数经过了68个周期,然后在第69个周期中取第四个满足条件的数{2,3,4,5}。从而可以得出第1500个数为68*30+5=2045。根据这个思路实现代码如下:
func searth2(n int)int{
a:=[]int{0, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30}
return(n/22)*30+a[n%22]
}
算法性能分析:
方法二的时间复杂度为O(1),此外,方法二使用了22个额外的存储空间。方法二的计算方法可以用来分析方法一的执行效率,从方法二的实现代码可以得出,方法一中循环执行的次数为(n/22)*30+a[n%22],其中,a[n%22]的取值范围为2~30,因此,方法一的时间复杂度为O(n)。
[考点] 如何求有序数列的第1500个数的值
4. 题目描述:
如何把十进制数(long型)分别以二进制和十六进制形式输出?
由于十进制数本质上还是以二进制的方式来存储的,在实现的时候可以把十进制数看成二进制的格式,通过移位的方式计算出每一位的值。为了方便起见,下面以byte类型的数为例介绍实现方法,假如现在要把十进制数7以二进制的形式来输出,由于7的二进制的表示为00000111,计算第6位二进制码是0还是1的方法为:首先把这个值左移6位得到11000000,然后再右移7位,得到00000001,移位后得到的值就是第6位二进制码的值。由此可以得出如下计算方法:假设十进制数对应的二进制数的长度为binNum,那么计算十进制数n的第i位二进制码值的公式为n<<i>>binNum-1。通过这种计算方法可以得到每一位的值,然后把对应的值存储在字符数组中即可。
上面介绍的方法使用的是移位操作,虽然效率比较高,但是难以理解。下面介绍一种简单的转换为十六进制的方法。可以使用类似于十进制转二进制的方法。把十进制的数对16求余数。得到的结果就是十六进制的最后一位,然后把这个十进制数除以16,用得到的数继续使用相同的方法计算其他的位数。需要注意的是对于十六进制10~15需要转换为A~F。示例代码如下:
package mare
import(
"bytes"
"fmt"
)
func intToBinary(n int)string {
if n<0{
fmt.Println("不支持负数")
return""
}
hexNum:=8*8;//二进制的位数(long占8个字节)
var pBinary bytes.Buffer
fori:=0; i<hexNum; i++{
//先左移i位把pBinary[i]移到最高位,然后右移hexNum-1位把pBinary[i]移到最后一位
tmpBinary:=(n<<uint(i))>>(uint(hexNum)-1)
if(tmpBinary==0){
pBinary.WriteRune('0')
}else{
pBinary.WriteRune('1')
}
}
return pBinary.String()
}
func intToHex(s int)string{
hex:=""
remainder:=0
for s!=0{
remainder=s%16
if(remainder<10){
hex=string(remainder+'0')+hex
}else{
hex=string(remainder-10+'A')+hex
}
s=s>>4
}
return hex
}
func main(){
fmt.Println("10的二进制输出为:", intToBinary(10))
fmt.Println("10的十六进制输出为:", intToHex(10))
}
程序的运行结果为
10的二进制输出为:0000000000000000000000000000000000000000000000000000000000001010
10的十六进制输出为:A
[考点] 如何把十进制数(long型)分别以二进制和十六进制形式输出
5. 题目描述:
给定一个整数,输出这个整数的二进制表示中1的个数。例如:给定整数7,其二进制表示为111,因此,输出结果为3。
方法一:移位法
可以采用位操作来完成。具体思路如下:首先,判断这个数的最后一位是否为1,如果为1,则计数器加1,然后,通过右移丢弃掉最后一位,循环执行该操作直到这个数等于0为止。在判断二进制表示的最后一位是否为1时,可以采用与运算来达到这个目的。具体实现代码如下:
package main
import(
"fmt"
)
//判断二进制码中1的个数
func countOne1(n int)int{
count:=0//用来计数
for n>0{
if(n&1)==1{//判断最后一位是否为1
count++
}
n>>=1//移位丢掉最后一位
}
return count
}
func main(){
fmt.Println("方法一")
fmt.Println(CountOne1(7))
fmt.Println(countOne1(8))
}
程序的运行结果为
3
1
算法性能分析:
这种方法的时间复杂度为O(n),其中,n代表二进制数的位数。
方法二:与操作法
给定一个数n,每进行一次n&(n-1)计算,其结果中都会少了一位1,而且是最后一位。例如,n=6,其对应的二进制表示为110,n-1=5,对应的二进制表示为101,n&(n-1)运算后的二进制表示为100,其效果就是去掉了110中最后一位1。可以通过不断地用n&(n-1)操作去掉n中最后一位1的方法求出n中1的个数,实现代码如下:
func countOne2(n int)int{
count:=0//用来计数
for n>0{
if n!=0{
n=n&(n-1)
}
count++
}
return count
}
算法性能分析:
这种方法的时间复杂度为O(m),其中,m为二进制数中1的个数,显然,当二进制数中1的个数比较少的时候,这种方法有更高的效率。
[考点] 如何求二进制数中1的个数