Đạ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
    Trong các đề thi có nhiều trường hợp phải đếm số lượng phần tử của một tập hợp thông qua các tập con của chúng. Ta sẽ xét cách giải các bài toán dạng này như thế nào? Tôi sưu tầm cách giải này thông qua các cuốn bồi dưỡng học sinh giỏi. Đây là nôi dung của thầy Vũ Đình Hoà (người đã từng đoạt giải toán quốc tế, thế kỷ trước) hướng dẫn.

    Ví dụ 1. Có 2 bài toán kiểm tra, nhưng lớp chỉ có 30 hs làm được bài thứ nhất và 20 hs làm được bài thứ 2. Chỉ có 10 hs làm được cả 2 bài. Hỏi số học sinh trong lớp?

    Giải:
    Gọi A là tạp hợp hs giải được bài 1, và B là tập hợp hs giải được bài 2 thì A ∩ B là tập hợp hs giải được cả 2 bài toán. Bài toán đặt ra là tính số phần tử A U B.

    Nếu A và B là 2 tập rời nhau thì:
    |A ∩ B| = |A| + |B|

    Trong trường hợp A và B giao khác Ø thì phải áp dụng công thức:
    |A U B| = |A| + |B| - |A ∩ B|
    bởi trong tổng |A| + |B| thì các phần tử chung trong |A ∩ B| (của cả A và B) được tính lặp đúng 2 lần.

    Sử dụng công thức này ta thấy số học sinh của lớp là:
    30 + 20 - 10 = 40 hs.

    Ví dụ 2. Giờ kiểm tra TRR có 3 bài. Biết rằng, mỗi hs làm được ít nhất 1 bài. Có
    20 hs làm được bài 1.
    14 hs làm được bài 2.
    10 hs làm được bài 3.
    6 hs giải được bài 1 và 3.
    5 hs giải được bài 2 và bài 3.
    2 hs giải được bài 1 và 2.
    1 hs giải được cả 3 bài.
    Hỏi lớp có bao nhiêu học sinh.

    Giải:
    Gọi A là số hs giải bài 1. B là số hs giải bài 2. C là số hs giải bài 3. Tính số học sinh tức là tính A U B U C.
    Lập luận tương tự bài trên để có công thức:
    |A U B U C| = |A| + |B| + |C| - (A ∩ B| - |B∩C| - |C∩A| + |A ∩B ∩C|
    = 20 + 14 + 10 - 6 - 5 - 2 + 1 = 32

    Bây giờ ta hãy giải đề thi năm 2007. Câu 1b.
    Trong lớp có 60 sv sau kỳ thi gòm 3 môn.
    25 sv không phải thi lại TRR.
    30 sv không phải thi lại CTDL.
    35 sv không phải thi lại Tiếng Anh.
    45 sv không phải thi lại ít nhất 2 môn.
    12 sv phải thi lại cả 3 môn.
    Tính số sv không phải thi lại môn nào.

    Bài toán này đảo vị trí các dữ liệu với 2 ví dụ trên. Có thể hiểu là:
    không phải thi lại = tổng số - thi lại
    Hoặc tổng = X + Y chẳng hạn, thì Y = Tổng - X

    Hãy giải đề thi trên bằng nhiều cách nhé!



    Được sửa bởi Admin ngày Sun Jun 26, 2011 10:28 am; 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

    2 Nguyên lý bao hàm loại trừ on Sun Jun 12, 2011 12:20 pm

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Bài anh giải là dựa trên nguyên lý bao hàm loại trừ.
    Nguyên lý này phát biểu tổng quát và chứng minh khá chi tiết ở Nhật ký toán học, nháy vào đây để đọc thêm và xem cách chứng minh bằng quy nạp
    Công thức tổng quát của nó hay dùng nhất là:
    |Hợp của các tập hợp ∩ nhau| = |tổng của các tập đơn| - |Tổng của ∩ tập đôi| + |tổng của ∩ tập ba| - |Tổng của ∩ tập bốn|...
    cứ cộng trừ xen kẽ...
    Nhiều bài tập ở link trên giống đề thi cao học lắm. Các anh chị chịu khó làm theo nguyên lý này cho dễ nha.
    Ví dụ: Trong tập S{1..280} có bao nhiêu số không chia hết cho 2, 3, 5 , 7
    Đặt A1 là tập các số chia hết cho 2
    Đặt A2 là tập các số chia hết cho 3
    Đặt A3 là tập các số chia hết cho 5
    Đặt A4 là tập các số chia hết cho 7
    Khi đó A1 U A2 U A3 U A4 là tập các số chia hết cho ít nhất một trong các số 2, 3, 5, 7.
    Tính bằng cách lấy 280 chia cho số chia hết, lấy phần nguyên.
    Ta sẽ được A1 = 280/2 = 140;           A2 = 280/3 = 93;           A3 = 280/5;           A4 = 280/7 =40
    Tính A1 ∩ A2 = 280/6 =46,           Tính A1 ∩ A3 = 280/10 =28
    Tính A1 ∩ A4 = 280/14 =20,           Tính A2 ∩ A3 = 280/15 =18
    Tính A2 ∩ A4 = 280/21 =13,           Tính A3 ∩ A4 = 280/35 =8
    Tính A1 ∩ A2 ∩ A3 = 280/30 =9,           Tính A1 ∩ A2 ∩ A4 = 280/42 =6
    Tính A1 ∩ A3 ∩ A4 = 280/70 =4,           Tính A2 ∩ A3 ∩ A4 = 280/105 =2
    Tính A1 ∩ A2 ∩ A3 ∩ A4 = 280/210 = 1
    Sử dụng công thức bao hàm loại trừ tìm được A1 U A2 U A3 U A4 = 216
    Số không chia hết cho 2, 3, 5, 7 trong S là 280 - 216 = 64.
    [You must be registered and logged in to see this image.] Các anh chị vui tính quá! Tiêu đề bài shock ghê!


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    Admin


    Quản trị viên
    Quản trị viên
    Trong sách thì nguyên lý này được gọi là nguyên lý bù trừ (trang 65), và nó được chứng minh tổng quát ở trang 68. Có phát biểu tổng quát và rút ra được giống như link mà bạn Hải Yến đã nêu.


    Bây giờ ta hãy giải đề thi năm 2007. Câu 1b.

    Trong lớp có 60 sv sau kỳ thi gòm 3 môn.

    25 sv không phải thi lại TRR.

    30 sv không phải thi lại CTDL.

    35 sv không phải thi lại Tiếng Anh.

    45 sv không phải thi lại ít nhất 2 môn.

    12 sv phải thi lại cả 3 môn.

    Tính số sv không phải thi lại môn nào.



    Bài này đề năm 2007 ra sai. Nên nếu giải ra sẽ có đáp số âm. Hôm nay thầy chỉnh lại 1 con số, đó là sĩ số lớp 70 chứ không phải 60 học sinh.
    Đây là tóm tắt lời giải của thầy trên lớp, nếu Khách viếng thăm không đi học, có thể tham khảo. Nếu Khách viếng thăm có đi học, thì kiểm tra xem lời giải có đúng như thầy chữa trên lớp không? Bởi tốc độ của thầy như ngựa phi, ai mà chưa kịp định thần thì đã sang nội dung khác mất rồi.

    Gọi a là số sinh viên thi lại TRR. Ta có: Na = 70 - 25 = 45
    Gọi b là số sinh viên thi lại CTDL. Ta có Nb = 70 - 30 = 40
    Gọi c là số sinh viên thi lại Tiếng Anh. Ta có Nb = 70 - 35 = 35

    Ta có: N(a ∩ b ∩ c) = 12
    N (a ∩ b) + N (b ∩ c) + N (a ∩ c) - 2N (a ∩ b ∩ c) = 45
    N (a ∩ b) + N (b ∩ c) + N (a ∩ c) = 45 + 24 = 69

    Theo nguyên lý bù trừ:
    N(a U b U c) = Na + Nb + Nc - N (a ∩ b) + N (b ∩ c) + N (a ∩ c) + N(a ∩ b ∩ c)
    = 45 + 40 + 35 - 69 + 12 = 63

    Vậy số sv không phải thi lại môn nào là:
    70 - 63 = 7


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

    vodoi1801


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    thầy ơi giải giúp em bài này theo nguyên lý bù trừ : có bao nhiêu số nguyên dương nhỏ hơn hoặc bằng 1000 hoặc là số lẻ hoặc là số chính phương?.em mới học tới nguyên lý này nên chưa lắm rõ.thanks thầy

    jetli123


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    vodoi1801 đã viết:thầy ơi giải giúp em bài này theo nguyên lý bù trừ : có bao nhiêu số nguyên dương nhỏ hơn hoặc bằng 1000 hoặc là số lẻ hoặc là số chính phương?.em mới học tới nguyên lý này nên chưa lắm rõ.thanks thầy
    không ai trả lời hô bạn à
    mình cũng đang phân vân câu này híc `)

    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 | © PunBB | Free forum support | Liên hệ | Report an abuse | Create a free blog