#41032: C++詳解-DFS


toseanlin@gmail.com (Dr. SeanXD)

學校 : 康橋雙語學校
編號 : 158065
來源 : [24.147.249.5]
最後登入時間 :
2024-09-07 10:27:31
b573. 排列組合、最大公因數 -- 102學年度商業類程式設計競賽 | From: [220.136.106.26] | 發表日期 : 2024-06-27 09:04

使用 DFS 的方式來找不同組合的數字,測資中不會有相同的數字 (例如:22)。

設定一個空的字串存不同的數字組合、一個 Map 存已經加過哪些數字了。如果字串長度等於原始字串長度就可以將其存到一個陣列中,否則就跑一個 For迴圈,如果目前字元沒有在 Map 中有資料,就再互叫一次 DFS,要先將字串加上目前的字元並且 Map 也要更新,呼叫完之後記得要將字串和 Map 還原。

找到兩個數字之後就找其中一個數字的所有因數,再和另外一個數字一一判斷有哪些因數是相同的。

 

範例程式碼

 
ZeroJudge Forum