數組中給定雙方的唯一三角形的數量

我想通過蠻力（O（N^3）或遞歸協調算法）找到「唯一」三角形的最大數目（每個數組元素只能使用一次））。應該採取什麼方法？數組中給定雙方的唯一三角形的數量

2013-07-05 mehmetin

就目前而言，我不認爲這個問題中有足夠的信息可供任何人回答。你能否進一步解釋，告訴我們你已經嘗試了什麼，以及你遇到的任何具體問題。你想用什麼語言來做這件事？ –

我正在用C++做。我應該補充說三角形應該是有效的。 – mehmetin

陣列中給出了邊長。需要構成有效三角形的三元組的最大數量。（a <（b + c）&& b <（a + c）&& c <（a + b））。每邊的長度只能使用一次，即三角形的邊應該是不相交的。如果有重複的邊長，相同的邊長可以多次使用。 – mehmetin

創建一個映射（hashmap應該沒問題），並將終點映射到side。所以每一方都會有兩個條目 - 每個端點一個。現在，您可以高效地查找從任何給定終點開始的所有方面。

一些基本的僞代碼：

// map[X] is all unused sides with X as end-point 
// markAsUsed should also remove the side from the map 
// markAsUnused should also add the side to the map 

// initial function call for any unused side 
backTrackFunction(anyUnusedSide) 

backTrackFunction(side AB) 
    if map.isEmpty 
    Found a solution. 
    markAsUsed(AB) 
    for each side AC in map[A] 
    if map[C].contains(CB) 
     // AB, CB and AC form a triangle 
     markAsUsed(CB) 
     markAsUsed(AC) 
     backTrackFunction(anyUnusedSide) 

     // Backtrack 
     markAsUnused(CB) 
     markAsUnused(AC)

上面可能有一些問題，但它只是打算成爲一個起點。

來源

2013-07-05 12:34:12 Dukeling

首先假定所有邊都具有正整數的長度。（對於實數，間隔半開放半封閉的並使其梅西耶來思考。）

基本上，如果我們發現得到與長邊的數量範圍[a,b]的一個有效途徑每0<=a<=b，我們可以處理它：

edgeList = sort edgeList by length ascending order 
    foreach (edge1 in edgeList) 
     foreach (edge2 in edgeList where [edge2 >= edge1]) 
      answer = answer + count_edge_number (edge2 , edge1+edge2-1); 
    return answer;

因此，我們只需要這樣的方式。要做到這一點，您只需按升序對邊進行排序，使用二進制搜索索引（訂閱）的間隔的下限和上限。（也就是說，對於任何[a,b]，請使用二分查找找到帶有element[i]<a的最大i和帶element[j]<=b的最小j）。這適用於O(logN)。

因此你的任務可以在O(N^2LogN)中實現，比稻草人O(N^3)好得多。

來源

2013-07-05 13:01:39 phoeagon

數組中給定雙方的唯一三角形的數量

回答

相關問題