尋找所有可能的子集的使用遞歸

-2

struct point 
{ 
    int x; 
    int y; 
};

和分表：

point tab[MAX];

程序應返回任何可能的對的重心之間的最小距離來自tab的子集。子集可以是任何大小（當然> = 1和< MAX）。我有義務用遞歸編寫這個程序。因此我必須返回int。我設置全局變量min（因爲同時做recurssion我要比較這個最小的一些值）

int min = 0;

我的功能應該是肯定的，以我添加元素的個數，Y的總和座標和X座標的總和。

int return_min_distance(int sY, int sX, int number, bool iftaken[])

我會很樂意爲您提供進一步的幫助。我想過另一張布爾表，我將其作爲參數傳遞，以確定我是否從表中獲得價值。我的問題仍然是如何實現這一點，我不知道如何開始。

來源

2014-01-16 Marcin Majewski

這是一個功課問題嗎？ –

你有沒有爲'return_min_distance（）'嘗試過的代碼？ – zero298

@Randall廚師我認爲它可以歸類爲家庭作業問題。這是測試多年前出現的問題之一，我準備通過這個測試，遞歸是我最薄弱的一點。 –

我認爲你需要一個函數，可以迭代通過表的所有子集，從任何內容或現有的迭代器開始。然後，該代碼變得容易：

int min_distance = MAXINT; 
SubsetIterator si1(0, tab); 
while (si1.hasNext()) 
{ 
    SubsetIterator si2(&si1, tab); 

    while (si2.hasNext()) 
    { 
     int d = subsetDistance(tab, si1.subset(), si2.subset()); 

     if (d < min_distance) 
     { 
      min_distance = d; 
     } 
    } 
}

的SubsetIterators可以是簡單的鹼-2的計數到MAX，其中1位指示在所述子集中的成員號碼。是的，這是一個O（N^2）算法，但我認爲它應該是。

訣竅是合併遞歸。對不起，我只是看不出它在這裏有什麼幫助。如果我能想到使用它的方法，我會編輯我的答案。

更新：我想到了更多，雖然仍然看不到遞歸的用法，但我找到了一種方法來使子集處理更容易。 SubsetIterators可以存儲x和y值的預先計算的總和，以便於進行距離計算，而不是貫穿整個表格。然後，在每次迭代中，減去離開子集的值並添加正在加入的值。一個簡單的位和操作可以揭示這些。爲了更有效率，您可以使用gray coding而不是二進制補碼來存儲成員資格位圖。這將保證在每次迭代中恰好有一個值進入和/或離開子集。最小的工作。

來源

2014-01-17 00:25:50

尋找所有可能的子集的使用遞歸

回答

相關問題