Không hiểu đề bài kỹ thuật lập trình c++: tìm phần tử hoàng hậu trong ma trận

#1

tim max.jpg1366×768 278 KB
đề bài như này khác gì tìm phân tử max của ma trận đâu nhỉ,sao thầy lại bảo duyệt ngang dọc ,chéo làm gì cho phức tạp nhỉ

#2

Phần tử này thoả mãn các yêu cầu:

  1. Nằm trên đường chéo chính
  2. Lớn nhất trong tất cả các đường đi qua nó

Nó giống như tìm cực đại địa phương của đồ thị vậy.

1 Like
#3

ai gợi ý xíu đi ạ,em ko biết bắt đầu như nào nữa

#4

Đây là môn gì đó cậu?

#5

kỹ thuât lâp trinh c++

#6

VD có 1 mảng như này

0,0,0,0
0,0,0,9
0,6,0,0
0,0,0,0

Theo mình hiểu thì mảng này sẽ có 2 hoàng hậu 6 và 9, mặc dù 9 là max của mảng nhưng cả 6 và 9 đều thỏa mãn điều kiện đề bài :smile:

1 Like
#7

thế là có nhiêu phân tử hoàng hậu à ,tưởng có 1 chớ

#9

nhìn na ná bài 8 quân hậu nhỉ, chỉ có có vì đặt quân hậu sao cho k bị các hậu có thể ăn nhau, thì h phải kiểm tra cột, hàng đường chéo chính, phụ mà nó đứng xem nó đã là lớn nhất chưa,

1 Like
#10

Tham số hóa hết các đường là một cách giải bài đó.

Bài này cụ thể là giải bài yên ngựa trước rồi mới khởi động tìm đường chéo. Ngược lại cũng được nhưng yên ngựa dễ viết.

1 Like
#11

9 ko phải là hoàng hậu vì không thuộc đường chéo chính

#12

Vậy là với mảng trên chỉ cần xét 4 ô trên đường chéo chính thôi ak :confused: thế dễ quá nhể

1 Like
#13

Nói như bạn thì hóa ra chỉ cần xét mỗi ô trung tâm là xong.

#14

Thế các ô ở góc cũng thuộc đường chéo chính thì sao?
Với mảng 4x4 thì có tất cả 8 ô cần xét, mỗi đường chéo chính có 4 ô
Với mảng 5x5 thì có tất cả 9 ô cần xét, mỗi đường chéo chính có 5 ô, giao nhau ở tâm

Tuy nhiên, khi xét mỗi ô, ta phải xem xét tất cả 4 đường đi qua ô đó (Nếu là góc thì chỉ có 3). Cho nên có khả năng trong ma trận không có hoàng hậu.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?