User Tag List

+ Trả lời chủ đề
Hiện kết quả từ 1 tới 10 của 10

Chủ đề: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

  1. #1
    svBK's Member
    Tham gia ngày
    Aug 2011
    Bài gửi
    44

    Mặc định Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    Mình không nhớ rõ đề lắm.Chỉ tương đối thôi!

    Câu 1: Có bao nhiêu số nhị phân có n số khi đọc ngược từ cuối cũng như đọc xuôi từ đầu?
    D/A: 2^(cận trên n/2)

    Câu 2: Có 5 kĩ sư tin học, 6 vị giáo sư. Có bao nhiêu cách xếp 11 người vào 1 bàn tròn sao cho không có 2 kĩ sư nào ngồi cạnh nhau?
    D/A: ( C(5,6)*5!*5!*5 )/5 = 86400
    Ps: Câu này tớ không chắc nhắn lắm, mọi người ra bao nhiêu?

    Câu 3:
    D/A:96

    Câu 4:
    D/A: Bằng 24 thì phải, mất toi bài này rồi, bài này tớ nhầm điểm
    Câu 5:...
    a. Lí thuyết
    b. Vẽ
    c. Tìm luồng cực đại
    Lần sửa cuối bởi dattbbk; 25-05-2012 lúc 07:37 PM
    Điều quan trọng không phải vị trí ta đang đứng, mà ở hướng ta đang đi...

  2. #2
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    Mình học thầy Thuận, hôm nay làm bài chán quá, chán nhất là cái bài đệ quy sai rất ngu
    Contact me:
    Email: sangnd [at] svBK.vn
    Personal website: My Blog | Chat với người lạ
    Facebook Page của Bách Khoa Forum: http://www.facebook.com/svbk.vn

  3. #3
    svBK's Newbie Avatar của Foundations
    Tham gia ngày
    Feb 2012
    Bài gửi
    4

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    ---------------------------------------------------------------------------------------------
    Câu 1: Có bao nhiêu số nhị phân có n số khi đọc ngược từ cuối cũng như đọc xuôi từ đầu? (xâu Palindrome)
    Kết quả: T(n) = 2^[n/2] (n/2 là chia rồi lấy phần nguyên già (tăng lên), ví dụ 3/2 = 1.5 thì lấy to hơn là 2)
    Cách 1: tính trực tiếp: thực chất số lượng xâu cần tìm bằng số lượng xâu có độ dài n/2, sắp xếp n/2 kí tự 0 và 1, ta được 2^(n/2) xâu
    Cách 2: tính đệ quy.
    n = 2k (chẵn) thì thêm vào giữa của xâu 1 kí tự (0 hoặc 1) ta đều thu được xâu thỏa mãn => T(2k+1) = 2*T(2k)
    n = 2k + 1 (lẻ) thì giữa xâu có 1 kí tự (0 hoặc 1), ta thêm vào cạnh kí tự này (thành 00 hoặc 11) để có xâu mới => T(2k+2) = T(2k + 1)
    Dãy T(n) = 2, 2, 4, 4, 8, 8, 16, 16, ... , 2^[n/2]
    ---------------------------------------------------------------------------------------------
    Câu 2: Có 5 kĩ sư tin học, 6 vị giáo sư. Có bao nhiêu cách xếp 11 người vào 11 ghế sao cho không có 2 kĩ sư nào ngồi cạnh nhau?
    Cách xếp:
    Xếp 5 kĩ sư tin học vào 5 vị trị A, B, C, D, E. có 5! cách hoán vị những người này. ___A___B___C___D___E___
    giữa 5 điểm nói trên có 6 khoảng trống, kí hiệu x1,x2,x3,x4,x5,x6.......................x1....x2.. .x3....x4....x5...x6
    xếp 6 luật sư vào 6 khoảng trống, có 6! cách hoán vị giữa các luật sư này
    Theo đề bài, để thỏa mãn không có 2 kĩ sư nào ngồi cạnh nhau thì x2,x3,x4,x5 phải có ít nhất 1 luật sư. Yêu cầu này tương đương với
    x1 + x2 + x3 + x4 + x5 + x6 = 6
    x1,x6>=0
    x2,x3,x4,x5 >= 1
    Thực hiện đổi biến
    y1= x1
    y2 = x2 - 1
    y3 = x3 - 1
    y4 = x4 - 1
    y5 = x5 - 1
    y6 = x6
    Ta đươc hệ
    y1 + y2 + y3 + y4 + y5 + ỵ6 = 2
    y1, y2, y3, y4, y5, y6 >= 0
    Giải theo bài toán chia kẹo, số lượng cách xếp là chỉnh hợp chỉnh hợp lặp chập 6 của 2 phần tử = 7C5
    Theo quy tắc nhân, số cách xếp là 5! * 6! * (7C5) = 120 * 720 * 21 = 1 814 400 (cách xếp)
    ----------------------------------------------------------------------------------
    Chúc anh em thi lại thành công

  4. #4
    svBK's Member
    Tham gia ngày
    Aug 2011
    Bài gửi
    44

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    Quote Nguyên văn bởi 1973 Xem bài viết
    Mình học thầy Thuận, hôm nay làm bài chán quá, chán nhất là cái bài đệ quy sai rất ngu
    Công nhận không ngờ đề thầy lại "hóc" như vậy
    Thôi Sang ạ! Dù sao cũng thi xong rồi, quên đi. Anh em tập trung ôn đường lối_2 ngày 16 câu, không biêt có nạp kịp không

  5. #5
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    Bọn tớ 29 mới thi nên vẫn còn 4 ngày, ôn dần dần vậy.

    Phải nói là thầy Thuận cho đề tập trung vào 1 mảng kiến thức quá, không cho thêm câu Tồn tại và tối ưu tổ hợp thì có phải sinh viên gỡ gạc được tẹo không

  6. #6
    svBK's Member
    Tham gia ngày
    Aug 2011
    Bài gửi
    44

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    Quote Nguyên văn bởi Foundations Xem bài viết
    ---------------------------------------------------------------------------------------------
    Câu 1: Có bao nhiêu số nhị phân có n số khi đọc ngược từ cuối cũng như đọc xuôi từ đầu? (xâu Palindrome)
    Kết quả: T(n) = 2^[n/2] (n/2 là chia rồi lấy phần nguyên già (tăng lên), ví dụ 3/2 = 1.5 thì lấy to hơn là 2)
    Cách 1: tính trực tiếp: thực chất số lượng xâu cần tìm bằng số lượng xâu có độ dài n/2, sắp xếp n/2 kí tự 0 và 1, ta được 2^(n/2) xâu
    Cách 2: tính đệ quy.
    n = 2k (chẵn) thì thêm vào giữa của xâu 1 kí tự (0 hoặc 1) ta đều thu được xâu thỏa mãn => T(2k+1) = 2*T(2k)
    n = 2k + 1 (lẻ) thì giữa xâu có 1 kí tự (0 hoặc 1), ta thêm vào cạnh kí tự này (thành 00 hoặc 11) để có xâu mới => T(2k+2) = T(2k + 1)
    Dãy T(n) = 2, 2, 4, 4, 8, 8, 16, 16, ... , 2^[n/2]
    ---------------------------------------------------------------------------------------------
    Câu 2: Có 5 kĩ sư tin học, 6 vị giáo sư. Có bao nhiêu cách xếp 11 người vào 11 ghế sao cho không có 2 kĩ sư nào ngồi cạnh nhau?
    Cách xếp:
    Xếp 5 kĩ sư tin học vào 5 vị trị A, B, C, D, E. có 5! cách hoán vị những người này. ___A___B___C___D___E___
    giữa 5 điểm nói trên có 6 khoảng trống, kí hiệu x1,x2,x3,x4,x5,x6.......................x1....x2.. .x3....x4....x5...x6
    xếp 6 luật sư vào 6 khoảng trống, có 6! cách hoán vị giữa các luật sư này
    Theo đề bài, để thỏa mãn không có 2 kĩ sư nào ngồi cạnh nhau thì x2,x3,x4,x5 phải có ít nhất 1 luật sư. Yêu cầu này tương đương với
    x1 + x2 + x3 + x4 + x5 + x6 = 6
    x1,x6>=0
    x2,x3,x4,x5 >= 1
    Thực hiện đổi biến
    y1= x1
    y2 = x2 - 1
    y3 = x3 - 1
    y4 = x4 - 1
    y5 = x5 - 1
    y6 = x6
    Ta đươc hệ
    y1 + y2 + y3 + y4 + y5 + ỵ6 = 2
    y1, y2, y3, y4, y5, y6 >= 0
    Giải theo bài toán chia kẹo, số lượng cách xếp là chỉnh hợp chỉnh hợp lặp chập 6 của 2 phần tử = 7C5
    Theo quy tắc nhân, số cách xếp là 5! * 6! * (7C5) = 120 * 720 * 21 = 1 814 400 (cách xếp)
    ----------------------------------------------------------------------------------
    Chúc anh em thi lại thành công
    Đề bài yêu cầu bàn tròn Foundations à

  7. #7
    svBK's Newbie Avatar của Foundations
    Tham gia ngày
    Feb 2012
    Bài gửi
    4

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    nguyên văn đấy, xếp vào 11 ghế cạnh nhau, không phải bàn tròn đâu

  8. #8
    svBK's Member
    Tham gia ngày
    Aug 2011
    Bài gửi
    44

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    Quote Nguyên văn bởi Foundations Xem bài viết
    nguyên văn đấy, xếp vào 11 ghế cạnh nhau, không phải bàn tròn đâu
    Bàn tròn mà, tớ mới đọ với mấy ông xong

  9. #9
    svBK's Newbie Avatar của Foundations
    Tham gia ngày
    Feb 2012
    Bài gửi
    4

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    thế thì t sai rồi, chán, đã không làm được, lại còn nhìn sai đề, hic

  10. #10
    svBK's Newbie
    Tham gia ngày
    Oct 2013
    Bài gửi
    2

    Mặc định Re: Toán rời rạc! Ai học cô Bình, nay thi đề 2 vào đọ đáp án chút!!!

    Năm nay mình đang học thầy thuận toán rời rạc. Bạn còn nhớ để thi không 1973? Có gửi giúp mình nhé

+ Trả lời chủ đề

Thông tin chủ đề

Users Browsing this Thread

Hiện có 1 người đọc bài này. (0 thành viên và 1 khách)

Từ khóa (Tag) của chủ đề này

Quyền viết bài

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình


About svBK.VN

    Bách Khoa Forum - Diễn đàn thảo luận chung của sinh viên ĐH Bách Khoa Hà Nội. Nơi giao lưu giữa sinh viên - cựu sinh viên - giảng viên của trường.

Follow us on

Twitter Facebook youtube