Đạ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
    Đề thi tuyển sinh cao học năm 2011 CTDL & GT
    HVKTQS

    Câu I.
    1. Các phần tử khác không của ma trận thưa A kích thước m x n được lưu trong danh sách liên kết đơn có cấu trúc như sau:
    Matric = ^List;
    List = Record
              value: Integer;
              index: Integer;
              next: Matrix;
    End;
    trong đó
    value lưu giá trị của phần tử khác không A[i, j];
    index lưu chỉ số (i - 1) * n + j
    Hãy viết giải thuật tính ma trận chuyển vị B = AT, biết rằng ma trận B cũng được lưu trữ theo cấu trúc trên.
    2. Dùng bảng minh họa hình ảnh của ngăn xếp S được sử dụng để tính giá trị của biểu thức hậu tố sau:
    6 1 - 7 1 - * 11 1 + 3 / 2 + /

    Câu II.
    1. Cho mảng K chứa n giá trị khóa K(1..n). Viết thủ tục chèn n giá trị khóa cảu mảng K đã cho vào cây tìm kiếm nhị phân.
    2. Cho văn bản T chỉ gồm các ký tự a, b, d, e, f, u, v, s với số lần xuất hiện như sau:
    Ký tự
    a
    s
    b
    d
    e
    f
    u
    v
    Số lần xuất hiện
    26
    29
    18
    21
    12
    10
    8
    6
    a. Xây dựng bộ mã Huffman tối ưu và vẽ cây nhị phân Huffman tương ứng.
    b Giả sử văn bản T đã được nén bằng bộ mã Huffman tối ưu, hãy cho biết số lượng bit của văn bản nén.

    Câu III.
    Cho đơn đồ thị G = (V, E) vô hướng, liên thông , có n đỉnh được đánh số từ 1 đến n, cho bởi danh sách kề như sau:
    DSK = Record
              m: Integer (Số cạnh liên thuộc)
              A: Array (1..m) of Integer (Mảng chứa tên các đỉnh)
    End
    DS (1..n) of DSK

    Trình bày thuật toán duyệt đồ thị G dựa trên phương pháp tìm kiếm theo chiều rộng và áp dụng thuật toán đó duyệt đồ thị sau:
    Đỉnh
    Danh sách đỉnh kề
    1
    2, 3, 4
    2
    1, 4
    3
    1, 4, 7
    4
    1, 2, 3, 5, 7
    5
    4, 6, 7
    6
    5, 7
    7
    3, 4, 5, 6
    Liệt kê các đỉnh theo thứ tự duyệt, giả thiết xuất phát từ đỉnh 2.

    Câu IV. Cho dãy X có n số nguyên X (x1, x2,..., xn) trình bày thuật toán sắp xếp chèn để sắp xếp dãy X thành dãy không tăng. Tính số phép toán so sánh phải thực hiện trong trường hợp xấu nhất, tốt nhất. Viết chi tiết các bước khi áp dụng thuật toán trên cho dãy sau 12, 4, 6, 2, 8, 11, 7, 22, 9, 5.

    Câu V. Cho hàm số f(x) xác định , liên tục và đơn điệu trên đoạn (a, b). Giả sử c là một giá trị thỏa mãn f(a) < c < f(b). Xây dựng thuật toán giải phương trình f(x) = c với sai số epsilon.

    https://khmt.123.st

    gacongnghiep

    gacongnghiep
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Câu V. Cho hàm số f(x) xác định , liên tục và đơn điệu
    trên đoạn (a, b). Giả sử c là một giá trị thỏa mãn f(a) < c <
    f(b). Xây dựng thuật toán giải phương trình f(x) = c với sai số epsilon.
    Giải:
    Ý tưởng:
    + f(x) liên tục và đơn điệu (a,b) -> Có thể hiểu nếu có bất kì 1 giá trị x thỏa mãn a f(a) + Giải thuật viết dạng giả mã như sau:
    Proc Tìm_X()
    Ok=0;
    WHILE (!OK) do
    x=(a+b)/2
    if (F(x-e)<=c) & (c<=F(x+e)) THEN Ok=1
    elseif
    (F(x-e)>=c) THEN b=x;
    ELSE a=x;
    Output x;

    Tongmanhcuong

    avatar
    Quản trị viên
    Quản trị viên
    Bạn này chẳng hiểu gì cả. Viết lung tung quá.

    H.Q.Huy

    avatar
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Đúng là gà công nghiệp..sặc..sặc... (CuoiBo)

    HaiYen

    HaiYen
    Thành viên cao cấp
    Thành viên cao cấp
    Theo em có thể làm bài này như sau:
    PROC TIM (a, b: real)
    IF /a-b/ < epsilon THEN write (a+b)/2
    ELSE
              REPEAT
                        m = (a+b)/2
                        IF (f(a) - c)(f(m) - c) < 0 THEN b = m;
                        ELSE a = m;
              UNTIL /a-b/ ≤ Epsilon
    write m;
    Nếu ai công nhận em làm đúng nhớ nhấn Thank đó nha.

    Tongmanhcuong

    avatar
    Quản trị viên
    Quản trị viên
    Chào em Hải Yến!

    Rất hoan nghênh em đưa ra lời giải. Nhưng theo anh lời giải của em nhầm rồi.

    Theo anh em nhầm ở chỗ If (a-b).....

    Em xem lại nhé. Rất mong gặp được em để thảo luận.

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Sao không ai đưa ra lời giải hoặc gợi ý vậy? Thật trái ngược so với topic TRR
    Mình xin ý kiến về bài 1, mong mọi người bình luận để chỉ ra cái sai chứ đừng nói chung chung không thể giúp ích gì cho người cần đọc cả. Xin cám ơn.
    ___________________________________________________________________
    Bài 1. Các phần tử khác không của ma trận thưa A kích thước m x n được lưu trong danh sách liên kết đơn có cấu trúc như sau:
    Matric = ^List;
    List = Record
    value: Integer;
    index: Integer;
    next: Matrix;
    End;
    trong đó
    value lưu giá trị của phần tử khác không A[i, j];
    index lưu chỉ số (i - 1) * n + j
    Hãy viết giải thuật tính ma trận chuyển vị B = AT, biết rằng ma trận B cũng được lưu trữ theo cấu trúc trên.
    ___________________________________________________________________
    Thực sự thì thày Tĩnh không dạy về thuật toán ma trận chuyển vị thì phải nên mình mới phỏng đoán như sau:
    Code:

    Proc.  Chuyenvi (A(m,n): Matric; m,n: integer)
        VAR B [n,m] = empty;
        FOR j:=0 to (m-1)
          FOR i:=0 to (n-1)
              B[j,i] = A [i.j] ^.List;
              B[j,i].index = (j-1)*m + i;
              B:=B^.next;
    Output (B[n,m]);

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Câu 1. b
    Dùng bảng minh họa hình ảnh của ngăn xếp S được sử dụng để tính giá trị của biểu thức hậu tố sau:
    6 1 - 7 1 - * 11 1 + 3 / 2 + /
    ******************************************
    Mi = {6; 1; -; 7; 1; -; *; 11; 1; +; 3; /; 2; +; / ;}
    Duyệt Ngăn xếp S
    6
    6
    1
    6, 1
    -
    5
    7
    5, 7
    1
    5, 7, 1
    -
    5, 6
    *
    30
    11
    30,11
    1
    30, 11, 1
    +
    30, 12
    3
    30, 12, 3
    /
    30, 4
    2
    30, 4, 2
    +
    30, 6
    /
    5
    Output {5} => Giá trị của biểu thức hậu tố M là 5

    Tongmanhcuong

    avatar
    Quản trị viên
    Quản trị viên
    Có người giả mạo Tống Mạnh Cường. Đợt này mình bận không lên diễn đàn và post bài. Không hiểu ai dùng username của mình để post bài nhỉ (Chắc là ban quản trị à).

    Gửi các bạn khóa K24 CNTT thân mến!!!!

    Nếu ai có nhu cầu muốn bổ sung kiến thức cho chắc hoặc hổng chỗ nào đó hoặc học yếu,... thì có thể liên hệ với mình để bồi dưỡng, nếu muốn được 5 điểm/môn chắc không khó. Liên hệ: [You must be registered and logged in to see this link.] hoặc 0983120890.

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Câu II.
    1. Cho mảng K chứa n giá trị khóa K(1..n). Viết thủ tục chèn n giá trị khóa cảu mảng K đã cho vào cây tìm kiếm nhị phân.
    **************************************************************
    K(i) | i = 1,2,...n
    Thủ tục:
    -
    Duyệt mảng K từ đầu đến cuối.
    - So sánh với giá trị đầu tiên của cây tìm kiếm nhị phân T.
    - Nếu giá trị k(i) lớn hơn giá trị nút trên cây T thì tiếp tục so sánh với nút con phải.
    - Nếu giá trị k(i) nhỏ hơn giá trị nút trên cây T thì tiếp tục so sánh với nút con trái.
    - Nếu không có nút con của T thì tạo nút con mới với giá trị là k(i).
    - Nếu giá trị k(i) bằng giá trị nút con của T, tiếp tục duyệt với k (i +1) và quay lại bước 2.
    Thuật toán:
    Code:

    Proc Chen_CNP (K: mảng, T: DS)
        FOR i:=1 to n
                WHILE ( T! = Nil)
                    if  ( k(i) = T)
                          return i = i + 1;
                    ELSE {
                            if ( k(i) > T)      T:= T^.Right;
                            ELSE                  T:= T^.Left;
                    T:= T^.next;
                Tao_nut_moi (T^.DS) = k(i);
    Ouput (T);

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Câu II.2. Cho văn bản T chỉ gồm các ký tự a, b, d, e, f, u, v, s với số lần xuất hiện như sau:

    Ký tự

    a

    s

    b

    d

    e

    f

    u

    v

    Số lần xuất hiện

    26

    29

    18

    21

    12

    10

    8

    6

    a. Xây dựng bộ mã Huffman tối ưu và vẽ cây nhị phân Huffman tương ứng.
    b Giả sử văn bản T đã được nén bằng bộ mã Huffman tối ưu, hãy cho biết số lượng bit của văn bản nén.

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

    Từ cây Huffman trên ta có thể tính được:



    Ký tự


    a


    s


    b


    d


    e


    f


    u


    v


    Mã hóa


    11


    10


    010


    001


    0000


    0001


    0110


    0111

    Số bit mã hóa văn bản là:

    26.2 + 29.3 +18.3 +21.3 + 12.4+10.4+8.4+6.4 = 400

    Hiệu suất mã hóa: 400 /8 *( 26+29+18+21+12+10+8+6)= 0.385

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Câu III.Cho đơn đồ thị G = (V, E) vô hướng, liên thông , có n đỉnh được đánh số từ 1 đến n, cho bởi danh sách kề như sau:
    DSK = Record
    m: Integer (Số cạnh liên thuộc)
    A: Array (1..m) of Integer (Mảng chứa tên các đỉnh)
    End
    DS (1..n) of DSK
    Trình bày thuật toán duyệt đồ thị G dựa trên phương pháp tìm kiếm theo chiều rộng
    ********************************************************************
    Code:

    Proc.  Duyet_CR (G: DS; A: DSK; m:integer)
                HĐ = empty;
                boolean dx(int x);
                FOR i:= 1 to n  DO  dx(V(i)) =0;
                FOR i:= 1 to n
                      V(i) = v;  dx(v) = 1;  write(v);  enqueue(v, HĐ);
                      WHILE (HĐ! = empty)
                              a:= front (HĐ); Dequeue(a, HĐ);
                              x = A(a) ^.DSK;
                              FOR all  x of A(a)
                                        if (dx(x)=0) THEN {dx(x) = 1; write(x);  enqueue(x,HĐ);}

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Câu III. (tiếp) Trình bày thuật toán duyệt đồ thị G dựa trên phương pháp tìm kiếm theo chiều rộng và áp dụng thuật toán đó duyệt đồ thị sau:
    Đỉnh
    Danh sách đỉnh kề
    1
    2, 3, 4
    2
    1, 4
    3
    1, 4, 7
    4
    1, 2, 3, 5, 7
    5
    4, 6, 7
    6
    5, 7
    7
    3, 4, 5, 6
    Liệt kê các đỉnh theo thứ tự duyệt, giả thiết xuất phát từ đỉnh 2.
    ***************************************************************
    Duyệt theo thuật toán, bắt đầu xuất phát từ đỉnh v = 2
    Khởi tạo hằng đợi HD = rỗng.
    STT
    Đỉnh duyệt
    Danh sách kề
    Hằng đợi
    Kết quả ghi
    0
    -
    -
    2
    2
    1
    2
    1, 4
    2,1, 4
    2,4,1
    2
    4
    1, 2, 3, 5, 7
    1, 2, 3, 5, 7
    2, 4, 1, 7, 5, 3
    3
    7
    3, 4, 5, 6
    3, 4, 5, 6
    2, 4, 1, 7, 5, 3, 6
    4
    6
    5, 7
    5, 7
    2, 4, 1, 7, 5, 3, 6
    5
    5
    4, 6, 7
    4, 6, 7
    2, 4, 1, 7, 5, 3, 6
    6
    3
    1, 4, 7
    1, 4, 7
    2, 4, 1, 7, 5, 3, 6
    7
    1
    2, 3, 4
    2, 3, 4
    2, 4, 1, 7, 5, 3, 6
    8
    -
    -
    -
    2, 4, 1, 7, 5, 3, 6

    Kết quả thu được: 2, 4, 1, 7, 5, 3, 6
    ****************************************************
    Bình luậnt 1 tý: tôi giải phần này tuân theo thuật toán đưa ra bên trên nên đến cuối cùng hằng đợi bằng rỗng kết thúc vòng lặp WHILE. => trong hằng đợi ở bước cuối cùng = rỗng (Trong topic hướng dẫn duyệt tay đồ thị của admin có bảo phải ghi ra hằng đợi, nhưng lúc này hằng đợi = rỗng thì không hiểu ghi ra thế nào?).
    - Trong đề bài không có nói thứ tự các đỉnh, và trong thuật toán cũng không có phần sắp xếp => tôi duyệt và đưa ra kết quả thế này không biết có bị cho là sai không nhỉ?

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Câu IV. Cho dãy X có n số nguyên X (x1, x2,..., xn)
    trình bày thuật toán sắp xếp chèn để sắp xếp dãy X thành dãy không
    tăng. Tính số phép toán so sánh phải thực hiện trong trường hợp xấu
    nhất, tốt nhất.

    *********************************************************************
    Code:

    Proce.  SXCHEN (X [int n])
                            int i; int tg; int j;
                    FOR i:= 2 to n {
                                            tg:= x[i];
                                            j := i - 1;
                                            WHILE (j >0) & ( x[j] < tg) do
                                                                    x[j+1] = x[j];
                                                                    j = j - 1;
                                                                    x[j+1] = tg;
              }
    Ouput (X);
    Số phép toán so sánh phải thực hiện: = S
    - Trường hợp tốt nhất: X là dãy không tăng: S = 1+ 2 + 3...+ n = n(n-1)/2
    - Trường hợp xấu nhất: X là dãy không giảm: S = 3*(1+2+3+...+n) = 3n(n-1)/2
    ************************************************************
    Bình luận tý: không hiểu tôi có hiểu sai không nhỉ? vì trong các trường hợp không phải là tốt nhất thì ta phải có thêm 3 bước so sánh bằng. ==> liệu hiểu đúng ko nhỉ?



    Được sửa bởi dacminhm ngày Fri Aug 03, 2012 1:53 pm; sửa lần 2. (Reason for editing : Nhầm lẫn)

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Câu IV. (tiếp)Viết chi tiết các bước khi áp dụng thuật toán trên cho
    dãy sau 12, 4, 6, 2, 8, 11, 7, 22, 9, 5.
    ****************************************************************************
    - Bước 0: nhập dãy X = {12; 4; 6; 2; 8; 11; 7; 22; 9; 5}
    - Bước 1: duyệt khi i = 2; tg = x(2) = 4; j = 1 ; bắt đầu vòng lặp WHILE; x(j) = 12; x(j) > tg => kết thúc vòng lặp WHILE. Hiện tại X = {12; 4; 6; 2; 8; 11; 7; 22; 9; 5}
    - Bước 2: duyệt khi i = 3; tg= x(3) = 6; j= 2; bắt đầu vòng lặp WHILE; x(j) = 4; x(j) < tg; đổi chỗ x(3) và x(2). Tiếp tục với j = j - 1 = 1, Kết thúc vòng lặp WHILE Hiện tại X = {12; 6; 4; 2; 8; 11; 7; 22; 9; 5}
    - Bước 3: duyệt khi i = 4; tg = x(4) = 2; j = 3; bắt đầu vòng lặp WHILE; x(j) = 4; x(j) > tg => kết thúc vòng lặp WHILE. Hiện tại X = {12; 6; 4; 2; 8; 11; 7; 22; 9; 5}
    - Bước 4: duyệt khi i = 5; tg = x(5) = 8; j = 4; bắt đầu vòng lặp WHILE; x(j) = x(4) = 2; x(j) < tg; đổi chỗ x(5) và x(4). Hiện tại X = {12; 6; 4; 8; 2; 11; 7; 22; 9; 5}
    - Bước 5: tiếp tục j = j -1 = 3; x(j) = x(3) = 4; x(j) < tg; đổi chỗ x(4) và x(3). Hiện tại X = {12; 6; 8; 4; 2; 11; 7; 22; 9; 5}
    - Bước 6: tiếp tục j = j -1 = 2; x(j) = x(2) = 6; x(j) < tg; đổi chỗ x(3) và x(2). Hiện tại X = {12; 8; 6; 4; 2; 11; 7; 22; 9; 5}
    - Bước 7: tiếp tục j = j -1 = 1; x(j) = x(1) = 12; x(j) > tg; kết thúc vòng lặp WHILE. Hiện tại X = {12; 8; 6; 4; 2; 11; 7; 22; 9; 5}
    - Bước 8: duyệt khi i = 6; tg = x(6) = 11; j = 5; bắt đầu vòng lặp WHILE; x(j) = x(5) = 2; x(j) < tg; đổi chỗ x(6) và x(5). Hiện tại X = {12; 8; 6; 4; 11; 2; 7; 22; 9; 5}
    - Bước 9: tiếp tục j = j -1 = 4; x(j) = x(4) = 4; x(j) < tg; đổi chỗ x(5) và x(4). Hiện tại X = {12;8; 6; 11; 4; 2; 7; 22; 9; 5}
    - Bước 10: tiếp tục j = j -1 = 3; x(j) = x(3) = 6; x(j) < tg; đổi chỗ x(4) và x(3). Hiện tại X = {12; 8; 11; 6; 4; 2; 7; 22; 9; 5}
    - Bước 11: tiếp tục j = j -1 = 2; x(j) = x(3) = 8; x(j) < tg; đổi chỗ x(3) và x(2). Hiện tại X = {12; 11; 8; 6; 4; 2; 7; 22; 9; 5}
    - Bước 12: tiếp tục j = j -1 = 1; x(j) = x(1) = 12; x(j) > tg; kết thúc vòng lặp WHILE. Hiện tại X = {12; 11; 8; 6; 4; 2; 7; 22; 9; 5}
    - Bước 13: duyệt khi i = 7; tg = x(7) = 7; j = 6; bắt đầu vòng lặp WHILE; x(j) = x(6) = 2; x(j) < tg; đổi chỗ x(7) và x(6). Hiện tại X = {12; 11; 8; 6; 4; 7; 2; 22; 9; 5}
    - Bước 14: tiếp tục j = j -1 = 5; x(j) = x(5) = 4; x(j) < tg; đổi chỗ x(6) và x(5). Hiện tại X = {12; 11; 8; 6; 7; 4; 2; 22; 9; 5}
    - Bước 15: tiếp tục j = j -1 = 4; x(j) = x(4) = 6; x(j) < tg; đổi chỗ x(5) và x(4). Hiện tại X = {12; 11; 8; 7; 6; 4; 2; 22; 9; 5}
    - Bước 16: tiếp tục j = j -1 = 3; x(j) = x(3) = 8; x(j) > tg; kết thúc vòng lặp WHILE. Hiện tại X = {12; 11; 8; 7; 6; 4; 2; 22; 9; 5}
    - Bước 17: duyệt khi i = 8; tg = x(8) = 22; j = 7; bắt đầu vòng lặp WHILE; x(j) = x(7) = 2; x(j) < tg; đổi chỗ x(8) và x(7). Hiện tại X = {12; 11; 8; 7; 6; 4; 22; 2; 9; 5}
    - Bước 18: tiếp tục j = j -1 = 6; x(j) = x(6) = 4; x(j) < tg; đổi chỗ x(7) và x(6). Hiện tại X = {12; 11; 8; 7; 6; 22; 4; 2; 9; 5}
    - Bước 19: tiếp tục j = j -1 = 5; x(j) = x(5) = 6; x(j) < tg; đổi chỗ x(6) và x(5). Hiện tại X = {12; 11; 8; 7; 22; 6; 4; 2; 9; 5}
    - Bước 20: tiếp tục j = j -1 = 4; x(j) = x(4) = 7; x(j) < tg; đổi chỗ x(5) và x(4). Hiện tại X = {12; 11; 8; 22; 7; 6; 4; 2; 9; 5}
    - Bước 21: tiếp tục j = j -1 = 3; x(j) = x(3) = 8; x(j) < tg; đổi chỗ x(4) và x(3). Hiện tại X = {12; 11; 22; 8; 7; 6; 4; 2; 9; 5}
    - Bước 22: tiếp tục j = j -1 = 2; x(j) = x(2) = 11; x(j) < tg; đổi chỗ x(3) và x(2). Hiện tại X = {12; 22; 11; 8; 7; 6; 4; 2; 9; 5}
    - Bước 23: tiếp tục j = j -1 = 1; x(j) = x(1) = 12; x(j) < tg; đổi chỗ x(2) và x(1). Hiện tại X = {22; 12; 11; 8; 7; 6; 4; 2; 9; 5}
    - Bước 24: tiếp tục j = j -1 = 0; Kết thúc vòng lặp WHILE. Hiện tại X = {22; 12; 11; 8; 7; 6; 4; 2; 9; 5}
    - Bước 25: duyệt khi i = 9; tg = x(9) = 9; j = 8; bắt đầu vòng lặp WHILE; x(j) = x(8) = 2; x(j) < tg; đổi chỗ x(9) và x(8). Hiện tại X = {22; 12; 11; 8; 7; 6; 4; 9; 2; 5}
    - Bước 26: tiếp tục j = j -1 = 7; x(j) = x(7) = 4; x(j) < tg; đổi chỗ x(8) và x(7). Hiện tại X = {22; 12; 11; 8; 7; 6; 9; 4; 2; 5}
    - Bước 27: tiếp tục j = j -1 = 6; x(j) = x(6) = 6; x(j) < tg; đổi chỗ x(7) và x(6). Hiện tại X = {22; 12; 11; 8; 7; 9; 6; 4; 2; 5}
    - Bước 28: tiếp tục j = j -1 = 5; x(j) = x(5) = 7; x(j) < tg; đổi chỗ x(6) và x(5). Hiện tại X = {22; 12; 11; 8; 9; 7; 6; 4; 2; 5}
    - Bước 29: tiếp tục j = j -1 = 4; x(j) = x(4) = 8; x(j) < tg; đổi chỗ x(5) và x(4). Hiện tại X = {22; 12; 11; 9; 8; 7; 6; 4; 2; 5}
    - Bước 30: tiếp tục j = j -1 = 3; x(j) = x(3) = 11; x(j) > tg; Kết thúc vòng lặp WHILE. Hiện tại X = {22; 12; 11; 9; 8; 7; 6; 4; 2; 5}
    - Bước 31: Duyệt khi i = 10; tg = x(10) = 5; j = 9; bắt đầu vòng lặp WHILE; x(j) = x(9) = 2; x(j) < tg; đổi chỗ x(10) và x(9). Hiện tại X = {22; 12; 11; 9; 8; 7; 6; 4; 5; 2}
    - Bước 32: tiếp tục j = j -1 = 8; x(j) = x(8) = 4; x(j)< tg; đổi chỗ x(9) và x(8). Hiện tại X = {22; 12; 11; 9; 8; 7; 6; 5; 4; 2}
    - Bước 33: tiếp tục j = j -1 = 7; x(j) = x(7) = 6; x(j) > tg; Kết thúc vòng lặp WHILE. Hiện tại X = {22; 12; 11; 9; 8; 7; 6; 5; 4, 2}
    - Bước 34: Ghi ra tập X = {22; 12; 11; 9; 8; 7; 6; 5; 4, 2}

    dacminhm

    dacminhm
    Thành viên cao cấp
    Thành viên cao cấp
    Câu V. Cho hàm số f(x) xác định , liên tục và đơn điệu
    trên đoạn (a, b). Giả sử c là một giá trị thỏa mãn f(a) < c <
    f(b). Xây dựng thuật toán giải phương trình f(x) = c với sai số epsilon.
    ****************************************************
    Ý tưởng:
    _ T
    heo đề bài có hàm số f(x) liên tục và đơn điệu trên đoạn (a,b) tức là tập nghiệm của f(x) trên đoạn (a,b) là một danh sách có sắp xếp không tăng: a < b;
    _ Đoạn (a,b) có độ dài không cho trước, => dùng giải thuật đệ quy để tính
    _ sai số epsilon.không nói rõ như thế nào. ta cứ coi đó là một biến float e = epsilon. Nếu f(x) = x, thì đem so sánh nếu | x - c| < e thì ghi ra kết quả, còn không thì bỏ qua.
    Thuật toán:
    Code:

    Func. Phuongtrinh (a, b, c: double;  float e: epsilon)
              double x;
              x : = (F(a) + F(b))/2;
              if ( |F(x) - c| < e)    return (x);
              ELSE  {
                      if ( F(x) > c)  return Phuongtrinh (a, x-1, c, e);
                        ELSE              return Phuongtrinh (x, b, c, e);
                      }

    huy1984

    huy1984
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    anh em giúp e bài này với.thanh you.

    Bài 4. (Đồ thị)

    Cho một đồ thị có hướng chứa không quá 1000 đỉnh, bậc ngoài của mỗi đỉnh không quá 10. Để biểu diễn đồ thị nói trên, người ta sử dụng một ma trận thưa với định nghĩa như sau:


    Trên C
    struct Node {

    int data;

    int outNodes[10];

    int numberOfOutNodes;

    };

    struct Graph {

    struct Node nodes[1000];

    int numberOfNodes;

    };



    Trên Pascal
    type

    Node =

    record

    data : Integer;

    outNodes : array[1..10] of Integer;

    numberOfOutNodes : Integer;

    end;

    Graph =

    record

    nodes : array[1..1000] of Node;

    numberOfNodes : Integer;

    end;



    Hãy viết chương trình con đếm các đỉnh liên thông với v trong đồ thị g (đỉnh liên thông u là đỉnh có tồn tại đường đi từ v đến u trên đồ thị)

    Trên C:

    int countConnectedNodes(struct Graph *g, int v);

    Trên Pascal:

    Function countConnectedNodes(g : ^Graph , v : Integer) : Integer;

    nvdon

    nvdon
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    thank very much

    ngoanhtuan

    ngoanhtuan
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Cám ơn nhiều, diễn đàn rất ý nghĩa !

    thanlong2910

    thanlong2910
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    dacminhm đã viết:Câu V. Cho hàm số f(x) xác định , liên tục và đơn điệu
    trên đoạn (a, b). Giả sử c là một giá trị thỏa mãn f(a) < c <
    f(b). Xây dựng thuật toán giải phương trình f(x) = c với sai số epsilon.
    ****************************************************
    Ý tưởng:
    _ T
    heo đề bài có hàm số f(x) liên tục và đơn điệu trên đoạn (a,b) tức là tập nghiệm của f(x) trên đoạn (a,b) là một danh sách có sắp xếp không tăng: a < b;
    _ Đoạn (a,b) có độ dài không cho trước, => dùng giải thuật đệ quy để tính
    _ sai số epsilon.không nói rõ như thế nào. ta cứ coi đó là một biến float e = epsilon. Nếu f(x) = x, thì đem so sánh nếu | x - c| < e thì ghi ra kết quả, còn không thì bỏ qua.
    Thuật toán:
    Code:

    Func. Phuongtrinh (a, b, c: double;  float e: epsilon)
              double x;
              [b]x : = (F(a) + F(b))/2;[/b]
              if ( |F(x) - c| < e)    return (x);
              ELSE  {
                      if ( F(x) > c)  return [b]Phuongtrinh (a, x-1, c, e);[/b]
                        ELSE              return Phuongtrinh (x, b, c, e);
                      }


    Bác xem lại hộ em cái: (x = a+b)/2;
    và: if (f(x)>c) return Phuongtrinh(a,x,c,e) nhé.

    thanlong2910

    thanlong2910
    Thành viên ít chịu khó
    Thành viên ít chịu khó
    [quote="dacminhm"]Câu II.a
    [td style="padding:.75pt .75pt .75pt .75pt"]



    b
    [/td] [td style="padding:.75pt .75pt .75pt .75pt"]



    e
    [/td] [td style="padding:.75pt .75pt .75pt .75pt"]



    u
    [/td] [td style="padding:.75pt .75pt .75pt .75pt"]



    Mã hóa
    [/td] [td style="padding:.75pt .75pt .75pt .75pt"]



    10
    [/td] [td style="padding:.75pt .75pt .75pt .75pt"]



    001
    [/td] [td style="padding:.75pt .75pt .75pt .75pt"]



    0001
    [/td] [td style="padding:.75pt .75pt .75pt .75pt"]



    0111
    [/td]
    26.2 + 29.3 +18.3 +21.3 + 12.4+10.4+8.4+6.4 = 400

    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