Re: [問題] vector<int *> 會有 memory leak 問題嗎?

看板C_and_CPP作者 (火神)時間14年前 (2011/03/12 08:43), 編輯推噓1(101)
留言2則, 2人參與, 最新討論串4/5 (看更多)
好久沒有寫這類型的程式了 基本上這種題目不外乎就是在產生數列時盡早砍掉可以砍的部分 因此使用 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
P.S. 以上的程式預期 slot 內為 sorted data
03/12 16:56, 1F

03/12 22:45, , 2F
E 大好強!! 大推 !!
03/12 22:45, 2F
文章代碼(AID): #1DUp8eR8 (C_and_CPP)
討論串 (同標題文章)
文章代碼(AID): #1DUp8eR8 (C_and_CPP)