Đạ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]

    Admin


    Quản trị viên
    Quản trị viên
    Bạn Khách viếng thăm thân!
    Xem xét một cách toàn diện thì đề thi về CTDL và GT thường rất dài. Nghĩa là khi vào thi mà Khách viếng thăm không cắm cúi viết liên tục từ đầu đến cuối thì có lẽ chẳng thể kịp thời gian. Có nghĩa là Khách viếng thăm có tài giỏi đến mấy mà không chịu học thuộc thì không thể có điểm cao được.

    Các đề thi trong 1 câu thường có 1 phần là yêu cầu Khách viếng thăm phải biểu diễn bằng tay từng bước một công việc nào đấy. Việc biểu diễn duyệt đồ thị cũng hay được yêu cầu trên các đề thi. Việc này cần thực hiện và trình bày thì Khách viếng thăm phải làm như thế nào?

    Ví dụ:
    Đề sẽ cho 1 đồ thị. Nếu họ vẽ ra, thì sẽ yêu cầu Khách viếng thăm viết một ma trận kề, hoặc danh sách kề. Hoặc ngược lại, nếu đề ra một ma trận kề, hoặc danh sách kề thì Khách viếng thăm phải vẽ được đồ thị ra. Việc này rất quan trọng, nó quyết định rằng Khách viếng thăm có làm đúng hay làm sai và có được điểm hay không?

    Giả sử có danh sách kề như sau:


    v

    Kề của v

    a

    b, c, d, e

    b

    a, d

    c

    a, e, g

    d

    b, a, e

    e

    d, f, g, c, a

    f

    e, g

    g

    e, c, f
    Bây giờ đề bài yêu cầu chúng ta mô tả việc duyệt theo chiều sâu thì phải làm thế nào?

    Đầu tiên, bản chất của việc duyệt theo chiều sâu là gì? Giả sử duyệt từ đỉnh a, thì hãy coi đỉnh a như là gốc. Nguyên tắc duyệt là chạy nhanh càng xa khỏi gốc trước, duyệt từ xa, sau đó với co dần lại. Ngược lại, với duyệt theo chiều rộng thì duyệt hết những đình kề hiện tại, rồi mới duyệt các đỉnh xa hơn.

    Duyệt theo chiều sâu sử dụng đệ quy, còn duyệt theo chiều rộng, sử dụng hàng đợi.

    Thôi cố đọc sách của thầy Đỗ Xuân Lôi, mua ở cửa hàng sách cũ khoảng 10.000 - 15.000 cuốn, sẽ hiểu hết mà. Hoặc thích đọc qua máy tính thì [You must be registered and logged in to see this link.].

    Cách làm:
    1. Vẽ lại bảng danh sách kề vào bài thi
    2. Đánh các số be bé giống như luỹ thừa vào các đỉnh. Đây là thứ tự duyệt.
    3. Nhớ đánh dấu các đỉnh đã duyệt để tránh duyệt nhầm vào đỉnh đã duyệt rồi.
    4. Ghi xuống 1 dòng cuối bảng thứ tự các đỉnh đã duyệt.

    Bài trên làm thế nào?
    Xem cách trình bày đây sẽ hiểu.

    Duyệt theo chiều sâu, bắt đầu từ đỉnh a.


    Dấu

    v

    Kề của v

    x

    a1

    b2, c, d, e

    x

    b

    a, d3

    x

    c

    a, e, g

    x

    d

    b, a, e4

    x

    e

    d, f5, g, c, a

    x

    f

    e, g6

    x

    g

    e, c7, f
    Thứ tự:
    a, b, d, e, f , g, c
    Bây giờ Khách viếng thăm cần chia sẻ cùng mọi người đi!


    ================
    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

    Admin


    Quản trị viên
    Quản trị viên
    Bây giờ cần trình bày duyệt tay theo chiều rộng xuất phát từ a thì làm thế nào vào bài thi?
    Kẻ lại cái bảng ra, có cột để đánh dấu, cũng đánh thứ tự như cái bảng duyệt chiều sâu nhé!
    Phía dưới bảng ghi 2 dòng:
    Dòng 1, ghi thứ tự của hàng đợi.
    Dòng 2, ghi kết quả.

    Làm như vầy:

    Dấu

    v

    Kề của v

    x

    a1

    b2, d3, e4, c5

    x

    b

    a, d

    x

    c

    a, e, g

    x

    d

    b, a, e

    x

    e

    d, f6, g7,
    c, a


    x

    f

    e, g

    x

    g

    e, c, f



    Hàng đợi: a, b, d, e, c, f, g
    Kết quả: a, b, d, e, c, f, g


    ================
    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

    Admin


    Quản trị viên
    Quản trị viên
    Cho đồ thị G {V, E} có n đỉnh 1-n. Cho bởi danh sách cạnh.
    DS [1..m] of cạnh
              cạnh = record
                        đ,c : tên đỉnh;
                        t: trọng số;
              end;

    a. Viết thủ tục tìm cây khung bé nhất theo thuật toán Prim.
    b. Áp dụng tính bằng tay với các dữ liệu sau:
    Đỉnh
    Đầu Cuối Trọng số
    a b 5
    b c 4
    b d 2
    a m 3
    f e 6
    d e 3
    d f 4
    d b 5
    d c 2
    a f 7
    b n 6
    n c 7
    c m 4
    d n 2
    m e 4
    f m 4
    a n 5
    a c 2
    f c 1
    b e 2
    e c 2
    Cách thực hiện bài này như thế nào?

    a. Việc viết thủ tục tính cây khung bé nhất xem [You must be registered and logged in to see this link.]
    b. Các bước cần thực hiện bằng tay như sau:
    Bước 1. Viết lại bảng dữ liệu trên bằng cách sắp xếp trọng số tăng dần.
    Ta có bảng dữ liệu B1 đã viết lại, có thêm cột k cuối cùng để ghi lại các bước cần xem xét.
    Đỉnh
    Đầu Cuối Trọng số k
    f c 1
    b d 2
    d c 2
    d n 2
    a c 2
    b e 2
    e c 2
    a m 3
    d e 3
    b c 4
    d f 4
    c m 4
    m e 4
    f m 4
    a b 5
    d b 5
    a n 5
    f e 6
    b n 6
    a f 7
    n c 7
    Bước 2. Tiếp theo, kẻ một bảng theo dõi B2, để đánh dấu như sau:
    V a b c d e f m n
    VT







    Bước 3. Xét trong danh sách từ trên xuống của bảng B1 chọn cạnh có trọng số nhỏ nhất. Đánh dấu cột k =1. Đồng thời đánh dấu x vào bảng B2 dòng VT những đỉnh đã duyệt.

    Bước 4. Thực hiện duyệt từ trên xuống, bảng B1, những dòng nào còn trống của cột k thì kiểm tra ở bảng B2 xem có đáp ứng được một đình đã có trong VT, còn đỉnh kia chưa có trong VT không. Nếu đáp ứng được thì đánh dấu lại giá trị k ++ vào cột k của B1 và đánh dấu x vào bảng B2 dòng VT đỉnh đã duyệt.

    Bước 5. Ghi kết quả:
    Ghi theo thứ tự của cột k các cạnh. Đồng thời tính độ lớn của cây khung bằng tổng các trọng số.
    Ví dụ sau bước 5 B1 sẽ là:
    Đỉnh

    Đầu Cuối Trọng số k
    f c 1 1
    b d 2 3
    d c 2 2
    d n 2 4
    a c 2 6
    b e 2 5
    e c 2
    a m 3
    d e 3
    b c 4 7
    d f 4
    c m 4
    m e 4
    f m 4
    a b 5
    d b 5
    a n 5
    f e 6
    b n 6
    a f 7
    n c 7
    Ghi lại kết quả:
    Cây khung: {(f, c), (d, c), (b, d), (d, n), (b, e), (a, c), (b, c)}
    Tổng của các trọng số là: 14


    ================
    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

    TuanNghia


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Cám ơn anh Admin, vì em không có điều kiện đi ôn thi nên việc ôn tập cũng vất vả lắm. Tiện đây mong anh giúp em, với đồ thị cho Như trên thì việc giải tay đối với bài cây khung nhỏ nhất với thuật toán Kruskal là như thế nào ạ.

    Mong anh giúp em để hiểu hơn về thuật toán này...

    Ban QT: Tương tự, bằng cách copy đoạn trên ra ra bỏ bước (không kiểm tra) liên thuộc.

    kim pha na


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    hi . em đoc chẳng hiểu các anh có thể viết c++ về thuật toán prim tìm cây khung nhỏ nhất được không?

    Ban QT:
    Ở đây trình bày để làm vào bài thi được điểm. Học về giải thuật phải viết bằng giả mã. Nếu muốn xem cụ thể thì down tài liệu trên để đọc và muốn xem viết bằng C++ thì sử dụng gooogle... Bạn không làm theo yêu cầu của đề bài sẽ được 0 điểm phần trình bày của bạn.

    huutaisc


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    [quote="Admin"]Bạn Khách viếng thăm thân!
    Xem xét một cách toàn diện thì đề thi về CTDL và GT thường rất dài. Nghĩa là khi vào thi mà Khách viếng thăm không cắm cúi viết liên tục từ đầu đến cuối thì có lẽ chẳng thể kịp thời gian. Có nghĩa là Khách viếng thăm có tài giỏi đến mấy mà không chịu học thuộc thì không thể có điểm cao được.

    Các đề thi trong 1 câu thường có 1 phần là yêu cầu Khách viếng thăm phải biểu diễn bằng tay từng bước một công việc nào đấy. Việc biểu diễn duyệt đồ thị cũng hay được yêu cầu trên các đề thi. Việc này cần thực hiện và trình bày thì Khách viếng thăm phải làm như thế nào?

    Ví dụ:
    Đề sẽ cho 1 đồ thị. Nếu họ vẽ ra, thì sẽ yêu cầu Khách viếng thăm viết một ma trận kề, hoặc danh sách kề. Hoặc ngược lại, nếu đề ra một ma trận kề, hoặc danh sách kề thì Khách viếng thăm phải vẽ được đồ thị ra. Việc này rất quan trọng, nó quyết định rằng Khách viếng thăm có làm đúng hay làm sai và có được điểm hay không?

    Giả sử có danh sách kề như sau:


    v

    Kề của v

    a

    b, c, d, e

    b

    a, d

    c

    a, e, g

    d

    b, a, e

    e

    d, f, g, c, a

    f

    e, g

    g

    e, c, f
    Bây giờ đề bài yêu cầu chúng ta mô tả việc duyệt theo chiều sâu thì phải làm thế nào?
    Duyệt theo chiều sâu :
    Bắt đầu từ đỉnh a -> ta tới b ta được a,b
    từ b : kiếm đỉnh kề của b không nằm khác a,b . ta đươc (d) -> a b d .
    từ d : kiem dinh ke của d khong nam trong a b d .ta duoc (e) -> a b d e
    tu e : kiem dinh ke cua e khong nam trong a b d e ta duoc (f) ->a b d e f
    tu f : kiem dinh ke cua f khong nam trong a b d e f ta duoc (g) -> a b d e f g
    tu f: kiem dinh ke cua f khong nam trong a b d e f ta duoc (c)-> a b d e f g c
    Đến đây là kết thúc nha các bạn ~)

    Duyệt theo chiều rộng :
    Bắt đầu từ đỉnh a, liệt kê hết các đỉnh kề của a ta được -> a b c d e
    nhin vao day tren ta thay tiep theo a la b.
    liet ke tap dinh cua b ma khong co trong a b c d e -> khong co dinh nao
    tiep theo b la c. liet ke cac dinh cua c khong co trong a b c d e (g) -> a b c d e g
    tiep theo c la d. liet ke cac dinh cua d khong co trong a b c d e g (khong co)
    tiep theo d la e . liet ke cac dinh cua e khong co trong a b c d e g (f) -> a b c d e g f
    Đủ các đinh thì la dừng lại -> a b c d e g f

    Minto Trầm


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Theo em thì kết quả bài này phải là:
    (f,c); (d,c);(b,d);(d,n);(a,c);(b,e);(a,m)
    Mọi người kiểm tra lại xem có đúng không ạ.
    Admin đã viết:Cho đồ thị G {V, E} có n đỉnh 1-n. Cho bởi danh sách cạnh.
    DS [1..m] of cạnh
              cạnh = record
                        đ,c : tên đỉnh;
                        t: trọng số;
              end;

    a. Viết thủ tục tìm cây khung bé nhất theo thuật toán Prim.
    b. Áp dụng tính bằng tay với các dữ liệu sau:
    Đỉnh
    Đầu Cuối Trọng số
    a b 5
    b c 4
    b d 2
    a m 3
    f e 6
    d e 3
    d f 4
    d b 5
    d c 2
    a f 7
    b n 6
    n c 7
    c m 4
    d n 2
    m e 4
    f m 4
    a n 5
    a c 2
    f c 1
    b e 2
    e c 2
    Cách thực hiện bài này như thế nào?

    a. Việc viết thủ tục tính cây khung bé nhất xem [You must be registered and logged in to see this link.]
    b. Các bước cần thực hiện bằng tay như sau:
    Bước 1. Viết lại bảng dữ liệu trên bằng cách sắp xếp trọng số tăng dần.
    Ta có bảng dữ liệu B1 đã viết lại, có thêm cột k cuối cùng để ghi lại các bước cần xem xét.
    Đỉnh
    Đầu Cuối Trọng số k
    f c 1
    b d 2
    d c 2
    d n 2
    a c 2
    b e 2
    e c 2
    a m 3
    d e 3
    b c 4
    d f 4
    c m 4
    m e 4
    f m 4
    a b 5
    d b 5
    a n 5
    f e 6
    b n 6
    a f 7
    n c 7
    Bước 2. Tiếp theo, kẻ một bảng theo dõi B2, để đánh dấu như sau:
    V a b c d e f m n
    VT







    Bước 3. Xét trong danh sách từ trên xuống của bảng B1 chọn cạnh có trọng số nhỏ nhất. Đánh dấu cột k =1. Đồng thời đánh dấu x vào bảng B2 dòng VT những đỉnh đã duyệt.

    Bước 4. Thực hiện duyệt từ trên xuống, bảng B1, những dòng nào còn trống của cột k thì kiểm tra ở bảng B2 xem có đáp ứng được một đình đã có trong VT, còn đỉnh kia chưa có trong VT không. Nếu đáp ứng được thì đánh dấu lại giá trị k ++ vào cột k của B1 và đánh dấu x vào bảng B2 dòng VT đỉnh đã duyệt.

    Bước 5. Ghi kết quả:
    Ghi theo thứ tự của cột k các cạnh. Đồng thời tính độ lớn của cây khung bằng tổng các trọng số.
    Ví dụ sau bước 5 B1 sẽ là:
    Đỉnh

    Đầu Cuối Trọng số k
    f c 1 1
    b d 2 3
    d c 2 2
    d n 2 4
    a c 2 6
    b e 2 5
    e c 2
    a m 3
    d e 3
    b c 4 7
    d f 4
    c m 4
    m e 4
    f m 4
    a b 5
    d b 5
    a n 5
    f e 6
    b n 6
    a f 7
    n c 7
    Ghi lại kết quả:
    Cây khung: {(f, c), (d, c), (b, d), (d, n), (b, e), (a, c), (b, c)}
    Tổng của các trọng số là: 14

    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 | Create a free blog