Python程序員面試分類(lèi)真題17

Python程序員面試分類(lèi)真題171.

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

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

方法二：因子法

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

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

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

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

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

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

defzeroCount(n):

count=0

whilen＞0:

n=n/5

count+=n

returncount

if__name__=="__main__":

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

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

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

算法性能分析：

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

2.

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

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

defmaxs(a,b):

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

if__name__=="__main__":

printmaxs(5,6)

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

6

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

3.

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

最簡(jiǎn)單的方法就是用一個(gè)計(jì)數(shù)器來(lái)記錄滿(mǎn)足條件的整數(shù)的個(gè)數(shù)，然后從1開(kāi)始遍歷整數(shù)，如果當(dāng)前遍歷的數(shù)能被2或者3或者5整除，那么計(jì)數(shù)器的值加1，當(dāng)計(jì)數(shù)器的值為1500時(shí)，當(dāng)前遍歷到的值就是所要求的值。根據(jù)這個(gè)思路實(shí)現(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)

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

2045

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

首先可以很容易得到2，3和5的最小公倍數(shù)為30，此外，1～30這個(gè)區(qū)間內(nèi)滿(mǎn)足條件的數(shù)有22個(gè){2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30}，由于最小公倍數(shù)為30，我們可以猜想，滿(mǎn)足條件的數(shù)字是否具有周期性(周期為30)昵?通過(guò)計(jì)算可以發(fā)現(xiàn)，31～60這個(gè)區(qū)間內(nèi)滿(mǎn)足條件的數(shù)也恰好有22個(gè){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)這些滿(mǎn)足條件的數(shù)具有周期性(周期為30)。由于1500/22=68，1500%68=4，從而可以得出第1500個(gè)數(shù)經(jīng)過(guò)了68個(gè)周期，然后在第69個(gè)周期中取第四個(gè)滿(mǎn)足條件的數(shù){2,3,4,5}。從而可以得出第1500個(gè)數(shù)為68*30+5=2045。根據(jù)這個(gè)思路實(shí)現(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

算法性能分析：

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

4.

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

defintToBinary(n):

hexNum=8*8#二進(jìn)制的位數(shù)(long占8個(gè)字節(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的二進(jìn)制輸出為:"+intToBinary(long(10))

print"10的十六進(jìn)制輸出為:"+intToHex(long(10))

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

10的二進(jìn)制輸出為：

0000000000000000000000000000000000000000000000000000000000001010

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

5.

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

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

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

defcountOne(n):

count=0#用來(lái)計(jì)數(shù)

whilen＞0:

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

count+=1

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

returncount

if__name__=="__main__":

printcountOne(7)

printcountOne(8)

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

3

1

算法性能分析：

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

方法二：與操作法

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

defcountOne(n):

count=0#用來(lái)計(jì)數(shù)

whilen＞0:

ifn!=0:#判斷最后一