2 qq 34341918 qq_34341918 于 2016.03.19 10:52 提问

C语言相邻数求最大和的问题求解答

#include
int** matrix(int row) {
int** matr;
matr = malloc(row*sizeof(int*));
for(int i = 0; i < row; i++) {
matr[i] = malloc(row*sizeof(int));
}
return matr;

}

void get_input(int** arrays, int row) {
for(int i = 0; i < row; i++) {
for(int j = 0; j < row; j++) {
scanf("%d", &arrays[i][j]);
}
}

}

int compareFunction(const void *a,const void *b) {

return *(int *)b - *(int *)a;

}

int compareBigger(int *diagline, int maxium) {
if(diagline[0] >= maxium) {
maxium = diagline[0];
}
return maxium;
}

void rowdirection(int *straightline, int num, int rows, int **mat) {
int i = 0;
for(int row = 0; row < rows; row++) {
for(int column = 0; column < rows - num + 1; column++ ) {
for(int j = 0; j < num; j++) {
straightline[i] += mat[row][column + j];
}i++;
}
}
}

void coldirection(int *straightline, int num, int rows, int **mat) {
int i = 0;
for(int column = 0; column < rows; column++) {
for(int row = 0; row < rows - num + 1; row++ ) {
for(int j = 0; j < num; j++) {
straightline[i] += mat[row + j][column];
}i++;
}
}
}

void diagdirection(int *diagline, int num, int rows, int **mat) {

int i = 0;
for(int row = 0; row < rows - num + 1; row++ ) {
    for(int col = 0; col < rows - num + 1; col++ ) {
        for(int j = 0; j < num; j++) {
            diagline[i] += mat[row + j][col + j];
        }i++;
        //printf("%d\n", diagline[i]);
    }
}

}

void antidiagdirection(int *diagline, int num, int rows, int **mat) {

int i = 0;
for(int row = 0; row < rows - num + 1; row++ ) {
    for(int col = num - 1; col < rows; col++ ) {
        for(int j = 0; j < num; j++) {
            diagline[i] += mat[row + j][col - j];
        }i++;
        //printf("%d\n", diagline[i]);
    }
}

}

void main() {

int maxium = 0;

int row, num;
scanf("%d %d\n", &row, &num);
int straightnum = row*(row - num + 1);
int diagnum = (row - num + 1)*(row - num + 1);
int **mat = matrix(row);

get_input(mat, row);

int *straightline1 = (int *)malloc(straightnum*sizeof(int));
rowdirection(straightline1, num, row, mat);
qsort(straightline1, straightnum, sizeof(int), compareFunction);
maxium = compareBigger(straightline1, maxium);
//printf("%d\n", maxium);

int *straightline2 = (int *)malloc(straightnum*sizeof(int));
coldirection(straightline2, num, row, mat);
qsort(straightline2, straightnum, sizeof(int), compareFunction);
maxium = compareBigger(straightline2, maxium);
//printf("%d\n", maxium);

int *diagline1 = (int *)malloc(diagnum*sizeof(int));

    diagdirection(diagline1, num, row, mat);
    qsort(diagline1, diagnum , sizeof(int), compareFunction);
    maxium = compareBigger(diagline1, maxium);

//printf("%d\n", maxium); 

int *diagline2 = (int *)malloc(diagnum*sizeof(int));

    antidiagdirection(diagline2, num, row, mat);
    qsort(diagline2, diagnum , sizeof(int), compareFunction);
    maxium = compareBigger(diagline2, maxium);

//printf("%d\n", maxium);

    printf("%d", maxium);

free(straightline1);
free(straightline2);
free(diagline1);
free(diagline2);
free(mat);

}


学校的作业,input是第一行 两个int, 一个是 下面的表的行列数(方阵),一个是用来规定有多少个相邻数来求最大和。
我用的是四种function把所有情况都写进四个指针,初始化maxium=0,然后指针内部降序排序,四次依次询问是否大于maxium,最后输出maxium。
问题是有些未知的test(test文件老师不会公开给我们)是wrong answer,菜鸟如我找不出那个情况。
题目有行数不超过100,求和个数不超过行数,每个数字不大于1000的限制,
然后test的工具可以忽略free的问题(我还没来得及写,但是free不会造成wrong answer)
求大神指点
代码楼下附加

1个回答

qq_34341918
qq_34341918   2016.03.19 10:53

#include
int** matrix(int row) {
int** matr;
matr = malloc(row*sizeof(int*));
for(int i = 0; i < row; i++) {
matr[i] = malloc(row*sizeof(int));
}
return matr;

}

void get_input(int** arrays, int row) {
for(int i = 0; i < row; i++) {
for(int j = 0; j < row; j++) {
scanf("%d", &arrays[i][j]);
}
}

}

int compareFunction(const void *a,const void *b) {

return *(int *)b - *(int *)a;

}

int compareBigger(int *diagline, int maxium) {
if(diagline[0] >= maxium) {
maxium = diagline[0];
}
return maxium;
}

