我必须制作一个程序,接受二维数组的行/列数量以及数组本身作为输入。
它应该通过仅向右、向上或向下移动来计算它可以在矿井中收集的“钻石”的最大数量。
代码没有给出任何编译错误,但是当我运行它时,它给出了一个段错误。
可能这与我在 main
中使用的 malloc
有关,但我不知道如何修复它。
代码是:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define max(a,b) (((a)>(b))?(a):(b))
int maxdiam(int *mine, int m, int n) {
// table for storing intermediates
int table[m][n];
memset(table, 0, sizeof(table));
for(int c=n-1; c>=0; c--) {
for (int r=0; r<m; r++) {
// right
int right = (c == n-1)? 0: table[r][c+1];
// right up
int rightup = (r == 0 || c == n-1)? 0:table[r-1][c+1];
// right down
int rightdown = (r == m-1 || c == n-1)? 0:
table[r+1][c+1];
// Max collected
table[r][c] = mine[r] + max(right, max(rightup, rightdown));
}
}
// max diam == max first column all rows
int res = table[0][0];
for (int i=1; i<m; i++)
res = max(res, table[i][0]);
return res;
}
// Driver Code
int main(int argc, char* v[]) {
int n;
scanf("%d", &n);
int m = n;
int **mine = malloc(sizeof(int *) * n);
for(int i = 0; i < n; i++) {
mine[i] = (int *)malloc(n * sizeof(int));
}
for(int i=0; i < n; i++) {
for(int j=0; j < n; j++) {
scanf("%d", &mine[i][j]);
}
}
printf("%d\n", maxdiam(&mine[m][n], m, n));
return 0;
}
预期的输入和输出:
input:
3
1 3 3
2 1 4
0 6 4
output:
12
input:
4
1 3 1 5
2 2 4 1
5 0 2 3
0 6 1 2
output:
16
input:
4
10 33 13 15
22 21 4 1
5 0 2 3
0 6 1 2
output:
83
我不是要找人为我的问题提供正确的代码,但我希望有人知道我为什么会收到上述错误以及如何解决这个问题。
最佳答案
您的代码中存在许多问题,其中一些已在评论中提及。下面,我发布了一个工作版本(我用你的示例数据测试了它),在我进行更改的代码中添加了注释(所有这些都有三重斜线,///
标记它们)。
撇开这几个问题不谈,您的代码逻辑(遍历数组寻找最大值的方式)没有问题 - 这就是我将此答案作为完整解决方案发布的原因。
请随时询问我所做的任何更改的更多信息和/或说明。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
///#define max(a,b) (((a)>(b))?(a):(b)) // Should be already defined in stdlib.h
int maxdiam(int** mine, int m, int n) { /// NOTE: "mine" is an int** - NOT an int*
// table for storing intermediates
/// int table[m][n]; // Variable length arrays are NOT standard C, so use the following ...
int** table = malloc(sizeof(int*) * m); // This allocates a 'm' size array of pointers ...
for (int i = 0; i < m; ++i) {
table[i] = malloc(sizeof(int) * n); // ... each of which points to an 'n' size array of intregers
memset(table[i], 0, sizeof(int) * n); // And here, we set the values to all zero.
}
/// memset(table, 0, sizeof(table)); // This cannot be used with the 'malloc' system!
for (int c = n - 1; c >= 0; c--) {
for (int r = 0; r < m; r++) {
// right
int right = (c == n - 1) ? 0 : table[r][c + 1];
// right up
int rightup = (r == 0 || c == n - 1) ? 0 : table[r - 1][c + 1];
// right down
int rightdown = (r == m - 1 || c == n - 1) ? 0 : table[r + 1][c + 1];
// Max collected
/// table[r][c] = mine[r] + max(right, max(rightup, rightdown)); // You forgot the column index!
table[r][c] = mine[r][c] + max(right, max(rightup, rightdown));
}
}
// max diam == max first column all rows
int res = table[0][0];
for (int i = 1; i < m; i++) res = max(res, table[i][0]);
/// Here, we free the 'temporary' array(s) we created ...
for (int i = 0; i < m; ++i) free(table[i]);
free(table);
return res;
}
// Driver Code
int main(int argc, char* v[]) {
int n;
scanf("%d", &n);
int m = n;
int** mine = malloc(sizeof(int*) * n);
for (int i = 0; i < n; i++) {
mine[i] = malloc(n * sizeof(int)); // Note: you shouldn't "cast" the return value of malloc!
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &mine[i][j]);
}
}
/// printf("%d\n", maxdiam(&mine[m][n], m, n)); // This will pass the address of the first element of the last row!
printf("%d\n", maxdiam(mine, m, n)); // Use this instead - to pass the address of the 'row' array!
return 0;
}
注意:在我标出“可变长度数组”的那一点上 - 如果您的系统(可能是 gcc
)允许这样做,那么您可以继续使用它,从而采取使用 malloc
和 free
退出我提供的系统。但是,我认为这不是学习 C
编程的最佳方式。
关于c - 如何找到矿山中最大数量的钻石?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58483079/