ในปัญหานี้ เราได้รับเมทริกซ์สี่เหลี่ยมขนาด nXn งานของเราคือ หาค่าน้อยที่สุดและมากที่สุดจากแนวทแยงของเมทริกซ์สี่เหลี่ยม เราต้องหาค่าน้อยที่สุดและมากที่สุดของแนวทแยงหลักและแนวทแยงรองของเมทริกซ์
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input
mat[][] = {
{3, 4, 7},
{5, 2, 1},
{1, 8, 6}
}
Output
Smallest element in Primary Diagonal = 2 Largest element in Primary Diagonal = 6 Smallest element in Secondary Diagonal = 1 Largest element in Secondary Diagonal = 7
วิธีแก้ปัญหา
วิธีแก้ที่ง่ายคือใช้ nested loops สำหรับตรวจสอบองค์ประกอบที่แนวทแยงหลัก เราจะพิจารณา i = j และสำหรับแนวทแยงรอง เราจะพิจารณา i + j = n - 1 เราจะหาค่าสูงสุดและต่ำสุดของเมทริกซ์สำหรับทั้งแนวทแยงหลักและแนวทแยงรอง
โปรแกรมแสดงการทำงานของวิธีแก้
ตัวอย่าง
#include<iostream>
using namespace std;
void findMaxAndMinOfDiagonals(int mat[3][3], int n){
if (n == 0)
return;
int pDiagMin = mat[0][0],
pDiagMax = mat[0][0];
int sDiagMin = mat[0][n - 1],
sDiagMax = mat[0][n - 1];
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (i == j){
if (mat[i][j] < pDiagMin)
pDiagMin = mat[i][j];
if (mat[i][j] > pDiagMax)
pDiagMax = mat[i][j];
}
if ((i + j) == (n - 1)) {
if (mat[i][j] < sDiagMin){
sDiagMin = mat[i][j];
}
if (mat[i][j] > sDiagMax)
sDiagMax = mat[i][j];
}
}
}
cout<<("\nSmallest Element of Principal Diagonal: ")<<pDiagMin;
cout<<("\nGreatest Element of Principal Diagonal: ")<<pDiagMax;
cout<<("\nSmallest Element of Secondary Diagonal: ")<<sDiagMin;
cout<<("\nGreatest Element of Secondary Diagonal: ")<<sDiagMax;
}
int main(){
int mat[3][3] = {
{ 3, 4, 7 },
{ 0, 2, 1 },
{ 1, 7, 8 }
};
int n = sizeof(mat) / sizeof(mat[0]);
findMaxAndMinOfDiagonals(mat, n);
}
ผลลัพธ์
Smallest Element of Principal Diagonal: 2 Greatest Element of Principal Diagonal: 8 Smallest Element of Secondary Diagonal: 2 Greatest Element of Secondary Diagonal: 7
วิธีแก้ที่มีประสิทธิภาพมากกว่าคือลด nested loop เหลือ single loop โดยใช้ข้อเท็จจริงที่ว่า สำหรับแนวทะแยงหลัก ดัชนีทั้งสองของเมทริกซ์เหมือนกัน คือ
primary diagonal elements = mat[i][j] เช่นเดียวกัน สำหรับแนวทแยงรอง elements = mat[i][n - i - 1]
โปรแกรมแสดงการทำงานของวิธีแก้
ตัวอย่าง
#include<iostream>
using namespace std;
void findMaxAndMinOfDiagonals(int mat[3][3], int n){
if (n == 0)
return;
int pDiagMin = mat[0][0],
pDiagMax = mat[0][0];
int sDiagMin = mat[0][n - 1],
sDiagMax = mat[0][n - 1];
for (int i = 1; i < n; i++) {
if (mat[i][i] < pDiagMin)
pDiagMin = mat[i][i];
if (mat[i][i] > pDiagMax)
pDiagMax = mat[i][i];
if (mat[i][n - 1 - i] < sDiagMin)
sDiagMin = mat[i][n - 1 - i];
if (mat[i][n - 1 - i] > sDiagMax)
sDiagMax = mat[i][n - 1 - i];
}
cout<<("\nSmallest Element of Principal Diagonal: ")<<pDiagMin;
cout<<("\nGreatest Element of Principal Diagonal: ")<<pDiagMax;
cout<<("\nSmallest Element of Secondary Diagonal: ")<<sDiagMin;
cout<<("\nGreatest Element of Secondary Diagonal: ")<<sDiagMax;
}
int main(){
int mat[3][3] = {
{ 3, 4, 7 },
{ 0, 2, 1 },
{ 1, 7, 8 }
};
int n = sizeof(mat) / sizeof(mat[0]);
findMaxAndMinOfDiagonals(mat, n);
}
ผลลัพธ์
Smallest Element of Principal Diagonal: 2 Greatest Element of Principal Diagonal: 8 Smallest Element of Secondary Diagonal: 1 Greatest Element of Secondary Diagonal: 7
