Python程序员面试分类真题17

Python程序员面试分类真题171.

如何判断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。根据以上思路实现代码如下：

defzeroCount(n):

count=0

whilen＞0:

n=n/5

count+=n

returncount

if__name__=="__main__":

print"1024!末尾0的个数为:"+str(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，根据这个思路实现代码如下：

defmaxs(a,b):

return((a+b)+abs(a-b)/2)

if__name__=="__main__":

printmaxs(5,6)

程序的运行结果为：

6

需要注意的是，由于宏定义不同于函数定义，在上述宏定义中，a，b必须要有括号，否则当a，b的值为表达式的时候会出现意想不到的错误。[考点]如何按要求比较两个数的大小

3.

一个有序数列，序列中的每一个值都能够被2或者3或者5所整除，1是这个序列的第一个元素。求第1500个值是多少。正确答案：方法一：蛮力法

最简单的方法就是用一个计数器来记录满足条件的整数的个数，然后从1开始遍历整数，如果当前遍历的数能被2或者3或者5整除，那么计数器的值加1，当计数器的值为1500时，当前遍历到的值就是所要求的值。根据这个思路实现代码如下：

defsearth(n):

i=0

count=0

i=1

whileTrue:

ifi%2==0ori%3==0ori%5==0:

count+=1

ifcount==n:

break

i+=1

returni

if__name__=="__main__":

printsearth(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。根据这个思路实现代码如下：

defsearth(n):

a=[0,2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30]

ret=(n/22)*30+a[n%22]

returnret

算法性能分析：

方法二的时间复杂度为O(1)，此外，方法二使用了22个额外的存储空间。方法二的计算方法可以用来分析方法一的执行效率，从方法二的实现代码可以得出，方法一中循环执行的次数为(N/22)*30+a[N%22]，其中a[N%22]的取值范围为2～30，因此方法一的时间复杂度为O(N)。[考点]如何求有序数列的第1500个数的值

4.

如何把十进制数(long型)分别以二进制和十六进制形式输出正确答案：Python的左移N位代表乘以2的N次方，右移代表除以2的N次方。因此先将数值右移i位，得到除以2的i次方(整除)后的数值b，如10除以2的0次方，得到b=10；再取b整除2后的余数0，即二进制的最后一位，以此类推，得到10转换2进制的结果1010；二进制的位数有64位，以位数为上限，对输入的10进制数字进行循环转换操作，当循环达64次时终止，示例代码如下：

defintToBinary(n):

hexNum=8*8#二进制的位数(long占8个字节)

bit=[]

foriinrange(hexNum):

b=n＞＞i

c,d=divmod(b,2)

bit.append(str(d))

return"join(bit[::-1])

defintToHex(s):

hexs=""

remainder=0

whiles!=0:

remainder=s%16

ifremainder＜10:

hexs=str(remainder+int('0'))+hexs

else:

hexs=str(remainder-10+ord('A'))+hexs

s=s＞＞4

returnchr(int(hexs))

if__name__=="__main__":

print"10的二进制输出为:"+intToBinary(long(10))

print"10的十六进制输出为:"+intToHex(long(10))

程序的运行结果为：

10的二进制输出为：

0000000000000000000000000000000000000000000000000000000000001010

10的十六进制输出为：A[考点]如何把十进制数(long型)分别以二进制和十六进制形式输出

5.

给定一个整数，输出这个整数的二进制表示中1的个数。例如：给定整数7，其二进制表示为111，因此输出结果为3。正确答案：方法一：移位法

可以采用位操作来完成。具体思路如下：首先，判断这个数的最后一位是否为1，如果为1，那么计数器加1，然后，通过右移丢弃掉最后一位，循环执行该操作直到这个数等于0为止。在判断二进制表示的最后一位是否为1时，可以采用与运算来达到这个目的。具体实现代码如下：

#判断n二进制码中1的个数

defcountOne(n):

count=0#用来计数

whilen＞0:

if(n&1)==1:#判断最后一位是否为1

count+=1

n＞＞1#移位丢掉最后一位

returncount

if__name__=="__main__":

printcountOne(7)

printcountOne(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的个数，实现代码如下：

defcountOne(n):

count=0#用来计数

whilen＞0:

ifn!=0:#判断最后一