Python程序員面試分類真題19

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

用1、2、2、3、4、5這六個數(shù)字，寫一個main函數(shù)，打印出所有不同的排列，例如：512234、412345等，要求：“4”不能在第三位，“3”與“5”不能相連。（江南博哥）正確答案：打印數(shù)字的排列組合方式的最簡單的方法就是遞歸，但本題存在兩個難點：第一，數(shù)字中存在重復(fù)數(shù)字，第二，明確規(guī)定了某些位的特性。顯然，采用常規(guī)的求解方法似乎不能完全適用了。

其實，可以換一種思維，把求解這6個數(shù)字的排列組合問題轉(zhuǎn)換為大家都熟悉的圖的遍歷的問題，解答起來就容易多了?？梢园?、2、2、3、4、5這6個數(shù)看成是圖的6個結(jié)點，對這6個結(jié)點兩兩相連可以組成一個無向連通圖，這6個數(shù)對應(yīng)的全排列等價于從這個圖中各個結(jié)點出發(fā)深度優(yōu)先遍歷這個圖中所有可能路徑所組成的數(shù)字集合。例如，從結(jié)點“1”出發(fā)所有的遍歷路徑組成了以“1”開頭的所有數(shù)字的組合。由于“3”與“5”不能相連，因此，在構(gòu)造圖的時候使圖中“3”和“5”對應(yīng)的結(jié)點不連通就可以滿足這個條件。對于“4”不能在第三位，可以在遍歷結(jié)束后判斷是否滿足這個條件。

具體而言，實現(xiàn)步驟如下所示：

(1)用1、2、2、3、4、5這6個數(shù)作為6個結(jié)點，構(gòu)造一個無向連通圖。除了“3”與“5”不連通外，其他的所有結(jié)點都兩兩相連。

(2)分別從這6個結(jié)點出發(fā)對圖做深度優(yōu)先遍歷。每次遍歷完所有結(jié)點的時候，把遍歷的路徑對應(yīng)數(shù)字的組合記錄下來，如果這個數(shù)字的第三位不是“4”，那么把這個數(shù)字存放到集合Set中(由于這6個數(shù)中有重復(fù)的數(shù)，因此，最終的組合肯定也會有重復(fù)的。由于集合Set的特點為集合中的元素是唯一的，不能有重復(fù)的元素，因此，通過把組合的結(jié)果放到Set中可以過濾掉重復(fù)的組合)。

(3)遍歷Set集合，打印出集合中所有的結(jié)果，這些結(jié)果就是本問題的答案。

實現(xiàn)代碼如下：

classTest:

def__init__(self,arr):

#self.numbers=[1,2,2,3,4,5]

self.numbers=arr

#用來標記圖中結(jié)點是否被遍歷過

self.visited=[None]*len(self.numbers)

#圖的二維數(shù)組表示

self.graph=[([None]*len(self.numbers))foriinrange(len(self.numbers))]

self.n=6

#用來標記圖中結(jié)點是否被遍歷過

#self.visited=None

#圖的二維數(shù)組表示

#self.graph=None

#數(shù)字的組合

bination="

#存放所有的組合

self.s=set()

"""

**方法功能:對圖從結(jié)點start位置開始進行深度遍歷

**輸入?yún)?shù):start:遍歷的起始位置

"""

defdepthFirstSearch(self,start):

self.visited[start]=True

bination+=str(self.numbers[start])

iflen(bination)==self.n:

#4不出現(xiàn)在第三個位置

ifbination.index("4")!=2:

self.s.add((bination))

j=0

whilej＜self.n:

ifself.graph[start][j]==1andself.visited[j]=False:

self.depthFirstSearch(j)

j+=1

bination=bination[:-1]

self.visited[start]=False

#方法功能:獲取1、2、2、3、4、5的左右組合,使得"4"不能在第三位,"3"與"5"不能相連

defgetAllCombinations(self):

#構(gòu)造圖

i=0

whilei＜self,n:

j=0

whilej＜self.n:

ifi==j:

self.graph[i][j]=0

else:

self.graph[i][j]=1

j+=1

i+=1

#確保在遍歷的時候3與5是不可達的

self.graph[3][5]=0

self.graph[5][3]=0

#分別從不同的結(jié)點出發(fā)深度遍歷圖

i=0

whilei＜self.n:

self.depthFirstSearch(i)

i+=1

defprintAllCombinations(self):

forstrsinself.s:

printstrs,

if__name__=="__main__":

