[C/C++] Liệt kê các dòng có tổng dòng lớn nhất trong ma trận

Yêu cầu:
Liệt kê các dòng có tổng dòng lớn nhất trong ma trận

Thuật toán:
1. Allocate vùng nhớ kích thước bằng số hàng ma trận để lưu tổng các phần tử trong mỗi hàng
2. Tính tổng các phần tử trong mỗi hàng và lưu vào memory trỏ bởi con trỏ *sum
3. Duyệt mảng sum để tìm giá trị lớn nhất của mảng sum
4. Đếm số hàng có tổng lớn nhất
5. Lưu giá trị đếm được vào biến output sz
6. Cấp phát vùng nhớ trỏ bởi con trỏ arr_max để lưu chỉ số
7. Duyệt mảng sum để tìm ra các hàng có tổng lớn nhất, lưu chỉ số hàng vào mảng arr_max

Code:

/*************** Find maximum row in matrix******************
*Author: vncoding
*Date  : 13/05/2019
************************************************************/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <memory.h>
#define N 100
#define M 100

void ImportData(int[][M], int, int, char*);
void PrintMatrix(int[][M], int, int, char);
int* FindMaxRow(int[][M], int, int, int*);



void main()
{
    int aRow, aCol;
    int A[N][M];
    int *res;
    int sz = 0;
    int idx;

    printf("\nNumber of row: ");
    scanf("%d", &aRow);
    printf("\nNumber of column: ");
    scanf("%d", &aCol);

    ImportData(A, aRow, aCol, "A");
    PrintMatrix(A, aRow, aCol, 'A');

    res = FindMaxRow(A, aRow, aCol, &sz);

    printf("\nThe maximum rows are: \n");
    for (idx = 0; idx < sz; idx++)
    {
        printf("row: %d\n", res[idx] + 1);
    }

    getch();
}

/*************************************************************
* Function      : FindMaxRow()
* Parameter     : A[][M]: input matrix (I)
*                 aRow  : row number of matrix A (I)
*                 aCol  : column number of matrix A (I)
*                 sz    : size of maximum row (O)
* Return        : index of maximum row
*
* Description   : Find index of maximum row
*************************************************************/
int* FindMaxRow(int A[][M], int aRow, int aCol, int* sz)
{
    int iARow, iACol;
    int cnt = 0;
    int idx = 0;
    int max;
    int *sum;
    int *max_arr;

    //1. Allocate memory
    sum = (int*)malloc(aRow * sizeof(int));
    if (!sum)
    {
        printf("Error in allocating memory!");
        return NULL;
    }
    memset(sum, 0x00, aRow * sizeof(int));

    //2. Calculate sum of element in each row
    for (iARow = 0; iARow < aRow; iARow++)
    {
        for (iACol = 0; iACol < aCol; iACol++)
        {
            *(sum + iARow) += A[iARow][iACol];
        }
    }

    //3. Sweep array to find maximum row
    max = sum[0];
    for (idx = 1; idx < aRow; idx++)
    {
        if (max < sum[idx])
        {
            max = sum[idx];
        }
    }

    //4. Count the number of maximum row
    for (idx = 0; idx < aRow; idx++)
    {
        if (max == sum[idx])
        {
            cnt++;
        }
    }

    //5. Save size of maximum rows
    *sz = cnt;

    //6. Allocate memory to store maximum rows
    max_arr = (int*)malloc((*sz) * sizeof(int));
    if (!max_arr)
    {
        printf("Error in allocating memory!");
        return NULL;
    }
    memset(max_arr, 0x00, (*sz) * sizeof(int));

    //7. Pick up index of maximum rows into array
    cnt = 0;
    for (idx = 0; idx < aRow; idx++)
    {
        if (max == sum[idx])
        {
            max_arr[cnt++] = idx;
        }
    }

    free(sum);

    return max_arr;

}

/*************************************************************
* Function      : ImportData()
* Parameter     : A[][M]: input matrix (I)
nRow  : row number   (I)
nCol  : column number(I)
nameMatrix: matrix name (I)
* Return        : void
* Description   : Import matrix data
*************************************************************/
void ImportData(int Matrix[][M], int nRow, int nCol, char* nameMatrix)
{
    int iRow, iCol;
    for (iRow = 0; iRow < nRow; iRow++)
        for (iCol = 0; iCol < nCol; iCol++)
        {
            printf("\n%s[%d][%d] = ", nameMatrix, iRow, iCol);
            scanf("%d", &Matrix[iRow][iCol]);
        }
}

/*************************************************************
* Function      : PrintMatrix()
* Parameter     : Matrix: input matrix (I)
                  nRow  : row number   (I)
                  nCol  : column number(I)
                  name  : name of matrix (I)
* Return        : void
* Description   : Display matrix data
*************************************************************/
void PrintMatrix(int Matrix[][M], int nRow, int nCol, char name)
{
    int iRow, iCol;
    printf("\n%c = ", name);
    for (iRow = 0; iRow < nRow; iRow++)
    {
        printf("\n");
        for (iCol = 0; iCol < nCol; iCol++)
        {
            printf("\t%d\t", Matrix[iRow][iCol]);
        }
    }
}

Kết quả:

Number of row: 4
Number of column: 4

A[0][0] = 1
A[0][1] = 2
A[0][2] = 3
A[0][3] = 4
A[1][0] = 0
A[1][1] = 1
A[1][2] = 2
A[1][3] = 3
A[2][0] = 4
A[2][1] = 3
A[2][2] = 2
A[2][3] = 1
A[3][0] = 3
A[3][1] = 2
A[3][2] = 4
A[3][3] = 1

A =
        1               2               3               4
        0               1               2               3
        4               3               2               1
        3               2               4               1

The maximum rows are:
row: 1
row: 3
row: 4

Be the first to comment

Leave a Reply

Your email address will not be published.

*