Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Trên bàn cờ quốc tế A[1..8, 1..8], giả sử quân mã nằm ở ô (x, y). Cho ô (i, j), hãy sử dụng mô hình đồ thị để xác định cách đi quân mã từ ô (x, y) đên ô (i, j) sao cho tốn ít nước nhất.
    Bài này tôi viết hơi dài, mọi người đọc và kiểm tra độ đúng đắn của thuật toán và sửa lại cho ngắn nhé. Bài viết sử dụng thuật toán duyệt theo chiều rộng.
    FOR m : = 1 TO 8 DO
              FOR n : = 1 TO 8 DO
                        Đã_xét(a(m, n)) : = 0;

    {Viết ngược. Vì đường đi ngắn nhất từ (x, y)→(i, j) cũng chính là đường đi ngắn nhất từ (i, j)→(x, y), cái này liên quan đến output đường đi ở dưới cùng)}
    u : = i;
    v : = j;
    Enqueue (a(u, v), HĐ)
    Đã_xét(a(u, v)) : = 1;
    WHILE Đã_xét(x, y) ≠ 0 DO
              u : = front(HĐ).hàng;
              v : = front(HĐ).cột;
              DeQueue(HĐ);
    {kiểm tra các cách nhảy của ngựa vào ô tiếp theo. Nếu ô đó nằm trong bàn cờ và chưa xét thì cho vào hàng đợi. Gán chỉ số ô tiếp theo bằng chỉ số ô trước nó cộng thêm 1. Có nghĩa là chỉ số của ô sẽ bằng số lần nhảy từ ô xuất phát đến ô đó}
              IF ((u ≤ 6 & v ≥ 1) & Đã_xét(a(u + 2, v - 1)) = 0) THEN
                        Enqueue (a(u + 2, v - 1), HĐ);
                        Đã_xét(a(u + 2, v - 1) : = Đã_xét(a(u, v)) + 1;
              IF ((u ≤ 6 & v ≤ 7) & Đã_xét(a(u + 2, v + 1)) = 0) THEN
                        Enqueue (a(u + 2, v + 1), HĐ);
                        Đã_xét(a(u + 2, v + 1)) : = Đã_xét(a(u, v)) + 1;
              IF ((u ≤ 7 & v ≤ 6) & Đã_xét(a(u + 1, v + 2)) = 0) THEN
                        Enqueue (a(u + 1, v + 2), HĐ);
                        Đã_xét(a(u + 1, v + 2)) : = Đã_xét(a(u, v)) + 1;
              IF ((u ≥ 1 & v ≤ 6) & Đã_xét(a(u - 1, v + 2)) = 0) THEN
                        Enqueue (a(u - 1, v + 2), HĐ);
                        Đã_xét(a(u - 1, v + 2)) : = Đã_xét(a(u, v)) + 1;
              IF ((u ≥ 2 & v ≥ 7) & Đã_xét(a(u - 2, v + 1)) = 0) THEN
                        Enqueue (a(u - 2, v + 1), HĐ);
                        Đã_xét(a(u - 2, v + 1)) : = Đã_xét(a(u, v)) + 1;
              IF ((u ≥ 2 & v ≥ 1) & Đã_xét(a(u - 2, v - 1)) = 0) THEN
                        Enqueue (a(u - 2, v - 1), HĐ);
                        Đã_xét(a(u - 2, v - 1)) : = Đã_xét(a(u, v)) + 1;
              IF ((u ≥ 1 & v ≥ 2) & Đã_xét(a(u - 1, v - 2)) = 0) THEN
                        Enqueue (a(u - 1, v - 2), HĐ);
                        Đã_xét(a(u - 1, v - 2)) : = Đã_xét(a(u, v)) + 1;
              IF ((u ≤ 7 & v ≥ 2) & Đã_xét(a(u + 1, v - 2)) = 0) THEN
                        Enqueue (a(u + 1, v - 2), HĐ);
                        Đã_xét(a(u + 1, v - 2)) : = Đã_xét(a(u, v)) + 1;

    {Viết lại đường đi của con mã (viết ngược, nếu muốn viết xuôi, có lẽ đổi vai trò cho chúng ngay từ đầu. Vì đường đi ngắn nhất từ (x y)→(i, j) cũng chính là đường đi ngắn nhất từ (i, j)→(x y))}
    k : = Đã_xét (a(x, y));
    u : = x;
    v : = y;
    write(a(u, v);
    WHILE k ≠1 DO
              IF ((u ≤ 6 & v ≥ 1) & Đã_xét(a(u + 2, v - 1)) = k - 1) THEN k : = k - 1; u0 : = u + 2; v0 : = v - 1;
              IF ((u ≤ 6 & v ≤ 7) & Đã_xét(a(u + 2, v + 1)) = k - 1) THEN k : = k - 1; u0 : = u + 2; v0 : = v + 1;
              IF ((u ≤ 7 & v ≤ 6) & Đã_xét(a(u + 1, v + 2)) = k - 1) THEN k : = k - 1; u0 : = u + 1; v0 : = v + 2;
              IF ((u ≥ 1 & v ≤ 6) & Đã_xét(a(u - 1, v + 2)) = k - 1) THEN k : = k - 1; u0 : = u - 1; v0 : = v + 2;
              IF ((u ≥ 2 & v ≥ 7) & Đã_xét(a(u - 2, v + 1)) = k - 1) THEN k : = k - 1; u0 : = u - 2; v0 : = v + 1;
              IF ((u ≥ 2 & v ≥ 1) & Đã_xét(a(u - 2, v - 1)) = k - 1) THEN k : = k - 1; u0 : = u - 2; v0 : = v - 1;
              IF ((u ≥ 1 & v ≥ 2) & Đã_xét(a(u - 1, v - 2)) = k - 1) THEN k : = k - 1; u0 : = u - 1; v0 : = v - 2;
              IF ((u ≤ 7 & v ≥ 2) & Đã_xét(a(u + 1, v - 2)) = k - 1) THEN k : = k - 1; u0 : = u + 1; v0 : = v - 2;
              u : = u0;
              v : = v0;
              write(a(u, v));
    - May mà viết sẵn ở trong word, chẳng biết bấm chỉnh sửa gì mà toàn bộ dấu + ("cộng") bị mất hết. Mấy bài trung tố, hậu tố tôi đọc cũng bị mất hết dấu cộng. Viết ở Firefox thì mới thêm được bảng, nhưng lại gặp rắc rối này.


    ================
    [You must be registered and logged in to see this image.]

    Admin


    Quản trị viên
    Quản trị viên
    Lỗi mất dấu cộng là do cái thằng WYSIWYG. Khi cài thằng này vào diễn đàn (để gõ thế nào, định dạng luôn thế ấy, không phải soạn ở HTML) thì nó không tương thích với Forum PunBB. Nên nếu có nháy vào nút A/A thì khi quay lại nhớ phải kiểm tra dấu "cộng" và dấu "xuống dốc", nó sẽ xoá bỏ các dấu này tự động, đồng thời xoá luôn 1 loạt dấu cách thay bằng một dấu cách. Thế nên tôi mới phải điều trị nó bằng chữ c a c h. Rất củ chuối. Những lỗi lặt vặt này chỉnh rất mất thời gian, nên để dành khi thi xong. Những bài dài, theo tôi nên soạn trong Word copy sang là tốt nhất (Trừ mấy công thức thì cần khôn một tí để dán).
    [You must be registered and logged in to see this image.]


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Công nhận là MrP làm bài này cũng tốt thật. Đề thi mà có câu này, chắc nhiều người sẽ bị ngất vì họ không bít đánh cờ vua, đọc đã choáng huống chi là làm...
    Kiểu này phải học cách đánh cờ. Hình như quân Mã đi theo hình chữ nhật 2x3 hoặc 3x2. Có bài cơ bản là 2 ô cạnh nhau, đi mấy nước, 2 ô đối nhau đi mấy nước. Mấy lần em học mà không đi được. Nếu quen được điều đó chắc thì làm bài dạng này dễ hơn nhiều.


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    4 Bài toán con ngựa on Wed Jul 13, 2011 5:53 pm

    abc


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Viết kiểu này, theo em chẳng hay gì cả.
    Thực ra, với một con mã ở vị trí (i,j), rõ ràng có thể biết được ngay vị trí sẽ đến của nó.
    Đưa các vị trí sẽ đến vào mảng, sau đó duyệt mảng (tối đa 8 vị trí).
    Viết ngắn và dễ nhớ hơn nhiều.
    Tham khảo mấy bài của các thầy Học viện đã giảng về CTDL>, rất rõ ràng và dễ nhớ.
    Good luck!

    http://www.cafetuoitre.com

    huyenminh


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    Xem bài này xong mà chảng hiểu gì các bác ạ.

    6 Re: bài toán con mã on Tue Mar 05, 2013 1:26 am

    heocoiminmin


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    anh MrP ơi, a có code bài này ko, share cho em với, cảm ơn anh nhiều ạh!

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | www.sosblogs.com