Saya perlu memeriksa apakah saya dapat menemukan di dalam ukuran matriks yang diberikan 5*8 matriks yang memiliki transpos dan jika ada lebih dari satu saya harus menemukan yang terbesar.

Contoh matriks yang diberikan

1 2 0 3 2 1 0 7
2 3 4 1 2 3 4 5
3 4 6 2 5 6 7 6
4 5 7 3 6 8 9 8
6 7 1 4 7 9 0 9

Dalam matriks ini kita dapat menemukan matriks 4x4 yang memiliki transpos dan matriksnya terbesar di matriks utama

1 2 3 4 
2 5 6 7 
3 6 8 9 
4 7 9 0 
#include <stdio.h>

#define M 4
#define column 5
#define row 8

int main()
{
    int matrixA[5][8];

printf("please enter a matrix to check if there is a transpose matrix\n");
    for (int i = 0; i < column; i++)
    {
        for (int j = 0; j < row; j++)
        {
            printf("please enter %d row and %d column: ", i + 1, j + 1);
            scanf("%d", &matrixA[i][j]);
        }
    }
transpose(matrixA, column, row);

}

void transpose(int A[][row], int c, int r)
{
    int matrixAT[M][M];
    

    for (int size = r; size > 0; size--)
    {
        for (int j = 0; j < c - size + 1; j++)
        {
            for (int b = 0; b <= r - size; b++)
            {
                printf("Checking Matrix at row: %d , column: %d ,size: %dx%d", j, b, size, size);
                for (int k = j, w = 0; k < size + j; k++, w++)
                {
                    for (int l = b, z = 0; l < size + b; l++, z++)
                    {
                        matrixAT[w][z] = A[k][l];
                    }
                    printf("/n");
                }
                if (IsSymmetric(matrixAT, size))
                    printf("Matrix found");
            }
        }
    }
}
int IsSymmetric(int mat[M][M], int size)
{
    int flag = 0;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (mat[i][j] == mat[j][i]) flag++;
                

        }
    }
    return flag == size * size ? 1 : 0;
}

Ini kode saya, saya tidak tahu apa yang saya lakukan salah

1
Nath 23 April 2021, 05:06

2 jawaban

Jawaban Terbaik

IsSymmetric Anda lambat karena selalu memeriksa semua elemen mengapa tidak berhenti pada ketidaksetaraan pertama saja? Juga menyalinnya ke array temp lagi dan lagi ...

Masalah utamanya adalah Anda tidak memeriksa setiap posisi dan ukuran saat Anda memanggil transpose(matrixA, column, row); hanya sekali di luar loop ...

Juga main Anda tidak mengembalikan apa pun dan dinyatakan sebagai int ...

Saya akan mulai dengan kekerasan seperti ini:

#define column 5
#define row 8
int IsSymmetric(int mat[column][row], int i0,int j0,int size) // check n*n sub matrix at i0,j0 no need to copy again and again to temp array
    {
    for (int i = 0; i < size; i++)
     for (int j = 0; j < size; j++)
      if (mat[i0+i][j0+j] != mat[i0+j][j0+i]) return 0;
    return 1;
    }
int min(int a,int b){ return (a<b)?a:b; } // not sure if min is present in your environment if is comment this line out
int main()
    {
    int matrixA[5][8];
    ...
    for (int i = 0; i < column; i++)
     for (int j = 0; j < row; j++)
      for (int n = 1; n <= min(column-i,row-j); n++)
       if (IsSymmetric(matrixA,i,j,n))
        {
        // here do what you want with the i,j,n*n sub matrix
        // like remember position and size for the biggest n
        }
    ...
    return 0; // return value as you declared int main
    }

Semoga saya tidak membuat kesalahan ketik di sini karena saya baru saja menulis ini ke editor jawaban dari kode asli Anda.

Namun seperti yang Anda lihat kompleksitas O(n^4) (rata-rata O(n^3)) yang sangat lambat. Namun untuk matriks kecil Anda, itu bukan masalah.