arr=[1,2,2,3,4,5]

t=Test(arr)

t.getAllCombinations()

#打印所有組合

t.printAllCombinations()

由于結(jié)果過多，因此這里就不列出詳細的運行結(jié)果了。[考點]如何求數(shù)字的組合

2.

10個房間里放著數(shù)量隨機的金幣。每個房間只能進入一次，并只能在一個房間中拿金幣。一個人采取如下策略：前4個房間只看不拿。隨后的房間只要看到比前4個房間都多的金幣數(shù)，就拿。否則就拿最后一個房間的金幣。編程計算這種策略拿到最多金幣的概率。正確答案：這道題要求一個概率的問題，由于10個房間里放的金幣的數(shù)量是隨機的，因此，在編程實現(xiàn)的時候首先需要生成10個隨機數(shù)來模擬10個房間里金幣的數(shù)量。然后判斷通過這種策略是否能邑拿到最多的金幣。如果僅僅通過一次模擬來求拿到最多金幣的概率顯然是不準確的，那么就需要進行多次模擬，通過記錄模擬的次數(shù)m，拿到最多金幣的次數(shù)n，從而可以計算出拿到最多金幣的概率n/m。顯然這個概率與金幣的數(shù)量以及模擬的次數(shù)有關(guān)系。模擬的次數(shù)越多越能接近真實值。下面以金幣數(shù)為1到10的隨機數(shù)，模擬次數(shù)為1000次為例給出實現(xiàn)代碼：

importrandom

"""

方法功能:總共n個房間,判斷用指定的策略是否能拿到最多金幣

返回值:如果能拿到返回True,否則返回False

"""

defgetMaxNum(n):

ifn＜1:

print"參數(shù)不合法"

return

a=[None]*n

#隨機生成n個房問里金幣的個數(shù)

i=0

whilei＜n:

a[i]=random.uniform(1,n)#生成1～n的隨機數(shù)

i+=1

#找出前四個房間中最多的金幣個數(shù)

max4=0

i=0

whilei＜4:

ifa[i]＞max4:

max4=a[i]

i+=1

i=4

whilei＜n-1:

ifa[i]＞max4:#能拿到最多的金幣

returnTrue

i+=1

returnFalse#不能拿到最多的金幣

if__name__=="__main__":

monitorCount=1000+0.0

success=0

i=0

whilei＜monitorCount:

ifgetMaxNum(10):

success+=1

i+=1

printsuccess/monitorCount

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

0.421

運行結(jié)果分析：

運行結(jié)果與金幣個數(shù)的選擇以及模擬的次數(shù)都有關(guān)系，而且由于是個隨機問題，因此同樣的程序每次的運行結(jié)果也會不同。[考點]如何拿到最多金幣

3.

給定一個正整數(shù)n，求解出所有和為n的整數(shù)組合，要求組合按照遞增方式展示，而且唯一。例如：4=1+1+1+1、1+1+2、1+3、2+2、4(4+0)。正確答案：以數(shù)值4為例，和為4的所有的整數(shù)組合一定都小于4(1,2,3,4)。首先選擇數(shù)字1，然后用遞歸的方法求和為3(4-1)的組合，一直遞歸下去直到用遞歸求和為0的組合的時候，所選的數(shù)字序列就是一個和為4的數(shù)字組合。然后第二次選擇2，接著用遞歸求和為2(4-2)的組合；同理下一次選3，然后用遞歸求和為1(4-3)的所有組合。依此類推，直到找出所有的組合為止，實現(xiàn)代碼如下：

"""

方法功能:求和為sums的所有整數(shù)組合

輸入?yún)?shù):sums正整數(shù),result存儲組合結(jié)果,count記錄組合中數(shù)字的個數(shù)

"""

defgetAllCombination(sums,result,count):

ifsums＜0:

return

#數(shù)字的組合滿足和為sums的條件,打印出所有組合

ifsums==0:

prrnt"滿足條件的組合:".

i=0

whilei＜count:

printresult[i],

i+=1

print'\n'

return

#打印debug信息,為了便于理解

print"----當前組合:",

i=0

whilei＜count:

printstr(result[i]),

i+=1

print"----"

#確定組合中下一個取值

i=(1ifcount==0elseresult[count-1])

print"---"+"i="+str(i)+"count="+str(count)+"---"#打印debug信息,為了便于理解

whilei＜=sums:

result[count]=i

count+=1

