Đạ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 [Hướng dẫn]Sắp xếp vun đống on Tue May 31, 2011 10:33 am

    Admin


    Quản trị viên
    Quản trị viên
    Sắp xếp vun đống (Heapsort)
    Định nghĩa: Một cây nhị phân nếu xét từ trên xuống dưới, từ trái sang phải mà khoá của một nút luôn ≥ nút con thì gọi là đống.
    Cần lưu ý:
    - Không nói gì, ngầm định là đống không tăng theo định nghĩa, còn trường hợp đống không giảm, đề sẽ nói rõ.
    - Không nói gì, ngầm định là đống được lưu trữ vào dạng mảng danh sách. Lần lượt từ trái sang phải, hết mức nọ đến mức kia. Hết hàng nọ đến hàng kia.
    Về chỉ số: Nếu i chỉ ra nút bất kì, tuy nhiên i ≤ n/2, thì :
    - Con trái có chỉ số là: 2i
    - Con phải có chỉ số là: 2i+1
    - Khi nói con chung chung, ngầm định là con trái.

    Một cây nhị phân, được gọi là đống cực đại nếu khóa của mọi nút không nhỏ hơn khóa các con của nó. Khi biểu diễn một mảng a[] bởi một cây nhị phân theo thứ tự tự nhiên điều đó nghĩa là a[i] ≥ a[2*i] và a[i] ≥ a[2*i +1] với mọi i =1..int(n/2). Ta cũng sẽ gọi mảng như vậy là đống. Như vậy trong đống a[1] (ứng với gốc của cây) là phần tử lớn nhất. Mảng bất kỳ chỉ có một phần tử luôn luôn là một đống.

    Vun đống
    Việc sắp xếp lại các phần tử của một mảng ban đầu sao cho nó trở thành đống được gọi là vun đống.

    Vun đống tại đỉnh thứ i
    Nếu hai cây con gốc 2 * i và 2 * i +1 đã là đống thì để cây con gốc i trở thành đống chỉ việc so sánh giá trị a[i] với giá trị lớn hơn trong hai giá trị a[2 * i] và a[2 * i + 1], nếu a[i] nhỏ hơn thì đổi chỗ chúng cho nhau. Nếu đổi chỗ cho a[2 * i], tiếp tục so sánh với con lớn hơn trong hai con của nó cho đến khi hoặc gặp đỉnh lá.


    Vun một mảng thành đống

    Để vun mảng a[1..n] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j]với j =Int(n/2) ngược lên tới a[1]. (Thủ tục MakeHeap trong giả mã dưới đây).

    Sắp xếp bằng vun đống
    Đổi chỗ (Swap): Sau khi mảng a[1..n] đã là đống, lấy phần tử a[1] trên đỉnh của đống ra khỏi đống đặt vào vị trí cuối cùng n, và chuyển phần tử thứ cuối cùng a[n] lên đỉnh đống thì phần tử a[n] đã được đứng đúng vị trí.

    Vun lại: Phần còn lại của mảng a[1..n-1] chỉ khác cấu trúc đống ở phần tử a[1]. Vun lại mảng này thành đống với n-1 phần tử.

    Lặp: Tiếp tục với mảng a[1..n-1]. Quá trình dừng lại khi đống chỉ còn lại một phần tử.

    Lưu ý khi đọc đề và làm bài:
    - Khi đề bài ra như sau: Cho mảng X{X1, X2...Xn}, trong đó các giá trị X1, X2..Xn là các số cho sẵn.
    - Hỏi: Chứng minh rằng đây không phải là đống, hoặc xác định xem X có phải là đống không. Thì khi làm chỉ cần chỉ ra 2 phần tử không thuộc tính chất của đống. Sau đó khẳng định luôn nó không phải là đống. Còn nếu khẳng định X là đống thì chứng minh theo tính chất của đống là với mọi chỉ số i <i ≥ X2i và Xi ≥ X2i+1. Khi đề không yêu cầu viết chương trình giả mã, thì chỉ việc vẽ các bước để sắp xếp thành đống.

    Ví dụ đề ra như sau:
    Cho dãy X10 {12, 4, 8, 17,6, 5, 21, 33, 22, 20}
    Hãy kiểm tra X có thoả mãn điều kiện là một đống không? Nếu không, hãy sắp xếp X sao cho là một đống.

    Cách làm:
    1. Kiểm tra X có thoả mãn điều kiện là một đống không?
    Ta thấy với i = 1 thì Xi = X1 = 12, X2i = X2 = 4, X2i+1 = X3 = 8 thoả mãn tính chất Xi ≥ X2i và Xi ≥ X2i

    Với i = 2 thì Xi = X2 = 4, X2i = X4 = 17, X2i+1 = X5 = 6 không thoả mãn tính chất Xi ≥ X2i và Xi ≥ X2i

    Từ 2 trường hợp trên, kết luận X không phải là đống.

    2. Sắp xếp X sao cho thành đống.

    (Thực hiện vẽ đống theo từng công đoạn đổi chỗ Xi và các con của nó). Lưu ý Xi mà nhỏ hơn cả 2 con của nó, thì vẽ đổi chỗ cho con trái trước, sau đó mới đổi chỗ cho con phải. Vẽ theo thứ tự sau:
    - Đổi chỗ ở nhánh bên phải nhất hàng cuối cùng → Đổi chỗ sang bên trái -→ hàng kế tương tự.

    Thuật toán và giả mã:
    Có nhiều sách viết, nhưng thống nhất theo cách viết thầy dạy, đừng có mà í ới theo các sách viết khác để nhầm lẫn là không có điểm đâu nha.

    Thủ tục con vun đống:
    Proc VĐ1(k: Chỉ số gốc, Temp: Giá trị chờ, m: chỉ số nút cuối cùng)
    1. Stop = false;
    2. While 2k < m & !Stop
    a. j: = 2k
    if ((j+1) ≤ m) & (Xj ≤ Xj+1) then j := j + 1;
    b. if Xj > Temp then {Xk : = Xj ; k = j}
    else Stop := true;
    3. Xk: = Temp


    Thủ tục tạo đống (sẽ gọi thủ tục vun đống nhiều lần đến khi đạt được mục đích thì thôi):
    Proc Tạo đống;
    n:=/X/
    1. for i:= INT(n/2) downto 1 VĐ1(i, Xi, n)
    2. For m := n - 1 downto 1
    Temp := Xm+1;
    VĐ1(1, Temp, m)
    Xm+1 = Temp;
    3. Output X


    Anh Admin xem lại Tạo đống nhé, thuật toán này thày viết nhưng chưa đúng đâu
    Em Son
    Giải thuật của thầy còn thiếu (em đọc sách thầy Lôi em thấy thế), sách thầy Lôi dễ hiểu hơn nhiều.



    Được sửa bởi Admin ngày Mon Jul 11, 2011 10:46 am; sửa lần 4. (Reason for editing : Theo bài học và lời dặn của thầy)


    ================
    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: [Hướng dẫn]Sắp xếp vun đống on Tue May 31, 2011 1:10 pm

    Tuan Diep


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    các bạn các bác ơi!
    tôi thấy môn CSDLGT chúng ta cần giải quyết triệt để hết các bài kiểm tra thầy tĩnh cho, để cho anh em học đuối như chung tôi nghiên cứu ko thì nguy mất. vì những bài đó khó, mà thầy ko chữa.
    Muốn tham gia diễn đàn nhưng chỉ biết đọc thôi chứ chẳng biết gì khác để gửi trao đổi. Mhúc cả lớp thành công!


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

    3 Phần mô phỏng vun đống on Fri Jun 03, 2011 7:30 pm

    ptiep


    Thành viên ít chịu khó
    Thành viên ít chịu khó


    Mô phỏng thuật toán sắp xếp vun đống.

    Admin: Phần này đã được Embed. Thanks. Đã nhấn thanks rồi, thanks thêm cái nữa nha. Màu nền này nghĩa là bài đã được đánh giá rất cao đó.



    Được sửa bởi Admin ngày Sat Jun 04, 2011 3:39 am; sửa lần 1. (Reason for editing : Nhúng vào bài viết)


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

    4 Re: [Hướng dẫn]Sắp xếp vun đống on Fri Jun 03, 2011 8:33 pm

    Admin


    Quản trị viên
    Quản trị viên
    Bản quyền mô phỏng của Khoa học Máy tính
    Computer Science
    Faculty of Information Technology - Hanoi National University of Education

    Nếu bạn không thấy mô phỏng hiện ra, nghĩa là máy bạn chưa cài java. Bạn phải thực hiện cài java vào máy bằng cách nhấn vào đường link sau: [You must be registered and logged in to see this link.]
    Sau đó cứ việc nháy OK để java cài vào máy.

    Tất cả các trang mô phỏng cơ sở, sẽ được viết theo dạng java cho nó nhẹ, nên bạn hãy cài java để xem nhé!

    Hiện tại tôi có thể hướng dẫn các bạn mô phỏng bằng Flash nhưng không có thời gian nhiều. Chắc là nếu thi đỗ được, chúng ta sẽ làm lại toàn bộ mô phỏng dạng này bằng flash cho đẹp.

    Đường link tham khảo các bài viết bằng sử dụng Flash căn bản (nếu không hiện tiếng Việt, xin chọn từ thựcđơn View, codepage ISO8859-1 (cái này tôi viết lâu rồi, từ hồi chưa chuẩn hoá unicode):
    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]

    Nháy tham khảo: Code mẫu lập trình flash
    Giáo trình sử dụng: Giáo trình lập trình Flash



    Được sửa bởi Admin ngày Sat Jun 04, 2011 7:58 pm; sửa lần 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

    5 Re: [Hướng dẫn]Sắp xếp vun đống on Fri Jun 03, 2011 11:01 pm

    ptiep


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Cảm ơn Admin đã quan tâm. Mình rất muốn post bài nhưng trình độ còn hạn chế nên chưa có nhiều bài để tham gia. Mình chỉ nhắc nhở các bạn khi làm bài CTDL phải có dòng Output kết quả vì theo đáp án nó chiếm 0.25 điểm đó.


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

    6 Bình luận về sắp xếp vun đống on Tue Jun 07, 2011 8:33 am

    Admin


    Quản trị viên
    Quản trị viên
    Bình luận thủ tục con vun đống:
    Thủ tục này nhằm biến các phần tử từ vị trí k đến vị trí n thành đống.
    Các phần tử trước k và sau m không được thực hiện.
    Proc VĐ1(k: Chỉ số gốc, Temp: Giá trị chờ, m: chỉ số nút cuối cùng)
    1. Stop = false;// → Đặt một cờ nhằm làm chìa khoá để thoát khỏi vòng lặp bất cứ lúc nào
    2. While 2k ≤ m & !Stop // → Chừng nào mà nút cha vẫn nằm trong khoảng cần xét và cờ cho phép thực hiện
    a. j: = 2k // → Đặt biến j để thuận tiện truy cập nút con
    if ((j+1) ≤ m) & (Xj << = Xj+1) then j:= j+1;
    // → Nếu con phải lớn hơn con trái, thì chuyển sang con phải, đương nhiên không thoả mãn thì ngầm định con trái rồi.
    b. if Xj > Temp then {Xk : = Xj ; k=j} // → Nếu con bằng với giá trị chờ, thì gán giá trị nút cha bằng giá trị của nút con
    // → đồng thời chuyển xuống cấp thấp hơn, nút cha chính là nút con vừa xét
    else Stop := true; // → Trường hợp nút con mà không lớn hơn nút cha
    3. Xk: = Temp // → Gán nút cha hiện tại bằng giá trị chờ

    Có điều gì đó có vẻ không ổn ở thủ tục này. Tại sao ở bước 2b lại không đổi chỗ giá trị nút cha Xk và nút con Xj nhỉ? Mà lại chỉ có gán giá trị của nút con cho nút cha. Có nghĩa là sau phép gán này, giá trị của nút con vẫn như cũ. Còn giá trị của nút cha bị đè bởi giá trị của nút con đưa vào. Giá trị này bị mất hoàn toàn, không thể khôi phục được vì mình có lưu nó vào chỗ nào đâu?

    Ta có dám sửa lại thuật toán của thầy đưa ra cho chuẩn không?
    Thôi thì cứ mạo muội xin phép thầy sửa lại cho nó tròn trịa. Bọn em không dám nói là cách của thày sai, mà chỉ dám phát biểu rằng cách của thầy còn thiếu một chút gì đó, có lẽ thầy quên không đưa vào. Ta đưa vào thế nào nhỉ?

    Cảm giác như khi thầy viết dòng lệnh b. if Xj > Temp then {Xk : = Xj ; k=j} không phải là ý gán giá trị của nút con cho nút cha, mà là chuyển vị trí cần xét bắt đầu từ nút cha, sang vị trí cần xét bắt đầu từ nút con của nó. → Mà cũng cảm giác tiếp như là đống đã vun rồi ý. Thủ tục nếu là chuyển vị trí giống như tìm chỗ là một nút trong cây để đưa giá trị Temp vào. Thế nhưng nếu tìm chỗ để đưa giá trị temp vào thì giá trị trước khi đưa vào của nút đó phải để ở đâu?


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

    7 Re: [Hướng dẫn]Sắp xếp vun đống on Tue Jun 07, 2011 9:37 am

    Admin


    Quản trị viên
    Quản trị viên
    Tôi thì cũng dốt về lập trình giả mã lắm, do quen viết bằng phần mềm thật rồi, nên cứ đưa tạm hướng giải quyết như thế này. Nếu các bạn thấy cần phải chỉnh chỗ nào thì ý kiến luôn để chúng ta có chương trình chuẩn. Tôi viết theo đúng kiểu của thầy:

    Proc VĐ1(k: Chỉ số ban đầu, X: Dãy, m: chỉ số nút cần dừng lại)// Ở đây chỉ số m là chỉ số để chặn để không vun những giá trị có chỉ số sau m → nhằm sử dụng cho thuật toán sắp xếp.
    1. Stop = false;// → Đặt một cờ nhằm làm chìa khoá để thoát khỏi vòng lặp bất cứ lúc nào (Giữ nguyên)
    2. While 2k ≤ m & !Stop // → Chừng nào mà nút cha vẫn nằm trong khoảng cần xét và cờ cho phép thực hiện (Giữ nguyên)
    a. j: = 2k // → Đặt biến j để thuận tiện truy cập nút con (Giữ nguyên)
    if ((j+1) ≤ m) & (Xj << = Xj+1) then j:= j+1;
    // → Nếu con phải lớn hơn con trái, thì chuyển sang con phải, đương nhiên không thoả mãn thì ngầm định con trái rồi. (Giữ nguyên)
    b. if Xj > Xk then
                        Đổi (Xk : = Xj) ;
                        k=j // → Nếu con bằng với giá trị chờ, thì gán giá trị nút cha bằng giá trị của nút con
    // → đồng thời chuyển xuống cấp thấp hơn, nút cha chính là nút con vừa xét
    else Stop := true; // → Trường hợp nút con mà không lớn hơn nút cha
    3. End.

    Phải viết riêng thủ tục tạo đống:
    Bất cứ một dãy nào, đều có thể dùng thủ tục này để tạo thành đống:

    Proc Tạo Đống (X: Dãy, m: Chỉ số nút cần dừng lại)
    1. i := Int(m/2)// Lấy vị trí bắt đầu vun là nút cha cuối cùng.
    2.while i > 0 // Vun lùi dần len đến gốc
                        VĐ1( i, X, m);//Thực hiện thủ tục vun
                        i := i - 1;
    End.


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

    8 Re: [Hướng dẫn]Sắp xếp vun đống on Tue Jun 07, 2011 9:58 am

    Admin


    Quản trị viên
    Quản trị viên
    Bây giờ chúng ta sẽ viết lại thủ tục sắp xếp vun đống của thầy cho thật chuẩn:
    Theo lời giảng của thầy là thầy cho giá trị gốc của đống xuống dưới cùng của dãy. Đưa giá trị mới vào đúng vị trí gốc. Nghĩa là, đống mới này sẽ được thêm 1 phần tử và mục đích là sẽ vun đống lại các phần tử từ đầu dãy đến phần tử cuối dãy cũ (chừa cái phần tử từ gốc đưa xuống ra). Ở vòng tiếp theo, mỗi vòng ta phải chừa thêm 1 phần tử. Vòng lặp thu hẹp đến khi hết các phần tử cần vun đống.

    Proc Sắp xếp;
    1. m:=/X/;
    2. Tạo đống (X, m);
    3. While m > 0 do
                        a. Đổi chỗ (X[m]; X[1]);// Đổi chỗ gốc và phần tử cuối.
                        b. m-- //Giảm bớt số phần tử đã đưa xuống
                        c. VĐ1(1, X, m); //Vun đống và chừa ra số các phần tử bị hạ xuống.
    4. Output X.


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

    9 Re: [Hướng dẫn]Sắp xếp vun đống on Wed Jun 08, 2011 6:10 am

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    Procedure VĐ1(i: byte; key: integer; m: byte);
    {- sx trên mảng A[1...n]; key: giá trị khoá để so sánh; m: chỉ số của nút}
    var: k,j: integer; Stop: boolean;
    1) {gán k vào giá trị của Root}
    a) stop:=false;
    b) k: = i;
    2) WHILE (2*k ≤ m) & !stop DO
              a) j := 2*k;
              b)IF (j < m) & ( Xj < Xj+1) THEN j := j + 1;
              c)IF key < Xj THEN Xk := Xj; k := j;
                        ELSE Xk := key;
    3) End.

    PROC Heap_Sort(n: byte);
    var max, i, m: nteger;
    1) FOR i: = n/2 DOWNTO 1 DO VĐ1(i, xi, n);
    2) FOR m := n - 1 DOWNTO 1 DO
              a) max: = X[1];
              b) VĐ1(1, max, m);
              c) m := max;
    3) End.


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

    10 Re: [Hướng dẫn]Sắp xếp vun đống on Mon Jul 30, 2012 5:21 pm

    dacminhm


    Thành viên cao cấp
    Thành viên cao cấp
    Không biết khóa K23 học thế nào nhưng trong khóa K24 thì thuật toán của thày như sau (không biết có chép sai không? vì thày toàn viết từ giữa viết ra, mỗi đoạn lại viết một nơi [You must be registered and logged in to see this image.]
    Proce. Heap (k: chỉ số ô trống; temp: giá trị; m:chỉ số chặn trên)
              FOR m:= n downto 2
              temp:= xm ;
              xm:= x1;
              Heap(1; temp; m – 1;);
              WHILE (2k ≤ m) & !Stop
                        j:=2k;
                        if ((j + 1) ≤ m) & (xj < xj+1) THEN j:=j +1;
                        if (xj > temp) { xk := xj ; k:=j;}
                        ELSE stop:=true;
              xk := temp;
    Output X;
    Thuật toán trên khá giống thuật toán của Admin nhỉ? Chập 2 thành một mà. Nhưng đây mới chỉ là giải quyết bài toán cho mảng và sắp xếp thành một đống theo kiểu "giảm" nghĩa là có nút gốc lớn nhất, các nút cha lớn hơn hoặc bằng với nút con.
    Tuy nhiên trong vở có chép (chính xác là "Vẽ" theo đúng lời của thày) thì sau khi thành 1 đống như trên. Còn có mấy hình vẽ cho kết quả cuối cùng là đống sắp xếp theo kiểu "tăng dần" nghĩa là có nút gốc nhỏ nhất, các nút cha nhỏ hơn nút con.
    Thuật toán (phỏng đoán theo hình) là: đưa phần tử lớn nhất xuống lá cuối cùng, đưa nút con lên, tiếp tục".
    Xin hỏi thuật toán như vậy viết thế nào ? liệu nó vẫn là thuật toán bên trên hay không?



    Được sửa bởi dacminhm ngày Mon Jul 30, 2012 5:26 pm; sửa lần 2. (Reason for editing : Sửa lại code)


    ================
    Nothing to say!

    11 Ý của mình, các bạn xem thế nào nhé on Sun Feb 24, 2013 9:56 pm

    ngochant0801


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Theo mình thì thuật toán của thầy vẫn là chuẩn. Bởi vì ngay từ đầu temp:=x(k)
    bước b là chúng ta đi so sánh con trái và con phải với temp.

    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 | Sosblogs.com