Python程序員面試分類真題17

Python程序員面試分類真題171.

如何判斷1024!末尾有多少個0正確答案：方法一：蠻力法

最簡單的方法就是計算出1024!的值，然后判斷末尾有多少個0，但是這種方法有兩個非常大的缺點：（江南博哥）第一，算法的效率非常低下；第二，當(dāng)這個數(shù)字比較大的時候直接計算階乘可能會導(dǎo)致數(shù)據(jù)溢出，從而導(dǎo)致計算結(jié)果出現(xiàn)偏差。因此，下面給出一種比較巧妙的方法。

方法二：因子法

5與任何一個偶數(shù)相乘都會增加末尾0的個數(shù)，由于偶數(shù)的個數(shù)肯定比5的個數(shù)多，因此，1～1024所有數(shù)字中有5的因子的數(shù)字的個數(shù)決定了1024!末尾0的個數(shù)。因此，只需要統(tǒng)計因子5的個數(shù)即可。此外5與偶數(shù)相乘會使末尾增加一個0，25(有兩個因子5)與偶數(shù)相乘會使末尾增加兩個0，125(有三個因子5)與偶數(shù)相乘會使末尾增加3個0，625(有四個因子5)與偶數(shù)相乘會使末尾增加四個0。對于本題而言：

是5的倍數(shù)的數(shù)有：a1=1024/5=204個；

是25的倍數(shù)的數(shù)有：a2=1024/25=40個(a1計算了25中的一個因子5)；

是125的倍數(shù)的數(shù)有：a3=1024/125=8個(a1，a2分別計算了125中的一個因子5)；

是625的倍數(shù)的數(shù)有：a4=1024/625=1個(a1，a2，a3分別計算了625中的一個因子5)。

所以，1024!中總共有a1+a2+a3+a4=204+40+8+1=253個因子5。因此，末尾總共有253個0。根據(jù)以上思路實現(xiàn)代碼如下：

defzeroCount(n):

count=0

whilen＞0:

n=n/5

count+=n

returncount

if__name__=="__main__":

print"1024!末尾0的個數(shù)為:"+str(zeroCount(1024))

程序的運行結(jié)果為：

1024!末尾0的個數(shù)為：253

算法性能分析：

由于這種方法循環(huán)的次數(shù)為n/5，因此算法時間復(fù)雜度為O(n)。[考點]如何判斷1024!末尾有多少個0

2.

如何比較a、b兩個數(shù)的大小?不能使用大于、小于以及if語句。正確答案：絕對值法

根據(jù)絕對值的性質(zhì)可知，如果|a-b|==a-b，那么max(a,b)=a，否則max(a,b)=b，根據(jù)這個思路實現(xiàn)代碼如下：

defmaxs(a,b):

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

if__name__=="__main__":

printmaxs(5,6)

程序的運行結(jié)果為：

6

需要注意的是，由于宏定義不同于函數(shù)定義，在上述宏定義中，a，b必須要有括號，否則當(dāng)a，b的值為表達式的時候會出現(xiàn)意想不到的錯誤。[考點]如何按要求比較兩個數(shù)的大小

3.

一個有序數(shù)列，序列中的每一個值都能夠被2或者3或者5所整除，1是這個序列的第一個元素。求第1500個值是多少。正確答案：方法一：蠻力法

最簡單的方法就是用一個計數(shù)器來記錄滿足條件的整數(shù)的個數(shù)，然后從1開始遍歷整數(shù)，如果當(dāng)前遍歷的數(shù)能被2或者3或者5整除，那么計數(shù)器的值加1，當(dāng)計數(shù)器的值為1500時，當(dāng)前遍歷到的值就是所要求的值。根據(jù)這個思路實現(xiàn)代碼如下：

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)

程序的運行結(jié)果為：

2045

方法二：數(shù)字規(guī)律法

