總和矩陣的周長而不多次添加角落

Question

我試圖用遞歸來總和n個矩陣的周長。 （沒有多次加角）

我寫的是一個無限循環，並不排除角落。如何停止無限循環並排除角落？

int 
sumPerimeter(int** matrix, int i, int j, int height, int width) 
{ 
    if (i == 0 && j == 0) 
     return matrix[i][j] + sumPerimeter(matrix, i + 1, j, height, width); 

    if (i == height && j == 0) 
     return matrix[i][j] + sumPerimeter(matrix, i, j + 1, height, width); 

    if (i==height&& j == width) 
     return matrix[i][j] + sumPerimeter(matrix, i - 1, j, height, width); 

    if (i == 0 && j == width) 
     return matrix[i][j] + sumPerimeter(matrix, i, j - 1, height, width); 
} 

我決定把這個分成幾個階段，以使它更容易，下面的代碼是我目前的嘗試。當我使用視覺工作室瀏覽它時，它會工作，但它總是返回矩陣中的第一個數字。

int 
    sumRight(int** matrix, int i, int j, int height, int width,int count) 
    { 


    if (0 > width) 
     return 0; 

    if (j > width - 1) 
     return count; 

     int sum = matrix[i][j]; 
     count = sum + count; 

    sumRight(matrix, i, j + 1, height, width,count); 



    return count; 

} 

我想通了它爲什麼沒有返回正確的值。但我不知道如何讓它不會多次計算角落。任何意見，將不勝感激。

Answer 1

如果必須使用遞歸爲這個（這可能是一個糟糕的主意，因爲你獲得非常小，但它可能是好的教育目的），你可以選擇一個簡單的方法。

將基本情況設爲零高度的矩陣，反覆出現的情況是將第一行的總和與矩陣的其餘部分的總和相加。換句話說，類似下面的僞代碼：

def sumOfMatrix (matrix m, int row, int height, int width): 
    # No rows left, return zero. 

    if row == height: 
     return 0 

    # Get sum of first row. 

    sum = 0 
    for col in 0..width-1 inclusive: 
     sum = sum + m[row][col] 

    # Return that plus sum of rest of matrix. 

    return sum + sumOfMatrix (m, row+1, height, width) 

---

如果你真的想很巧妙，因爲這個詞的一些奇怪的定義，「聰明」 :-)，你可以做兩完全不同類型的遞歸，一個用於行，另一個用於一個矩陣：

def sumOfRow (matrix m, int row, int col, int width): 
    # No columns left, return zero. 

    if col == width: 
     return 0 

    # Get value plus sum of rest of row. 

    return m[row][col] + sumOfRow (m, row, col+1, width) 

def sumOfMatrix (matrix m, int row, int height, int width): 
    # No rows left, return zero. 

    if row == height: 
     return 0 

    # Get sum of this row plus sum of all other rows. 

    return sumOfRow (m, row, 0, width) + sumOf (m, row+1, height, width) 

---

如前所述，這是親bably遞歸錯誤的使用情況，因爲你可以簡單地做一個緊湊的迭代求解這樣的：

def sumOfMatrix (matrix m, int height, int width): 
    sum = 0 
    for row = 0..height-1 inclusive: 
     for col = 0..width-1 inclusive: 
      sum = sum + m[row][col] 
    return sum 

但是，如果你需要一個遞歸解決方案（因爲你是自學遞歸，或者你的教育是不能考慮更好的現實世界問題），上面的遞歸代碼應該足以幫助你。

Answer 2

遍歷矩形外圍的遞歸解決方案。

平面點的結構和一些輔助功能：

struct pt { int cx; int cy; }; 
pt init(int x0, int y0) { pt p0; p0.cx = x0; p0.cy = y0; return p0; } 
void prpt(pt p0) { printf("(%d;%d)\n", p0.cx, p0.cy); } 

int eq(pt p0, pt p1) 
{ 
    int rv = 0; 
    if((p0.cx == p1.cx) && (p0.cy == p1.cy)) { rv = 1; } 
    return rv; 
} 

int perim(pt curr, pt size) 
{ 
    int rv = 0; 
    if((0 <= curr.cx) && (curr.cx < size.cx) 
    && (0 <= curr.cy) && (curr.cy < size.cy)) 
    { 
     if(((0 == curr.cx) || ((1 + curr.cx) == size.cx)) 
      || (0 == curr.cy) || ((1 + curr.cy) == size.cy)) { rv = 1; } 
    } 
    return rv; 
} 

從明年外圍點可在4個方向前進，但其中只有2將是對周邊了。通過回顧以前的立場阻止後退。始發點也必須存儲以便結束遍歷。遞歸：

void fun(pt size, pt orig, pt prev, pt curr) 
{ 
    pt next; 
    if(perim(curr, size) && (!eq(curr, orig) || eq(curr, prev))) 
    { 
     prpt(curr); 

     next = curr; next.cy += 1; // N 
     if(!eq(next, prev)) { fun(size, orig, curr, next); } 

     next = curr; next.cx += 1; // E 
     if(!eq(next, prev)) { fun(size, orig, curr, next); } 

     next = curr; next.cy -= 1; // S 
     if(!eq(next, prev)) { fun(size, orig, curr, next); } 

     next = curr; next.cx -= 1; // W 
     if(!eq(next, prev)) { fun(size, orig, curr, next); } 
    } 
} 

原點，當前點和先前點在第一次調用時是相同的。橫穿7X5矩形的兩個方向上從在該示例中所選擇的點：

pt size = init(7, 5); 
pt orig = init(0, 0); 
pt prev = orig; 
pt curr = orig; 
fun(size, orig, prev, curr); 

在此基礎上一總和計算遍歷是由你。