Jika Anda membutuhkan sesuatu yang lebih cepat maka kita perlu tahu lebih banyak tentang data ... misalnya berapa kisaran nilainya? Beberapa petunjuk:

  • pada uji IsSymmetric positif satu sel submatriks lebih besar tanpa menguji elemen sebelumnya lagi (meningkatkan diagonal secara rekursif).
  • gunakan histogram untuk mendeteksi nilai yang mungkin hanya pada diagonal (muncul sekali secara global atau ganjil secara lokal)

Menggunakan hasil uji simetri tambahan dalam solusi O(n^3):

//---------------------------------------------------------------------------
#define column 5
#define row 8
//---------------------------------------------------------------------------
void submatrix_print(int mat[column][row], int i0,int j0,int n,int m)
    {
    int i,j;
    printf("%i*%i at %i,%i\r\n",n,m,i0,j0);
    for (i=0;i<n;i++,printf("\r\n"))
     for (j=0;j<m;j++)
      printf("%1i ",mat[i0+i][j0+j]);
    }
//---------------------------------------------------------------------------
void submatrix_print_transposed(int mat[column][row], int i0,int j0,int n,int m)
    {
    int i,j;
    printf("%i*%i at %i,%i\r\n",n,m,i0,j0);
    for (i=0;i<m;i++,printf("\r\n"))
     for (j=0;j<n;j++)
      printf("%1i ",mat[i0+j][j0+i]);
    }
//---------------------------------------------------------------------------
int min(int a,int b){ return (a<b)?a:b; }
int submatrix_symmetric(int mat[column][row], int i0,int j0) // returns biggest symetric submatrix size >=1 found at i0,j0
    {
    int i,n,N;
    N=min(column-i0,row-j0);    // max size that still fits into matrix
    for (n=2;n<N;n++)           // test all sizes above 1
     for(i=0;i<n-1;i++)         // only test newly added cells to last sub matrix
      if (mat[i0+n-1][j0+i]!=mat[i0+i][j0+n-1])
       return n-1;              // first non match means last tested size i svalid
    return n;                   // no mismatches mean full size is valid
    }
//---------------------------------------------------------------------------
int main()
    {
    int mat[5][8]=
        {
        1,2,0,3,2,1,0,7,
        2,3,4,1,2,3,4,5,
        3,4,6,2,5,6,7,6,
        4,5,7,3,6,8,9,8,
        6,7,1,4,7,9,0,9,
        };
    submatrix_print(mat,0,0,5,8);
//  submatrix_print_transposed(mat,0,0,5,8);

    int i,j,n,i0=0,j0=0,n0=0;
    for(i=0;i<column;i++)
     for(j=0;j<row;j++)
        {
        n=submatrix_symmetric(mat,i,j);
        if (n0<n){ n0=n; i0=i; j0=j; }
        }
    submatrix_print(mat,i0,j0,n0,n0);
    return 0;
    }
//-------------------------------------------------------------------------

Hasil dari kode tersebut adalah:

5*8 at 0,0 // input matrix
1 2 0 3 2 1 0 7 
2 3 4 1 2 3 4 5 
3 4 6 2 5 6 7 6 
4 5 7 3 6 8 9 8 
6 7 1 4 7 9 0 9 

4*4 at 1,3 // biggest symmetric sub matrix found
1 2 3 4 
2 5 6 7 
3 6 8 9 
4 7 9 0 
1
Spektre 23 April 2021, 09:34

Anda dapat membuat fungsi yang memeriksa apakah matriks dapat ditransposisikan atau tidak dan fungsi lain yang mengambil setiap waktu bagian dari matriks utama dan Anda memindahkannya setiap kali dan memeriksanya dengan fungsi 1 contoh : matriks 1 :m[1][1 ] mulai dari nol 1 2 2 3 2 matriks :m[2][2] mulai dari satu 2 0 3 4 kemudian ketika Anda selesai dengan matriks 2 dimensi Anda pergi ke 3 sampai akhir saya harap Anda mengerti saya dan maaf atas kesalahan saya Inggris

0
Chihab 23 April 2021, 02:59