Re: [問題] vector<int *> 會有 memory leak 問題嗎?
好久沒有寫這類型的程式了
基本上這種題目不外乎就是在產生數列時盡早砍掉可以砍的部分
因此使用 DFS 是一個很好的方向
將根部砍掉下面的枝葉就都不用算了
為了方便處理旋轉的問題
可以看一下以下,六芒星的圖形
O○
B○●●○A
● ●
○●●○
○
只要我們能夠保證空心的部分不會有旋轉重覆的狀況
實心部分我們就可以隨意排列
而鏡像的部分,我們只要保證在 O 點固定的情況下 A 的數字必小於 B
(因 A 大於 B 的情況必然可以使用 A 小於 B 的其中一組鏡像而來)
其它的所有數字我們亦能夠隨意排列
因此我們可以將數列編成以下的順序
0
5 11 6 1
10 7
4 9 8 2
3
留意我們將外圍的點編在 0 ~ 5 號
現在我們要做的就是保證產生不旋轉重覆的 0 ~ 5 號序列
並檢查此序列的 1 號必小於 5 號,問題就解決了
那麼,要怎麼產生不旋轉重複的 0 ~ 5 號序列呢?
想法與鏡像差不多,想像我們由小到大選擇 0 的數字,
那麼在 1 ~ 5 中任何頂點若包括比 0 處小的數字
都必然可由之前的數列中旋轉而來
現在我們有了產生六個頂點的程式
也有了基礎的 6 ~ 11 的排列組合程式
還剩下一件事情沒做
就是在數字足以產生第一個總合時將其記錄下來,
並在足以產生第二列總和時便確認其是否相等
如此一下又能砍掉剩下的第三列第四列的排列時間
好了,做完以上幾件事情,得到以下的程式
http://nopaste.csie.org/94360
要推廣到更多芒的星形,只需要將
#define STAR_CORNER 6
#define NUMBER_COUNT 12
int GetSum( int line);
bool EarlyCheck( int position);
這四個部分做相對應的修改即可
好了我們看結果
0 1 2 5 10 6 11 9 7 3 8 4
0 1 2 8 10 3 11 9 4 6 5 7
0 1 3 5 11 8 9 10 6 2 7 4
0 1 4 8 10 5 7 11 2 6 3 9
0 1 5 2 4 6 8 9 10 3 11 7
0 1 5 9 11 6 7 10 2 4 3 8
...
3 7 11 8 10 9 2 6 1 0 5 4
3 7 11 9 10 8 2 6 0 1 4 5
4 5 10 7 9 11 0 8 2 1 3 6
4 5 10 11 9 7 2 6 0 3 1 8
4 6 8 7 11 10 1 9 0 3 2 5
5 7 9 6 10 11 0 8 1 2 3 4
Total 80 sets.
時間我沒細算,大約兩秒左右吧
※ 引述《bleed1979 (十三)》之銘言:
: 如果把12把位置依原po給的圖擺放 0 到 11,各條線上總和要一樣。
: 以下是我的程式跑出來的結果,由小到大字典排序,共80組。
: 也不曉得對不對,甚至根本是錯的,我不知道。
: total is 80
: 如果程式和答案是對的,那首位數字只會是 0 到 5,剛好一半。
: 關鍵在於產生所有排列的方法。
: 因為我用 dfs 產生所有排列,就可以設定首位數字大於 5 就 return。
: 原始未更改的我的程式跑了 1 分多鐘,還有很多努力的空間。
: 資料結構我使用 map 搭配 unsigned long long,用 bit 紀錄解。
: 花費記憶體似乎不到 5 MB,甚至更低。
: 參考程式碼:http://nopaste.csie.org/b88fb
: Bleed
: ※ 引述《tropical72 (藍影)》之銘言:
: : 抱歉昨天有點忙,也在想怎麼詳述我的問題,雖最後硬爆完成,
: : 但為避免日後遇到類似問題,還是整理一下向各位先進請教,請各位先進不吝解惑。
: : 我換了另一個相似之例子出來引出問題
: : 聲明,這問題我想問的是 技巧、演算法(目前是用窮舉法,效率太差了)、資料結構方面。
: : 所有各位版友有意見、經驗盡管提出供小弟做參考。
: : (1) 問題述敘
: : 六芒星之交點、端點共有 12 個點,在這 12 個點裡面放入 12 個相異數字,
: : 找出這 12 數字之排法,使六芒星線上之數字總合完全相等。
: : 說明圖如連結所示 http://ppt.cc/yUL3
: : 這裡標記是以最上方為 array[0],順時針方向
: : 依序填入 array[1], array[2]..., array[11]
: : 程式最終「並不是要求得所有合條件之解」,
: : 而是要求「所有獨立之解,即所有解不可經由 旋轉、順逆時 而得來」。
: : 文字說明有點難,以下 (2) 點說明何謂 旋轉、順逆時 而來之解
: : 雖表面上要試的解是 12! 組解,但分析之後實際要試的解是 12!/(6*2) 組而已。
: : 聲明,六芒星只是一個說明,實際上可能會有 12 芒星、18 芒星,會一直擴下去。
: : (2) 解集合說明
: : 目前之解為將 array[12] 做排列,判斷總合是否相等,這樣共有 12! 種解法。
: : 但這實屬 「環狀排列」 問題,實際上真正的排法根本不到 12! 這麼多,
: : (2.1) 順逆時針算同一組:
: : 以 0-1-2-3-4-5-6-7-8-9-10-11 為例,這是順時針,若以逆時針來看
: : 0-11-10-9-8-7-6-5-4-3-2-1 這和上面是同一組。
: : (2.2) 轉一個端點也算同一組:
: : 六芒星有六個端點,
: : 以 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 為例,轉一次變成
: : 10-11-0 -1 -2 -3 -4 -5 -6 -7 -8 -9 ,再轉一次變成
: : 8 -9 -10-11-0 -1 -2 -3 -4 -5 -6 -7 ,
: : 這樣等於是一個解有 6 種變化 (轉法)
: : 根據 (2.1) (2.2) ,可知實際上要去試的組數是 12!/(6*2)
: : (3) 目前去找「不重覆解」之解法
: : 先提出一個重要的概念,目前求出之「獨立解」組數並不多,以下為我目前的演算法
: : begin
: : 初始化獨立解 SOL_SET 為空
: : (a) 試目前之數列 s
: : (b) 目前之數列 s 為一組可行解
: : (b.1) 自 SOL_SET 裡判斷是否為獨立解 ? 是-> (b.2), 否->(c)
: : (b.2) 加入 SOL_SET 裡
: : (c) s 為最後一組數列 ? 是-> 結束, 否 -> (d)
: : (d) 取得下組數列, 回到步驟 (a)
: : end
: : 由於觀查得知 SOL_SET 之數目並不多,第二個問題便產生
: : 我想過的是
: : vector< int* >, vector< vector<int> >,
: : list< int* >, list< vector<int> >,
: : 最後挑用 vector< int* >,所以才會問是否會有 memory leak 之問題
: : 而暴力窮舉法時,目前使用的是 #include <algorithm> 裡面之 next_permutation
: : 速度上是否會差很多?
: : 這問題實在很長,謝謝各位版友耐心看完,
: : 有任何意見請不吝指導,或給 keyword 也行!!
: : 小弟感激不盡 !!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 175.180.110.223
→
03/12 16:56, , 1F
03/12 16:56, 1F
推
03/12 22:45, , 2F
03/12 22:45, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 4 之 5 篇):