如何在递归函数中查找错误

Question

我试图找到给定2D数组NxN的每个可能排列的每列的最大和中的最小值，其中每行中的值可以向左移动。例如，阵列

4 6 
3 7

将有4种可能的排列：

4 6   6 4   4 6    6 4
3 7   3 7   7 3    7 3

每个排列的最大和分别为13、11、11、13。因此，最大和中最小的是11。我已经编写了一个应该可以工作的递归函数，但由于某种原因，它只适用于小于6x6的数组……我是编程新手，最近刚刚学习了递归，如果能为我提供任何关于如何递归思考和调试代码的帮助或建议，我将不胜感激。。。

对于阵列4x4

7410 1371 2665 3195
4775 4130 6499 3414
300 2092 4009 7638
5351 210 7225 7207

答案是18349，我的代码给出了正确的答案。

但是，对于阵列6x6

5219 842 7793 2098 5109 2621
1372 3253 3804 5652 810 1620
4894 6792 1784 4335 4772 6656
3203 1070 4716 5335 1157 6855
5529 2767 2205 408 7516 7454
375 7036 2597 5288 937 2893

答案应该是23733，但我得到了24176。这怎么可能？

这是我的代码：

#include <iostream>
using namespace std;
#define MAX_N 1000
int n, matrix[MAX_N][MAX_N], shift[MAX_N] = {0}, minSum = 100000000;
void possibTree(int position){

//Base case
if(position == n){
for (int i = 0; i < n; i++) {
// Temporary array to store the values in the row that just shifted towards the left
int temp[MAX_N] = {0};
for (int j = 0; j < n; j++) {
if(j - shift[i] < 0)
temp[n+(j-shift[i])] = matrix[i][j];
else
temp[j-shift[i]] = matrix[i][j];
}
for (int k = 0; k < n; k++)
matrix[i][k] = temp[k];
}

int max = 0;
for (int i = 0; i < n; i++) {
int temp = 0;
for (int j = 0; j < n; j++) {
temp += matrix[j][i];
}
if(temp > max)
max = temp;
}
if(minSum > max)
minSum = max;
return;
}

for (int i = 0; i < n; i++) {
shift[position] = i;
possibTree(position+1);
}
return;
}
int main() {
while(cin >> n){
memset(matrix, 0, sizeof(matrix));
memset(shift, 0, sizeof(shift));
if(n == -1) // The user enters "-1" to end the loop and terminate the program.
return 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
possibTree(0);
cout << minSum << endl;
minSum = 100000000;
}
return 0;
}

Answer 1

好吧，我相信我理解我的错误，我必须在每个基本情况结束时将矩阵重置为其原始状态，当矩阵很小时，代码仍然能够找到所有可能的最大和，但当矩阵变大时，一些可能性就没有产生。这是我的代码：

#include <iostream>
using namespace std;
#define MAX_N 1000
int n, matrix[MAX_N][MAX_N], OrigMatrix[MAX_N][MAX_N], shift[MAX_N] = {0}, minSum = 100000000;
void possibTree(int position){

//Base case
if(position == n){
for (int i = 0; i < n; i++) {
// Temporary array to store the values in the row that just shifted towards the left
int temp[MAX_N] = {0};
for (int j = 0; j < n; j++) {
if(j - shift[i] < 0)
temp[n+(j-shift[i])] = matrix[i][j];
else
temp[j-shift[i]] = matrix[i][j];
}
for (int k = 0; k < n; k++)
matrix[i][k] = temp[k];
}

int max = 0;
for (int i = 0; i < n; i++) {
int temp = 0;
for (int j = 0; j < n; j++) {
temp += matrix[j][i];
}
if(temp > max)
max = temp;
}
if(minSum > max)
minSum = max;
//EDITS
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = OrigMatrix[i][j];
}
}
return;
}

for (int i = 0; i < n; i++) {
shift[position] = i;
possibTree(position+1);
}

return;
}
int main() {
while(cin >> n){
memset(matrix, 0, sizeof(matrix));
memset(shift, 0, sizeof(shift));
if(n == -1) // The user enters "-1" to end the loop and terminate the program.
return 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
//EDITS
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
OrigMatrix[i][j] = matrix[i][j];
}
}
possibTree(0);

cout << minSum << endl;
minSum = 100000000;
}
return 0;
}