getAllCombination(sums-i,result,count)#求和為sums-i的組合

count-=1#遞歸完成后,去掉最后一個組合的數(shù)字

i+=1#找下一個數(shù)字作為組合中的數(shù)字

#方法功能:找出和為n的所有整數(shù)的組合

defshowAllCombination(n):

ifn＜1:

print"參數(shù)不滿足要求"

return

result=[None]*n#存儲和為n的組合方式

getAllCombination(n,result,0)

if__name__=="__main__":

showAllCombination(4)

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

----當前組合:----

---i=1count=0---

----當前組合:1----

---i=1count=1---

----當前組合:11----

---i=1count=2---

----當前組合:111----

---i=1count=3---

滿足條件的組合:1111

滿足條件的組合:112

----當前組合:12----

---i=2count=2---

滿足條件的組合:13

----當前組合:2----

---i=2count=1---

滿足條件的組合:22

----當前組合:3----

----i=3count=1---

滿足條件的組合:4

運行結(jié)果分析：

從上面運行結(jié)果可以看出，滿足條件的組合為：{1，1，1，1}，{1，1，2}，{1，3}，{2，2}，{4}，其他的為調(diào)試信息。從打印出的信息可以看出：在求和為4的組合中，第一步選擇了1；然后求3(4-1)的組合也選了1，求2(3-1)的組合的第一步也選擇了1，依次類推，找出第一個組合為{1，1，1，1}。然后通過count-和i+找出最后兩個數(shù)字1與1的另外一種組合2，最后三個數(shù)字的另外一種組合3；接下來用同樣的方法分別選擇2，3作為組合的第一個數(shù)字，就可以得到以上結(jié)果。

代碼i=(count==0?1:result[count-1]);用來保證：組合中的下一個數(shù)字一定不會小于前一個數(shù)字，從而保證了組合的遞增性。如果不要求遞增(例如把{1，1，2}和{2，1，1}看作兩種組合)，那么把上面一行代碼改成i=1即可。[考點]如何求正整數(shù)n所有可能的整數(shù)組合

4.

有一個函數(shù)func1能返回0和1兩個值，返回0和1的概率都是1/2，問怎么利用這個函數(shù)得到另一個函數(shù)func2，使func2也只能返回0和1，且返回0的概率為1/4，返回1的概率為3/4。正確答案：func1得到1與0的概率都為1/2。因此，可以調(diào)用兩次func1，分別生成兩個值a1與a2，用這兩個數(shù)組成一個二進制a2a1，它的取值的可能性為00，01，10，11，并且得到每個值的概率都為(1/2)*(1/2)=1/4，因此，如果得到的結(jié)果為00，那么返回0(概率為1/4)，其他情況返回1(概率為3/4)。實現(xiàn)代碼如下：

importrandom

#返回0和1的概率都為1/2

deffunc1():

