用全局值回溯遞歸差異？

以this爲例：用全局值回溯遞歸差異？

bool SolveSudoku(int grid[N][N]) 
{ 
    int row, col; 

    // If there is no unassigned location, we are done 
    if (!FindUnassignedLocation(grid, row, col)) 
     return true; // success! 

    // consider digits 1 to 9 
    for (int num = 1; num <= 9; num++) 
    { 
     // if looks promising 
     if (isSafe(grid, row, col, num)) 
     { 
      // make tentative assignment 
      grid[row][col] = num; 

      // return, if success, yay! 
      if (SolveSudoku(grid)) 
       return true; 

      // failure, unmake & try again 
      grid[row][col] = UNASSIGNED; 
     } 
    } 
    return false; // this triggers backtracking 
}

網格始終作爲參數遞歸調用傳遞，所以在每次迭代中電網的新副本。

我似乎無法概念化使用相同的邏輯與全局網格工作是否有任何區別。

失敗後，該變量設置爲「取消&再試一次」 - 這不應該在回溯中處理任何「撤銷」嗎？

如果網格是一個全球性的，爲什麼發送和額外的複製每次這個遞歸回溯會有什麼不同？

來源

2014-02-27 T.T.T.

網格總是作爲參數傳遞給遞歸調用，因此在每次迭代中都有一個新的網格副本。

不，在每次迭代中都有對網格的引用（指針）的新副本。實際工作一遍又一遍地在同一個網格上完成。

看一看this code snap例如：

#include <stdlib.h> 
#include <stdio.h> 
void foo(int arr[], int n) { 
    arr[0] = 1; 
} 
int main() { 
    int myArray[5] = {0,0,0,0,0}; 
    foo(myArray,5); 
    printf("%d",myArray[0]); 
    return 0; 
}

注意，沒有副本製作，並在foo()更改arr反映到myArray。我相信它會自動回答你的其餘問題（這與使用全局變量基本相同，但全局變量通常是不好的做法，發送對數組的引用是一種更好的做法）。

來源

2014-02-27 00:26:08 amit

好吧，我明白了，這是我前一陣子記得的整個「數組都是指針，好處」的東西。 –

在C/C++數組中，作爲指向數組開頭的指針傳遞。看看這個例子：

#include <iostream> 

static const int N = 10; 

void test(int a[N][N]) 
{ 
    std::cout << a << std::endl; 
} 

int main(int argc, char **argv) 
{ 
    int a[N][N]; 
    std::cout << a << std::endl; 
    test(a); 
    return 0; 
}

如果你運行它，你會得到印在標準輸出相同的值：

$ ./test  
0x7fff0c669930 
0x7fff0c669930

這是一個指向數組的開頭的值，因此main（）和test（）中使用相同的指針。

這意味着通過讓網格成爲全局變量，您不會獲得任何性能增益。相反，你會通過引入一個全球性的模塊來減少模塊化。

來源

2014-02-27 00:36:56 virtus

謝謝，對於有11個聲望的用戶來說不壞吧！） –

現在名字！ –

謝謝，我剛剛在StackOverflow上打開了一個帳戶:) – virtus

用全局值回溯遞歸差異？

回答

相關問題