iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 5
0

經過前幾天的演算法,都需要小動腦和邏輯上的思考對吧?透過一些比較和分配的技巧,來做資料的排序。

今天,就來講講列舉法 (俗稱暴力破解法)。

列舉法 (Enumeration) 的想法非常的簡單,就是把所有可能都列出來就對啦!!!其中至少會有一組符合我們條件的答案。

舉例來說我們有一筆資料[1, 2, 3],並且想要知道所有的排列組合,我們只能從頭開始排列起,一一地將所有位置都列舉出來。

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

大概了解列舉法之後,這邊還有一個常見的例子。

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

https://ithelp.ithome.com.tw/upload/images/20181020/20111557LR25zC4vwr.jpg
將數字 1 到 9 填入上面的方程式,使之為 1 。
https://ithelp.ithome.com.tw/upload/images/20181020/20111557Cl5LFl9qPW.jpg
當然,第二個方程式是不成立的,所以這種時候就是使用 試誤法(Try and Error)列舉 來找出所有的可能,並一一試驗看符不符合方程式。

全部的程式碼:

from copy import copy
list_1to9=[1,2,3,4,5,6,7,8,9]

#在b層建一個新的1-9,然後pop掉取過的,C層再複製b取過的,建一個新的1-9,pop調取過的
#d層再複製c層取過的,建新的1-9.....以下同上。這樣就最後一行就不用再把取過的加回去了。

# 如果再稍稍修改,效率會再更好喔
for a in list_1to9:        # a從list_1to9取數字
	list_a=copy(list_1to9)   # list_a複製list_1to9
	list_a.remove(a)         # 將a選取的數字從list_a去除,留下可以繼續被選取的字給b
	for b in list_a:         # b從list_a取數字
		list_b=copy(list_a)  # list_b複製list_a
		list_b.remove(b)     # 將b選取的數字從list_b去除,留下可以繼續被選取的字給c
		for c in list_b:
			list_c=copy(list_b)
			list_c.remove(c)
			for d in list_c:
				list_d=copy(list_c)
				list_d.remove(d)
				for e in list_d:
					list_e=copy(list_d)
					list_e.remove(e)
					for f in list_e:
						list_f=copy(list_e)
						list_f.remove(f)
						for g in list_f:
							list_g=copy(list_f)
							list_g.remove(g)
							for h in list_g:
								list_h=copy(list_g)
								list_h.remove(h)
								for i in list_h:
                                    #這時候選取完所有的數字,並填入方程式進行驗證,如果為是,輸出結果;如果為否,則沿著迴圈h到迴圈a一一測試各種可能。
									if (a/(b*10.+c)+d/(e*10.+f)+g/(h*10.+i))==1: 
										print (a,b,c,d,e,f,g,h,i) 

拉蒙碎碎念

這次的程式碼是真的需要多花點時間思考,但如果用筆寫下來,會更清楚喔。
其實在資料量不大的時候,有時候也是可以偷偷用列舉法來找出所有可能,畢竟是電腦在算。而且你那小腦袋要裝的是 吃喝玩樂 更重要的演算法才對啊哈哈哈哈


上一篇
[演算法] 基數排序法 (Radix Sort)
下一篇
[資料結構] 陣列 (Array) & 串列 (Linked List)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言