returnint(round(random.random())

#返回0的概率為1/4,返回1的概率為3/4

deffunc2():

a1=func1()

a2=func1()

tmp=a1

tmp1=(a2＜＜1)

iftmp==0:

return0

else:

return1

if__name__=="__main__":

i=0

whilei＜16:

printfunc2(),

i+=1

print'\n'

i=0

whilei＜16:

printfunc2(),

i+=1

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

1110110110111101

1111111111000010

由于結(jié)果是隨機的，調(diào)用的次數(shù)越大，返回的結(jié)果就越接近1/4與3/4。[考點]如何用一個隨機函數(shù)得到另外一個隨機函數(shù)

5.

隨機地從大小為n的數(shù)組中選取m個整數(shù)，要求每個元素被選中的概率相等。正確答案：從n個數(shù)中隨機選出一個數(shù)的概率為1/n，然后在剩下的n-1個數(shù)中再隨機找出一個數(shù)的概率也為1/n(第一次沒選中這個數(shù)的概率為(n-1)/n，第二次選中這個數(shù)的概率為1/(n-1)，因此，隨機選出第二個數(shù)的概率為((n-1)/n)*(1/(n-1))=1/n)，依次類推，在剩下的k個數(shù)中隨機選出一個元素的概率都為1/n。因此，這種方法的思路為：首先從有n個元素的數(shù)組中隨機選出一個元素，然后把這個選中的數(shù)字與數(shù)組第一個元素交換，接著從數(shù)組后面的n-1個數(shù)字中隨機選出1個數(shù)字與數(shù)組第二個元素交換，依次類推，直到選出m個數(shù)字為止，數(shù)組前m個數(shù)字就是隨機選出來的m個數(shù)字，且它們被選中的概率相等。實現(xiàn)代碼如下：

importrandom

defgetRandomM(a,n,m):

ifa==Noneorn＜=0orn＜m:

print"參數(shù)不合理"

return

i=0

whilei＜m:

j=random.randint(i,n-1)#//獲取i到n-1間的隨機數(shù)

#隨機選出的元素放到數(shù)組的前面

tmp=a[i]

a[i]=a[j]

a[j]=tmp

i+=1

if__name__=="__main__":

a=[1,2,3,4,5,6,7,8,9,10]

n=10

m=6

getRandomM(a,n,m)

i=0

whilei＜m:

printa[i],

i+=1

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

1

8

9

7

2

4

算法性能分析：

這種方法的時間復(fù)雜度為O(m)。[考點]如何等概率地從大小為n的數(shù)組中選取m個整數(shù)

6.

求出用1，2，5這三個數(shù)不同個數(shù)組合的和為100的組合個數(shù)。為了更好地理解題目的意思，下面給出幾組可能的組合：100個1，0個2和0個5，它們的和為100；50個1，25個2，0個5的和也是100；50個1，20個2，2個5的和也為100。正確答案：方法一：蠻力法

最簡單的方法就是對所有的組合進行嘗試，然后判斷組合的結(jié)果是否滿足和為100，這些組合有如下限制：1的個數(shù)最多為100個，2的個數(shù)最多為50個，5的個數(shù)最多為20個。實現(xiàn)思路為：遍歷所有可能的組合l的個數(shù)x(0＜=x＜=100)，2的個數(shù)y(0=＜y＜=50)，5的個數(shù)z(0＜=z＜=20)，判斷x+2y+5z是否等于100，如果相等，那么滿足條件，實現(xiàn)代碼如下：

defcombinationCount(n):

count=0

num1=n#1最多的個數(shù)

num2=n/2#2最多的個數(shù)

num5=n/5#5最多的個數(shù)

x=0

whilex＜==num1:

y=0

whiley＜=num2:

z=0

whilez＜=num5:

ifx+2*y+5*z==n:#滿足條件

count+=1

z+=1

y+=1

x+=1

returncount

if__name__=="__main__":

printcombinationCount(100)

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

541

算法性能分析：

這種方法循環(huán)的次數(shù)為101*51*21。

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

針對這種數(shù)學(xué)公式的運算，一般都可以通過找出運算的規(guī)律進而簡化運算的過程，對于本題而言，對x+2y+5z=100進行變換可以得到x+5z=100-2y。從這個表達式可以看出，x+5z是偶數(shù)且x+5z＜=100。因此，求滿足x+2y+5z=100組合的個數(shù)就可以轉(zhuǎn)換為求滿足“x+5z是偶數(shù)且x+5z＜=100”的個數(shù)。可以通過對z的所有可能的取值(0＜=z＜=20)進行遍歷從而計算滿足條件的x的值。

當z=0時，x的取值為0，2，4，…，100(100以內(nèi)所有的偶數(shù))，個數(shù)為(100+2)/2

當z=1時，x的取值為1，3，5，…，95(95以內(nèi)所有的奇數(shù))，個數(shù)為(95+2)/2

當z=2時，x的取值為0，2，4，…，90(90以內(nèi)所有的偶數(shù))，個數(shù)為(90+2)/2

當z=3時，x的取值為1，3，5，…，85(85以內(nèi)所有的奇數(shù))，個數(shù)為(85+2)/2

當z-19時，x的取值為5，3，1(5以內(nèi)所有的奇數(shù))，個數(shù)為(5+2)/2

當z=20時，x的取值為0(0以內(nèi)所有的偶數(shù))，個數(shù)為(0+2)/2

根據(jù)這個思路，實現(xiàn)代碼如下：

defcombinationCount(n):

count=0

m=0

whilem＜=n:

count+=(m+2)/2

m+=5

returncount

算法性能分析：

這種方法循環(huán)的次數(shù)為21。[考點]如何組合1，2，5這三個數(shù)使其和為100

7.

100個燈泡排成一排，第一輪將所有燈泡打開；第二輪每隔一個燈泡關(guān)掉一個，即排在偶數(shù)的燈泡被關(guān)掉，第三輪每隔兩個燈泡，將開著的燈泡關(guān)掉，關(guān)掉的燈泡打開。依次類推，第100輪結(jié)束的時