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

    1 Thuật toán sắp xếp hoà nhập on Mon May 30, 2011 10:09 pm

    Admin


    Quản trị viên
    Quản trị viên
    Thủ tục hoà nhập 2 mảng đã sắp

    Bài toán 1. Cho 2 mảng đã được sắp
    X= < X(p) và Y =

    Tạo mảng Z =< Z(t),Z(t+1),..., Z(t+m-p+n-q+1) > có thứ tự từ 2 mảng X và Y.

    Mô tả thuật toán hoà nhâp 1 (HN1)
    Ý tưởng:
    1. So sánh 2 phần tử nhỏ nhất của 2 mảng. Đưa phần tử nhỏ hơn ra mảng đích.(Loại bỏ phần tử này ra khỏi mảng chứa nó)
    2. Lặp lại thủ tục này cho đến khi vét hết một trong 2 mảng.
    3. Chuyển toàn bộ phần đuôi của mảng còn lại ra mảng đích.

    Thuật giải:
    Proce. HN1(X,Y: dãy; p, m, q, n: chỉ số; VAR Z)
              1. t:=1; i:=p; j:=q;
              2. While ( i<=m) & (j<=n)
                                  a. IF Xi < Yj THEN           { Zt: = Xi, i++ }
                                                                          else { Zt: = Yj, j++ }
                                  b. t++
              3. IF i>m FOR k:=j to n
                                                                          Zt+k-j := Yk
                        ELSE FOR k:=i to m
                                                                          Zt+k-i := Xk


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

    2 Re: Thuật toán sắp xếp hoà nhập on Mon May 30, 2011 10:15 pm

    Admin


    Quản trị viên
    Quản trị viên
    Thủ tục SXHN(VAR X: dãy; d, c : chỉ số)
    IF d< c THEN
              1. m:= (d+c)/2
              2. SXHN (d,m); SXHN (m+1, c);
              3. HN1(X, X, p, m, m+1, n, Z)
              4. for t:=d to c
                        Xt:= Zt
                                  t:=1; i:=m; j:=m+1


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

    3 Re: Thuật toán sắp xếp hoà nhập on Sat Jun 04, 2011 8:21 pm

    Admin


    Quản trị viên
    Quản trị viên
    Mô phỏng đơn giả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

    sonld1984


    Chuyên viên
    Chuyên viên
    Anh Admin có Post bài lên, nhưng em thấy sai rất nhiều
    1. Chỉ số t không thể là 1.
    2. Hàm đệ quy HN1(X, X, p, m, m + 1, n, Z) sai mà phải là
    HN1(X, X, d, m, m+1, c, Z );
    3. Không biết chỉ số t là bao nhiêu ??
    Tôi nghĩ ta nên hỏi lại thày thuật toán này


    ================

    5 Re: Thuật toán sắp xếp hoà nhập on Wed Jun 08, 2011 7:01 am

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    Tôi thấy đọc trong sách rất là rõ ràng mà.
    Ở đây chia ra mấy trường hợp;
    1. Hoà nhập hai dãy x và y đã được sx không tăng hoặc không giảm. → dùng HN1 để giải quyết.
    2. Hoà nhập hai nửa của một dãy đã được sx → HN2
    3. SX trên một mảng A[a....b] → chính là giải thuật mà thầy viết.

    Proc HN1(A:mảng; var Z:mảng; var a,c,b)

    {ở đây ta dùng mảng z để lưu trữ các phần tử đã được sx, c là chỉ số giữa của mảng A: c= (a+b)/2}
    {ta chia mảng A ra thành 2 mảng con [a...c] và [c+1...b] }
    1. i:=a; j:= c+1; k:= 0;
    {i:duyệt trên [a..c]; j: duyệt trên [c+1...b]; k: duyệt trên mảng Z}
    2. {so sánh các phần tử của hai mảng con với nhau}
    While (i < = c) and (j <= b) Do
              a. If A[i] < A[j] then Z[k]: = A[i]; i:= i+1;
                        Else Z[k]: = A[j]; j:= j+1;
                                  b. k:=k+1;
    3. If i> c then
                        For l:= j to b do Z[l+k-j] : = A[l];
                                  Else
                        For l:= i to c do Z[l+k-i] : = A[l];
    4. End.


    Proc hoa_nhap(var A: dãy số; d,c: chỉ số);
    If d < c then
    1. m: = (d+c)/2;
    2. hoa_nhap(d,m); hoa_nhap(m+1, c);
    3. HN1(A,a,c,c+1,b,Z);
    4. For t: = d to c do A[t]: = Z[t];
    End.



    Được sửa bởi Admin ngày Wed Jun 08, 2011 7:11 am; sửa lần 1. (Reason for editing : Viết lại đúng cấu trúc)


    ================
    Phong độ là nhất thời, đẳng cấp mới là mãi mãi. [You must be registered and logged in to see this image.]

    6 Re: Thuật toán sắp xếp hoà nhập on Sat Aug 06, 2011 9:28 am

    tendep73


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    admin cho hỏi sao không thấy thủ tục hòa nhập 2 nhỉ

    Ban QT: Hãy tự viết

    http://nguyenvantien.ucoz.com

    7 Re: Thuật toán sắp xếp hoà nhập on Sat Aug 06, 2011 4:56 pm

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Các đồng chí hiểu sai hết rồi. Tôi khuyên nên lập trình đi. Nói trên đầy dài dòng lắm.


    ================

    8 Re: Thuật toán sắp xếp hoà nhập on Sat Aug 06, 2011 5:11 pm

    tendep73


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Proce. HN2(X: dãy; p, m, q, n: chỉ số; Z: dãy xuất)
    1. t := p; i := p; j := q;
    2. WHILE ( i ≤ m) & (j ≤ n)
              a. IF Xi < Xj THEN { Zt: = Xi, i++ }
                        ELSE { Zt: = Xj, j++ }
              b. t++
    3. IF i > m FOR k := j to n
                        Zk := Xi
              ELSE FOR k := i to m
                        Zk = Xj

    Ban QT: Đã sửa giúp đúng cấu trúc. Bạn nên dùng chữ c a c h (không có khoảng trắng) để đặt khoảng cách chữ. Hoặc đặt phần lập trình giả mã trong thẻ CODE [You must be registered and logged in to see this image.]
    Bạn nên viết đôi dòng nói qua các biến, ví dụ bài trên là xâu có 2 đoạn đã sắp xếp không giảm rồi từ vị trí này đến vị trí này chẳng hạn để mọi người dễ hình dung.

    http://nguyenvantien.ucoz.com

    9 Re: Thuật toán sắp xếp hoà nhập on Wed Aug 10, 2011 10:47 am

    gacongnghiep


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Bài thầy cho: X(d) > X(m + 2) > ......... > X(c). Tạo Y(dc) không giảm. Mình viết như sau có ok không, các bạn check hộ mình vơi.

    Proc HN2P(X: mảng; d, c, m: Chỉ số; Var Y: mảng);
    1) t = 1; i = d; j = c;
    2) WHILE (i ≤ m) & (j ≥ m) DO
              a) IF Xi < Xj THEN Yt = Xj; i = i + 1;
                        ELSE Yt = Xi; j = j-1;
              b) t = t + 1;
    3) a) IF (i > m) & (j > m) THEN
              FOR k = j DOWNTO m DO Yt = Xk; t = t + 1;
    b) IF (i FOR k = i TO m DO Yt = Xk; t = t + 1;

    Ban QT: Bạn check lại dòng tô màu, không hiểu dòng lệnh đó của bạn.

    10 Re: Thuật toán sắp xếp hoà nhập on Sat Nov 12, 2011 7:57 pm

    vinhct


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    các bạn tham khảo tại đây.
    [You must be registered and logged in to see this link.]
    Có code và Video minh họa luôn, rất hay (O)

    http://ictprovn.net

    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

    Create a forum on Forumotion | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs.com