首先可以很容易得到2，3和5的最小公倍數(shù)為30，此外，1～30這個區(qū)間內(nèi)滿足條件的數(shù)有22個{2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30}，由于最小公倍數(shù)為30，我們可以猜想，滿足條件的數(shù)字是否具有周期性(周期為30)昵?通過計算可以發(fā)現(xiàn)，31～60這個區(qū)間內(nèi)滿足條件的數(shù)也恰好有22個{32,33,34,35,36,38,39,40,42,44,45,46,48,50,51,52,54,55,56,57,58,60}，從而發(fā)現(xiàn)這些滿足條件的數(shù)具有周期性(周期為30)。由于1500/22=68，1500%68=4，從而可以得出第1500個數(shù)經(jīng)過了68個周期，然后在第69個周期中取第四個滿足條件的數(shù){2,3,4,5}。從而可以得出第1500個數(shù)為68*30+5=2045。根據(jù)這個思路實現(xiàn)代碼如下：

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

算法性能分析：

方法二的時間復(fù)雜度為O(1)，此外，方法二使用了22個額外的存儲空間。方法二的計算方法可以用來分析方法一的執(zhí)行效率，從方法二的實現(xiàn)代碼可以得出，方法一中循環(huán)執(zhí)行的次數(shù)為(N/22)*30+a[N%22]，其中a[N%22]的取值范圍為2～30，因此方法一的時間復(fù)雜度為O(N)。[考點]如何求有序數(shù)列的第1500個數(shù)的值

4.

如何把十進制數(shù)(long型)分別以二進制和十六進制形式輸出正確答案：Python的左移N位代表乘以2的N次方，右移代表除以2的N次方。因此先將數(shù)值右移i位，得到除以2的i次方(整除)后的數(shù)值b，如10除以2的0次方，得到b=10；再取b整除2后的余數(shù)0，即二進制的最后一位，以此類推，得到10轉(zhuǎn)換2進制的結(jié)果1010；二進制的位數(shù)有64位，以位數(shù)為上限，對輸入的10進制數(shù)字進行循環(huán)轉(zhuǎn)換操作，當(dāng)循環(huán)達64次時終止，示例代碼如下：

defintToBinary(n):

hexNum=8*8#二進制的位數(shù)(long占8個字節(jié))

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

程序的運行結(jié)果為：

10的二進制輸出為：

0000000000000000000000000000000000000000000000000000000000001010

10的十六進制輸出為：A[考點]如何把十進制數(shù)(long型)分別以二進制和十六進制形式輸出

5.

給定一個整數(shù)，輸出這個整數(shù)的二進制表示中1的個數(shù)。例如：給定整數(shù)7，其二進制表示為111，因此輸出結(jié)果為3。正確答案：方法一：移位法

可以采用位操作來完成。具體思路如下：首先，判斷這個數(shù)的最后一位是否為1，如果為1，那么計數(shù)器加1，然后，通過右移丟棄掉最后一位，循環(huán)執(zhí)行該操作直到這個數(shù)等于0為止。在判斷二進制表示的最后一位是否為1時，可以采用與運算來達到這個目的。具體實現(xiàn)代碼如下：

#判斷n二進制碼中1的個數(shù)

defcountOne(n):

count=0#用來計數(shù)

whilen＞0:

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

count+=1

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

returncount

if__name__=="__main__":

printcountOne(7)

printcountOne(8)

程序的運行結(jié)果為：

3

1

算法性能分析：

這種方法的時間復(fù)雜度為O(N)，其中N代表二進制數(shù)的位數(shù)。

方法二：與操作法

給定一個數(shù)n，每進行一次n&(n-1)計算，其結(jié)果中都會少了一位1，而且是最后一位。例如，n=6，其對應(yīng)的二進制表示為110，n-1=5，對應(yīng)的二進制表示為101，n&(n-1)運算后的二進制表示為100，其效果就是去掉了110中最后一位1?？梢酝ㄟ^不斷地用n&(n-1)操作去掉n中最后一位1的方法求出n中1的個數(shù)，實現(xiàn)代碼如下：

defcountOne(n):

count=0#用來計數(shù)

whilen＞0:

ifn!=0:#判斷最后一