void rowdirection(int *straightline, int num, int rows, int **mat) {
int i = 0;
for(int row = 0; row < rows; row++) {
for(int column = 0; column < rows - num + 1; column++ ) {
for(int j = 0; j < num; j++) {
straightline[i] += mat[row][column + j];
}i++;
}
}
}

void coldirection(int *straightline, int num, int rows, int **mat) {
int i = 0;
for(int column = 0; column < rows; column++) {
for(int row = 0; row < rows - num + 1; row++ ) {
for(int j = 0; j < num; j++) {
straightline[i] += mat[row + j][column];
}i++;
}
}
}

void diagdirection(int *diagline, int num, int rows, int **mat) {

int i = 0;
for(int row = 0; row < rows - num + 1; row++ ) {
    for(int col = 0; col < rows - num + 1; col++ ) {
        for(int j = 0; j < num; j++) {
            diagline[i] += mat[row + j][col + j];
        }i++;
        //printf("%d\n", diagline[i]);
    }
}

}

void antidiagdirection(int *diagline, int num, int rows, int **mat) {

int i = 0;
for(int row = 0; row < rows - num + 1; row++ ) {
    for(int col = num - 1; col < rows; col++ ) {
        for(int j = 0; j < num; j++) {
            diagline[i] += mat[row + j][col - j];
        }i++;
        //printf("%d\n", diagline[i]);
    }
}

}

void main() {

int maxium = 0;

int row, num;
scanf("%d %d\n", &row, &num);
int straightnum = row*(row - num + 1);
int diagnum = (row - num + 1)*(row - num + 1);
int **mat = matrix(row);

get_input(mat, row);

int *straightline1 = (int *)malloc(straightnum*sizeof(int));
rowdirection(straightline1, num, row, mat);
qsort(straightline1, straightnum, sizeof(int), compareFunction);
maxium = compareBigger(straightline1, maxium);
//printf("%d\n", maxium);

int *straightline2 = (int *)malloc(straightnum*sizeof(int));
coldirection(straightline2, num, row, mat);
qsort(straightline2, straightnum, sizeof(int), compareFunction);
maxium = compareBigger(straightline2, maxium);
//printf("%d\n", maxium);

int *diagline1 = (int *)malloc(diagnum*sizeof(int));

    diagdirection(diagline1, num, row, mat);
    qsort(diagline1, diagnum , sizeof(int), compareFunction);
    maxium = compareBigger(diagline1, maxium);

//printf("%d\n", maxium); 

int *diagline2 = (int *)malloc(diagnum*sizeof(int));

    antidiagdirection(diagline2, num, row, mat);
    qsort(diagline2, diagnum , sizeof(int), compareFunction);
    maxium = compareBigger(diagline2, maxium);

//printf("%d\n", maxium);

    printf("%d", maxium);

free(straightline1);
free(straightline2);
free(diagline1);
free(diagline2);
free(mat);

}


Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
求不相邻的最大子数组和
问题1:给出一个数组,求出其中一个子集,使得子集中每个元素在原数组中两两都不相邻并使子集的和最大。 解法:对任意一个元素ai ,有两种可能: 选ai ,单选了ai 就不能选ai-1 ;不选ai 那么ai-1 可以选也可以不选,主要根据ai-2的情况,因此动态规划是这样设计的。  ds[i] 表示选i,a0....ai的最大子数组和; ns[i]表示不选择 i,a0 ....ai 的最大子数组
数组中不相邻元素的最大和
数组中不相邻元素的最大和 Maximum sum such that no two elements are adjacent
[LeetCode] House Robber 求数组中元素两两不相邻的子序列最大和
声明:原题目转载自LeetCode,解答部分为原创 Problem :     You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping
LeetCode (20) house robber (数组不相邻元素最大值)
题目描述You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent ho
【面试】求数组子序列的最大和
一、问题描述 输入一个整形数组,数组里可以有正数或负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。        例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。 第一次遇到这道题是参加x迅的笔试。题目中给出了两种解法,让
C语言 一次遍历求出第一大和第二大
#include int main() { int Arry[11]={4,7,2,20,3,9,10,1,15,6,21}; int First_Max,Second_Max; //默认第一大就是第一大,第二大就是第二大,后面有比第一大的就认为是最大, //比第二大而比第一小的就是第二大 First_Max=Arry[0]; Second_Max=Arry[1]; for (int
求子数组最大和 (非连续)(动态规划)
转自出处:http://likecer.com/dp-biggest-sub/
笔试题 百度2015大数据云计算研发笔试(非相邻数最大和)
给定一个整数的数组,相邻的数不能同时选,求从该数组选取若干整数,使得他们的和最大,要求只能使用o(1)的空间复杂度。要求给出伪码。
给定一个非负数组,求不相邻元素的最大和。
本题源自leetcode  198 --------------------------------------------------------- 思路:1 根据下标的奇偶来,每次取,如果不强这个房子,和抢这个房子的最大值。 代码: int rob(vector& nums) { int n = nums.size(); if(n == 0
次大和次小
次大和次小