[C/C++] Liệt kê các cột nhiều chữ số nhất trong ma trận số nguyên

Yêu cầu:
Liệt kê các cột nhiều chữ số nhất trong ma trận số nguyên

Thuật toán:
1. Allocate vùng nhớ chứa số lượng kí tự trong mỗi cột ma trận
2. Đếm số lượng chữ số trong mỗi cột
3. Duyệt mảng digit_cnt để tìm cột có số lượng chữ số nhiều nhất
4. Đếm số lượng cột có nhiều chữ số nhất
5. Lưu số lượng cột vào biến output sz
6. Cấp phát vùng nhớ lưu chỉ số cột có số lượng chữ số nhiều nhất
7. Lưu chỉ số cột (nhiều chữ số nhất) vào mảng arr_max

Code:

/******** Find index of column including most digit*********
*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* FindMostDigitCol(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 = FindMostDigitCol(A, aRow, aCol, &sz);

    printf("\nThe column including most digit are: \n");
    for (idx = 0; idx < sz; idx++)
    {
        printf("column: %d\n", res[idx] + 1);
    }

    getch();
}

/*************************************************************
* Function      : FindMostDigitCol()
* 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 column including the most digit
*
* Description   : Find index of column including the most digit
*************************************************************/
int* FindMostDigitCol(int A[][M], int aRow, int aCol, int* sz)
{
    int iARow, iACol;
    int cnt = 0;
    int idx = 0;
    int max;
    int tmp;
    int *digit_cnt;
    int *max_arr;

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

    //2. Count digits in each column
    for (iACol = 0; iACol < aCol; iACol++)
    {
        for (iARow = 0; iARow < aRow; iARow++)
        {
            tmp = A[iARow][iACol];
            do
            {
                digit_cnt[iACol]++;
                tmp /= 10;

            } while (tmp > 0);
        }
    }

    //3. Sweep array to find column with most digit
    max = digit_cnt[0];
    for (idx = 1; idx < aCol; idx++)
    {
        if (max < digit_cnt[idx])
        {
            max = digit_cnt[idx];
        }
    }

    //4. Count the number of column with most digit
    for (idx = 0; idx < aCol; idx++)
    {
        if (max == digit_cnt[idx])
        {
            cnt++;
        }
    }

    //5. Save size of column with most digit
    *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 column with most digit
    cnt = 0;
    for (idx = 0; idx < aCol; idx++)
    {
        if (max == digit_cnt[idx])
        {
            max_arr[cnt++] = idx;
        }
    }
    
    free(digit_cnt);
    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: 3
Number of column: 4

A[0][0] = 101
A[0][1] = 203
A[0][2] = 110
A[0][3] = 223
A[1][0] = 1
A[1][1] = 23
A[1][2] = 10
A[1][3] = 23
A[2][0] = 22
A[2][1] = 34
A[2][2] = 33
A[2][3] = 66

A =
        101             203             110             223
        1               23              10              23
        22              34              33              66

The column including most digit are:
column: 2
column: 3
column: 4

Be the first to comment

Leave a Reply