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

    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.

    https://khmt.123.st

    sonld1984

    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

    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)

    Admin

    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).

    https://khmt.123.st

    5[Lời giải]Tìm phần tử lớn thứ 2 bằng đệ quy Empty Bài giải Mon May 23, 2011 9:30 am

    sonld1984

    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[Lời giải]Tìm phần tử lớn thứ 2 bằng đệ quy Empty Bỏ một dòng FOR Mon May 23, 2011 9:44 am

    HaiYen

    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

    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

    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

    sonld1984

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

    10[Lời giải]Tìm phần tử lớn thứ 2 bằng đệ quy Empty Bác Phương viết thế sai rồi Tue May 24, 2011 7:53 am

    sonld1984

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

    hungbeo_fm2008

    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.

    ptiep

    avatar
    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

    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.

    https://khmt.123.st

    LeVanDat

    avatar
    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

    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

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

    Admin

    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






    https://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 https://khmt.123.st

    Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất