Re: [問題] vector<int *> 會有 memory leak 問題嗎？
如果把12把位置依原po給的圖擺放 0 到 11，各條線上總和要一樣。
以下是我的程式跑出來的結果，由小到大字典排序，共80組。
也不曉得對不對，甚至根本是錯的，我不知道。
total is 80
0 1 4 10 11 3 5 2 6 7 8 9
0 1 4 11 10 2 5 3 7 6 8 9
0 1 6 11 10 3 2 4 5 9 7 8
0 1 7 10 11 2 3 4 5 9 6 8
0 2 4 9 11 1 8 3 7 5 6 10
0 2 7 9 11 1 5 6 4 8 3 10
0 2 7 11 9 3 1 6 4 10 5 8
0 3 1 9 10 4 8 2 6 5 7 11
0 3 2 11 8 4 5 1 9 6 10 7
0 3 6 10 9 1 5 8 4 7 2 11
0 4 2 11 7 1 8 5 9 3 6 10
0 4 3 7 11 2 10 1 8 5 6 9
0 4 3 10 8 2 7 1 11 5 9 6
0 4 3 11 7 6 2 1 8 9 10 5
0 4 6 8 10 3 5 7 2 9 1 11
0 4 6 10 8 5 1 7 2 11 3 9
0 4 8 7 11 2 5 6 3 10 1 9
0 4 9 10 8 2 1 7 5 11 3 6
0 5 1 11 6 2 8 4 10 3 7 9
0 5 2 10 7 1 9 6 8 3 4 11
0 5 4 9 8 6 3 7 1 10 2 11
0 5 4 9 8 7 2 6 1 11 3 10
0 5 7 11 6 3 1 9 4 10 2 8
0 6 1 7 9 3 11 2 8 4 5 10
0 6 1 9 7 2 10 5 8 3 4 11
0 6 2 5 11 7 8 1 3 9 4 10
0 6 2 7 9 8 5 4 1 10 3 11
0 6 2 11 5 1 8 7 9 3 4 10
0 6 3 7 9 1 11 2 10 4 5 8
0 7 1 10 5 2 9 4 11 3 6 8
0 7 1 11 4 2 8 6 10 3 5 9
0 7 2 9 6 1 10 4 11 3 5 8
0 7 3 5 10 6 8 4 2 9 1 11
0 7 3 6 9 8 5 4 1 11 2 10
0 7 6 11 4 3 2 10 5 9 1 8
0 8 1 5 9 6 10 3 4 7 2 11
0 8 2 4 10 5 11 1 6 7 3 9
0 8 2 10 4 3 7 9 6 5 1 11
0 8 4 11 3 2 5 10 7 6 1 9
0 9 1 7 6 3 11 5 8 4 2 10
1 0 5 10 11 3 4 2 6 7 9 8
1 0 5 11 10 2 4 3 7 6 9 8
1 0 6 11 10 3 2 5 4 8 7 9
1 0 7 10 11 2 3 5 4 8 6 9
1 2 3 10 9 5 4 0 8 7 11 6
1 2 4 10 9 0 8 6 7 3 5 11
1 2 7 11 8 0 4 9 5 6 3 10
1 2 10 8 11 0 4 6 5 9 3 7
1 3 5 7 11 0 10 2 9 4 6 8
1 4 3 11 6 0 8 7 9 2 5 10
1 4 11 8 9 0 3 7 6 10 2 5
1 5 2 6 10 3 11 0 9 4 7 8
1 5 3 7 9 2 10 0 11 4 8 6
1 5 3 9 7 0 10 4 11 2 6 8
1 5 4 10 6 0 8 9 7 3 2 11
1 6 3 8 7 0 11 5 10 2 4 9
1 7 3 9 5 0 10 6 11 2 4 8
1 7 5 11 3 0 6 10 9 4 2 8
2 0 4 9 11 3 6 1 7 5 10 8
2 0 4 11 9 1 6 5 7 3 8 10
2 0 7 11 9 1 3 8 4 6 5 10
2 1 3 9 10 4 6 0 8 5 11 7
2 1 5 8 11 0 9 4 7 3 6 10
2 1 5 11 8 0 6 4 10 3 9 7
2 1 7 9 10 0 6 8 4 5 3 11
2 3 6 7 10 0 9 1 11 4 8 5
2 3 6 7 10 1 8 0 11 5 9 4
2 4 3 10 6 0 9 5 11 1 7 8
2 4 3 11 5 0 8 7 10 1 6 9
2 5 3 8 7 0 11 6 9 1 4 10
2 6 3 10 4 0 9 7 11 1 5 8
3 0 4 9 10 1 8 5 6 2 7 11
3 1 5 7 11 2 8 0 9 4 10 6
3 2 4 8 9 0 10 6 7 1 5 11
3 2 7 6 11 0 9 1 10 4 8 5
3 2 7 6 11 1 8 0 10 5 9 4
4 0 5 8 10 2 7 1 9 3 11 6
4 1 6 9 8 0 7 3 11 2 10 5
4 2 5 6 10 0 11 3 9 1 7 8
5 0 7 8 9 1 6 2 10 3 11 4
如果程式和答案是對的，那首位數字只會是 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)
: ※ 第一個問題 : 請問有沒有辦法只窮舉這 12!/(6*2) 組解，而不是完全窮舉 12! 之解
: (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 之數目並不多，第二個問題便產生
: ※ 請問 SOL_SET 該用何種資料結構？
: 我想過的是
: vector< int* >, vector< vector<int> >,
: list< int* >, list< vector<int> >,
: 最後挑用 vector< int* >，所以才會問是否會有 memory leak 之問題
: 而暴力窮舉法時，目前使用的是 #include <algorithm> 裡面之 next_permutation
: 速度上是否會差很多？
: 這問題實在很長，謝謝各位版友耐心看完，
: 有任何意見請不吝指導，或給 keyword 也行!!
: 小弟感激不盡 !!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.114.2
推
03/11 03:05, , 1F
03/11 03:05, 1F
→
03/11 03:05, , 2F
03/11 03:05, 2F
推
03/11 03:17, , 3F
03/11 03:17, 3F
→
03/11 06:58, , 4F
03/11 06:58, 4F
→
03/11 06:59, , 5F
03/11 06:59, 5F
→
03/11 13:05, , 6F
03/11 13:05, 6F
討論串 (同標題文章)