1. Kết quả Event Ghost 2016


    Dưới đây là danh sách những thành viên đoạt giải thưởng trong Event Ghost 2016

Mỗi Tuần 1 bài tập.

Thảo luận trong 'Pascal, C , C++' bắt đầu bởi ngochivinh, 21 Tháng hai 2012.


  1. ngochivinh

    ngochivinh Member Chính Thức

    30
    32
    18
    Bài 1: Cài đặt lại các bài toán đã giải trong chương 1.
    Bài 2: Giải các công thức truy hồi sau:
    • T(n) = 9T(n/3) + n
    • T(n) = T(2n/3) + 1
    • T(n) = 3T(n/4) + nlgn
    Bài 3: Cài đặt giải thuật giải quyết bài toán sau bằng cả hai phương pháp đệ quy và không đệ quy:
    Quá trình sinh sản của thỏ diễn ra theo quy tắc:
    • Các con thỏ không bao giờ chết
    • Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái)
    • Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới
    Giả sử từ đầu tháng 1 có một cặp mới ra đời thì đến giữa tháng thứ n sẽ có bao nhiêu cặp?
    Phân tích độ phức tạp của giải thuật trong cả hai trường hợp.
    Bài 4: Cài đặt giải thuật giải quyết bài toán Tháp Hà Nội bằng cả hai phương pháp đệ quy và không đệ quy. Phân tích độ phức tạp của giải thuật trong cả hai trường hợp.
    Bài 5: Cài đặt giải thuật giải quyết bài toán tính tổ hợp chập k của n phần tử bằng cả hai phương pháp đệ quy và không đệ quy. Phân tích độ phức tạp của giải thuật trong cả hai trường hợp.

    Mọi người cùng giải nhé. Cuối tuần mình sẻ ra đáp án.
     
  2. MrKing

    MrKing Thành Viên Cống Hiến

    1,177
    607
    113
    Đây là của 5 tuần àh!:th_117::th_117::th_117:
     
  3. khatmau_sr

    khatmau_sr Administrator Ban Quản Trị

    10,209
    9,570
    113
    Tên thật:
    Nguyễn Đình Bách
    Thanks nhưng mình lười lắm ! :th_6:
     
  4. Ljnkvn

    Ljnkvn Member Chính Thức

    9
    10
    3
    Nhìn đã thấy ngán rồi, hồi còn đi học thì chắc cũng chịu khó tí đây :th_9:
     
  5. ngochivinh

    ngochivinh Member Chính Thức

    30
    32
    18
    Bài 3: Cài đặt giải thuật giải quyết bài toán sau bằng cả hai phương pháp đệ quy và không đệ quy:
    Quá trình sinh sản của thỏ diễn ra theo quy tắc:
    • Các con thỏ không bao giờ chết
    • Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái)
    • Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới
    Giả sử từ đầu tháng 1 có một cặp mới ra đời thì đến giữa tháng thứ n sẽ có bao nhiêu cặp?
    Phân tích độ phức tạp của giải thuật trong cả hai trường hợp.

    Giải:
    (1) Giả sử từ đầu tháng 1 có một cặp mới ra đời
    (2) Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái)
    Từ giả thiết (1) và (2) ta có:

    *Tháng 1 có 1 cặp thỏ.
    *Tháng 2 có 1 cặp thỏ.
    (3) Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới
    *Tháng 3 có 2 cặp thỏ (1 cặp 2 trên tháng và 1 cặp 1 tháng)
    *Tháng 4 có 3 cặp thỏ (2 cặp 2 trên tháng và 1 cặp 1 tháng )
    *Tháng 5 có 5 cặp thỏ (3 cặp 2 trên tháng và 2 cặp 1 tháng)

    Ta thấy rằng số thỏ tăng lên theo quy luật của dãy số fibonaxi: 1 1 2 3 5 8
    Ta có công thức truy hồi của dãy số:

    T(1) = T(2) = 1
    T(n)=T(n-1)+(n-2) Với n>=3

    Giải Thích:
    Vì số cặp thỏ ở tháng này = số cặp thỏ ở tháng sau + Số cặp thỏ ở tháng sau nữa(Vì số cặp thỏ ở tháng sau nữa tới tháng này đều có tuổi >= 2 tháng ->vậy mỗi cặp của tháng sau nữa sẽ sinh ra 1 cặp )

    fibo1.jpg
    fibo2.jpg
     
  6. anhtaicm727

    anhtaicm727 Member Mới

    2
    1
    3
    bạn ơi giúp mình gấp.
    giống như bài tập 3 ở trên.
    giải thuật đầu tiền bạn nghĩ tới là gì? tại sao...
    tks bạn nhìu lắm luôn. bài tập lớn phải nộp thời gian gấp. help me
     
    myth thích bài này.
  7. anhtaicm727

    anhtaicm727 Member Mới

    2
    1
    3
    bạn ơi help me với. mình tks gất nhìu.
    bài 3 ở trên. giải thuật đầu tiên bạn nghĩ tới.? tại sao.
     

Chia sẻ trang này