Đạ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
    Cho dãy X có n phần tử là các số nguyên. Xk gọi là lớn thứ 2 trong dãy nếu:
    [You must be registered and logged in to see this image.]

    Nếu J = {J : Xj = T} thì

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



    Được sửa bởi Admin ngày Sun Jul 03, 2011 10:04 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

    sonld1984


    Chuyên viên
    Chuyên viên
    Tôi đưa ra phương án thế này, các đồng chí cho ý kiến
    * Ý tưởng: 2 vòng For nhưng không lồng nhau
    1. Vòng For 1: Tìm phần tử lớn nhất của dãy
    2. Vòng For 2: Tìm phần tử lớn nhất của dãy nhưng khác phần tử tìm được ở vòng for 1
    Như vậy tôi vẫn không hiểu độ phức tạp có phải là O(n) không?


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

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Tôi cũng có ý tưởng như đ/c Son. Nhưng theo tôi là phải 3 vòng chứ không phải 2:

    - Vòng 1: tìm Max_1.(giá trị lớn nhất)

    - Vòng 2: tìm giá trị bất kì trong dãy khác Max_1

    i:=1;
    While Ai = Max_1 do i:=i+1;
    Max_2:=Ai;


    - Vòng 3: If (Aj <> Max_1) và (Aj > Max_2) thì Max_2:= Aj

    Vòng 1 và 2 có độ phức tạp là n, vòng 3 có hai phép so sánh nên có độ phức tạp là 2n. Vậy 3 vòng là 4n ---> Độ phức tạp của thuật toán là O(n)


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

    Admin


    Quản trị viên
    Quản trị viên
    Tôi nghĩ chỉ cần 1 vòng. Ta nên đặt 1 biến Trước_Max. Trước khi gán biến Max, ta cho nó so luôn với Trước_Max (giống như với Max và bỏ qua nếu nó không đáp ứng). Độ phức tạp O(n).


    ================
    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 Bài giải on Mon May 23, 2011 9:30 am

    sonld1984


    Chuyên viên
    Chuyên viên

    * Thuật toán:
    -- Giả thiết dãy chỉ gồm các số tự nhiên
    Procedure PhanTuLonThu2(M: Dãy số);

    Var Max1: integer;

    Var Max2: integer;

    Max1:=-1;

    Max2:=-1;



    For i=1 to |M| do





    For i = 1 to |M| do





    if Mi > Max1





    Max1 := Mi;







    if Mi > Max2 And Mi < Max1







    Max2:=Mi;

    if Max2 = -1

    Output("Không có phần tử lớn thứ 2")

    else

    Output(Max2);





    -- Đây là thủ tục rất tường minh các bác xem góp ý
    -- Có thể dùng 1,3 vòng For nhưng tôi nghĩ một vòng For thì số phép tính vẫn
    như vậy vì thực chất mình chỉ tách ra và gộp vào thôi.



    Được sửa bởi Admin ngày Tue May 24, 2011 12:17 am; sửa lần 1. (Reason for editing : Sửa lại cấu trúc cho dễ nhìn)

    6 Bỏ một dòng FOR on Mon May 23, 2011 9:44 am

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp

    Procedure PhanTuLonThu2(M: Dãy số);

    Var Max1: integer;

    Var Max2: integer;

    Max1:=-1;

    Max2:=-1;



    For i=1 to |M| do





    if Mi > Max1





    Max1 := Mi;







    if Mi > Max2 And Mi < Max1







    Max2:=Mi;

    if Max2 = -1

    Output("Không có phần tử lớn thứ 2")

    else

    Output(Max2);


    Bỏ một dòng FOR



    Được sửa bởi Admin ngày Tue May 24, 2011 12:03 am; sửa lần 1. (Reason for editing : Trình bày theo cấu trúc cho dễ nhìn)

    sonld1984


    Chuyên viên
    Chuyên viên
    Cái thủ tục của chú Yên sai rồi
    Chú thử với dãy: 1,2,5 là thấy ngay

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    - Son xem lại bài đi nhé, nếu hai vòng for lồng vào nhau như Son viết thì thuật toán sẽ có độ phức tạp là O(n2) đấy.

    - Mình thắc mắc là đặt max1, 2 = -1 lúc ban đầu như thế liệu có ổn không nhỉ?

    - Nếu gán được max1,2 = -1 thì mình có thể dùng 1 vòng for.

    For i:= 1 to |M|
    ..... If Ai>=max1 then max1:=Ai
    Else If Ai >= max2 then max2:=Ai


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

    sonld1984


    Chuyên viên
    Chuyên viên
    Bác Cường sửa sai bài em rồi


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

    10 Bác Phương viết thế sai rồi on Tue May 24, 2011 7:53 am

    sonld1984


    Chuyên viên
    Chuyên viên
    Bác thử chuỗi 1,2,3 là thấy ngay

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    sonld1984 đã viết:Bác Cường sửa sai bài em rồi
    Chuẩn, tối qua anh vào thì vẫn còn nguyên bài ban đầu của chú. nếu anh Cường viết hai vòng For lồng vào nhau như thế thì độ phức tạp là n2 chứ ko phải là n nữa.
    Phải tách ra thành 2 vòng for riêng biệt thì độ phức tạp mới là n.


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

    ptiep


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Thuật toán tìm phần tử lớn thứ 2 trong dãy
    Các bạn tham khảo xem thuật toán này thế nào

    Procedure Phantulonthu2(X: dãy số)

    max1 = 1
    max2 = 2
    If x(max1) < x(max2) Then
    max2 = 1
    max1 = 2
    End If
    For i = 3 To n
    If x(i) > x(max1) Then
    max2 = max1
    max1 = i
    ElseIf (x(i) < x(max1)) And (x(i) > x(max2)) Then
    max2 = i
    End If

    Output max2;

    Đ/c Tiệp xem lại dãy (3, 3, 3, 3, 1) xem thế nào nhé.

    Admin


    Quản trị viên
    Quản trị viên
    Đúng là đề bài tìm phần tử lớn thứ 2 trong dãy, nếu mình tìm giá trị lớn thứ 2 trong dãy thì không hiểu đề bài và 0 điểm. Mình phải chỉ ra trị số n, chứ không phải giá trị M(n).

    Có thể do Mr.Son không đánh có cấu trúc, nên tôi nghĩ sai cấu trúc nên mới sửa lại cho dễ nhìn. Cấu trúc thế nào thì đề nghị tác giả copy vào Word dán vào table (như hướng dẫn) cho chuẩn.


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

    LeVanDat


    Chuyên viên
    Chuyên viên
    Bài của đ/c Tiệp không khẳng định được có phần tử thứ 2 hay không, nếu không có thì thế nào?

    sonld1984


    Chuyên viên
    Chuyên viên
    public static int VTMax1 = -1;
    public static int VTMax2 = -1;
    public static void PTLT2(int[] Arr, int n)
    {
    int GTMax1 = -1;
    int GTMax2 = -1;
    if (VTMax1 == -1) GTMax1 = -1;
    else GTMax1 = Arr[VTMax1];
    if (VTMax2 == -1) GTMax2 = -1;
    else GTMax2 = Arr[VTMax2];
    if (n >= 0)
    {
    if (Arr[n] > GTMax1)
    {
    VTMax2 = VTMax1;
    VTMax1 = n;
    }
    else
    {
    if (Arr[n] > GTMax2 && Arr[n] < GTMax1)
    {
    VTMax2 = n;
    }
    }
    PTLT2(Arr, n - 1);
    }
    }
    Output VTMax2;


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

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    Chà, đệ quy bằng C# à. [You must be registered and logged in to see this image.]


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

    Admin


    Quản trị viên
    Quản trị viên
    Ý tưởng:


    Truyền vào 3 chỉ số:


    N - số phần tử phải xét


    a- chỉ số chỉ ra để xét phần tử có giá trị Max, tức xét M(a)
    = Max


    b- chỉ số chỉ ra để xét phần tử
    có giá trị Max2, tức xét M(b) = Max2


    Viết


    Procedure Tim (n, a, b: chỉ số)

    IF n=0 then Output b;



    ELSE IF M(n) > M(a) THEN

    Tim (n-1, n, b)





    ELSE IF M(n) > M(b)

    THEN Tim (n-1, a, n)







    ELSE Tim (n-1, a, b)

    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

    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 | Khoa học | Đại học | © PunBB | Free forum support | Liên hệ | Report an abuse | www.sosblogs.com