Hỏi các giải bài toán hóc búa trên đề thi

#1

Hic, chuyện là e đang đi thi Tin Học Trẻ, cơ mà lại dùng cái Pascal ấy (từng chê dữ dội :sweat_smile:) nên chưa quen. Với lại mới vét cạn đào nông thuật toán và trường thì lại không dạy cụ thể cho kỳ thi nên tự mò :sob:.
Mọi người cho em hỏi là cách giải các bài toán đấy thường sẽ như thế nào ạ?
Trong 120 gồm Word, Excel, PowerPoint, Pascal thì nên phân thời gian thế nào ạ?

Em chân thành cảm ơn

p/s: Bài toán hack não
Cho 1 bảng vuông 3x3 chứa các số phân biệt 1 -> 9 và 3 số n1,n2,n3 thuộc bảng.
Hãy cho biết chúng có nằm trên đường chéo, ngang, dọc, hay không nằm.
Lưu ý: các số n1,n2,n3 có thể không theo trình tự

1 Like
#2

Mình có ý tưởng là xét giá trị tuyệt đối của hiệu từng cặp. nếu có 2 cặp giá trị tuyệt đối bắng nhau thì thẳng hàng, bằng 1 thì hàng ngang, bằng 3 thì hàng dọc, bằng 2 hoặc 4 thì hàng chéo.

4 Likes
#3

Nhắc tới tin học trẻ mới nhớ xD
Cậu bạn biết tùm lum ngôn ngữ cuối cùng phải lấy em nàng Pascal ra thi :laughing:

Hình như cái đề thiếu thiếu sao ý? Phải cho thêm là 1 -> 9 nằm theo thứ tự hay sao chứ nhỉ. Nếu để lộn xộn thì sẽ có trường hợp nằm cùng hàng ngang hoặc dọc hoặc chéo … hoặc không nằm :frowning:

2 Likes
#4

theo mình về cái bài toán:

Ma trận dạng :
a | b | c
d | e | f
g | h | k

(a,b,c,d,e,f,g,h,k đôi một khác nhau)
chạy For từ đầu tới khi đã xác định được vị trí của n1,n2,n3 (vị trí tính từ 1 nhé), lưu 3 vị trí đó vào 1 mảng 3 phần tử (Ví dụ Pos[3]), lúc này mảng đã có thứ tự tăng dần.
Đặt X1=Pos[2]-Pos[1], X2=Pos[1]-Pos[0]

X1=X2=1 thẳng hàng
X1=X2=3 thẳng cột
X1=X2=4 or 2 thì chéo
Ngược lại thì nằm ngoài.

3 Likes
#5

Mở rộng ra với bài toán ma trận n*n (giả sử các số cần xét là x1, x2, x3, bao nhiêu số không quan trọng miễn số lượng <= n):

|x3 - x2| == |x2 - x1| == 1: nằm trên hàng ngang.
|x3 - x2| == |x2 - x1| == n: nằm trên hàng dọc.
|x3 - x2| == |x2 - x1| == n+1 || |x3 - x2| == |x2 - x1| == n-1: nằm trên đường chéo.
6 Likes
#6

Đây là cách của mình:

B1: Vét cạn để tìm vị trí của n1.

B2: Tìm xem trong hàng, cột của n1 có đủ n2, n3 không. Ví dụ như từ n1 có vị trí [0][1] thì mình xét hàng 0 xem có đủ n1, n2, n3 không. Sau đó xét rồi xét xem cột 1 có đủ n1, n2, n3 không.

B3: Xét theo đường chéo. Đuờng chéo chính và đường chéo phụ. Cái này thì dễ rồi.

Cách này là dành cho bảng không theo thứ tự.

3 Likes
#7

Hehehehehehe, 1 lỗi nhỏ là là ăn tiết canh đó :smiley:

2 Likes
#8

đã sửa :3
e đang ngồi nghiêng nên bấm có 1 tay

1 Like
#9

Mình nghĩ cách này tốt khi kiểm tra bằng mắt thường, còn khi đưa lên code sẽ hơi rắc rối và chưa tối ưu
Trường hợp xấu nhất n1 ở vị trí cuối cùng trong ma trận thì phải tốn cái For chạy hết 9 phần tử, trong khi đó bạn đã có thể tận dụng kiểm tra vị trí của cả n2,n3.
Giả sử code kiểm tra theo thứ tự Hàng -> Cột -> Chéo mỗi lần kiểm tra là 2 For lồng nhau để kiểm tra mỗi phần tử ở Hàng,Cột,Chéo có bằng với n1,n2,n3 hay ko, mà trường hợp n1,n2,n3 nằm ở đường chéo thì phải mất thời gian kiểm Hàng và Cột, lúc này tốn 9 vòng For.
Và thêm nữa là nếu đường chéo thì chỉ kiểm tra được khi n1 ở 1 trong bốn góc nên bạn phải kiểm tra có tồn tại trường hợp nó trên đường chéo hay không.
:smile: vài giả định của mình.

2 Likes
#10

Đúng rồi. Nếu kiểm tra thêm cả n2, n3 nữa thì ok hơn. Thấy cái nào thì dừng lại ở đó.

Mình vừa nghĩ ra cách này. Hy vọng tối ưu hơn xíu.
Tạo 2 mảng hoặc một cấu trúc để lưu tọa độ của n1, n2, n3.
Vét cạn để tìm vị trí của chúng. Nếu tìm được cả 3 cái thì break liền.
Duyệt trên 2 mảng tọa độ để đếm số phần tử giống nhau ở từng mảng.
Nếu có 3 phần tử trùng nhau ở mảng cột hoặc mảng hàng thì chung cột hoặc chung hàng.
Nếu không có phần tử nào giống nhau ở cả 2 mảng thì chung đường chéo.
Ngược lại thì không chung.

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