Bài 1:Về nguyên lý bù trừ cho e hỏi câu:
Cho 10000 số từ 1 đến 10000.Hỏi có bao nhiêu số chia hết cho 7 đồng thời không chia hết cho 2 và 5.
(câu này e tìm được có bao nhiêu số chia hết cho 7 rồi,bao nhiêu số không chia hết cho 2 và 5 rồi nhưng e không thể dùng công thức gì liên kết giữa chia hết cho 7 và không chia hết cho 2 và 5 cả híc)
Baì 2: Hệ thức truy hồi
Đếm xâu nhị phân Fn có độ dài n sao cho không có 3 số không liên tiếp
(Em đã áp dụng cách lập hệ thức truy hồi mà admin đã nói nhưng có 1 số vấn đề mà nó không đúng với điều kiện là 3 số 0,e giải 2 số 0 thì ngon ơ vì e vẫn chưa hiểu rõ mấy và chỉ biết áp dụng khuôn mẫu)
mong mọi nguwoif hướng dẫn e giải 2 bài này .Thanks everyone

Mình không phải dân lập trình, không biết nguyên lý bù trừ là cái gì...
Nhưng ở bài 1 mình thấy có suy nghĩ đơn giản như thế này:
Đề: "Cho 10000 số từ 1 đến 10000.Hỏi có bao nhiêu số chia hết cho 7 đồng thời không chia hết cho 2 và 5.".

Có thể giải:
- Lấy phần nguyên của 10000/7 chính là tổng số các số chia hết cho 7.
- Qui luật các số chia hết cho 7 là: 7n (n: nguyên dương).
- Xét tập (7n) các số trong dãy 7n Thấy:
Nếu n lẻ thì 7n không chia hết cho 2, vậy tổng số các số trong tập 7n không chia hết cho 2 là = (n+1)/ 2
Nếu n chẵn thì 7n chi hết cho 2, tổng số các số trong tập 7n không chia hết cho 2 là n/2.
Gọi tệp số vừa chia hết cho 7 mà lại vừa không chia hết cho n là tệp 7n02
- Xét tệp 7n02 trên với trường hợp chia hết cho 5, tương đương với việc xét tệp 7n chia hết cho 35 gọi là tệp 35n02, làm tương tự như 7n chia hết cho 2.
- Kết quả cần tìm sẽ bằng 7n02 - 35n02.

lehoang103 đã viết:Mình không phải dân lập trình, không biết nguyên lý bù trừ là cái gì...
Nhưng ở bài 1 mình thấy có suy nghĩ đơn giản như thế này:
Đề: "Cho 10000 số từ 1 đến 10000.Hỏi có bao nhiêu số chia hết cho 7 đồng thời không chia hết cho 2 và 5.".

Có thể giải:
- Lấy phần nguyên của 10000/7 chính là tổng số các số chia hết cho 7.
- Qui luật các số chia hết cho 7 là: 7n (n: nguyên dương).
- Xét tập (7n) các số trong dãy 7n Thấy:
Nếu n lẻ thì 7n không chia hết cho 2, vậy tổng số các số trong tập 7n không chia hết cho 2 là = (n+1)/ 2
Nếu n chẵn thì 7n chi hết cho 2, tổng số các số trong tập 7n không chia hết cho 2 là n/2.
Gọi tệp số vừa chia hết cho 7 mà lại vừa không chia hết cho n là tệp 7n02
- Xét tệp 7n02 trên với trường hợp chia hết cho 5, tương đương với việc xét tệp 7n chia hết cho 35 gọi là tệp 35n02, làm tương tự như 7n chia hết cho 2.
- Kết quả cần tìm sẽ bằng 7n02 - 35n02.

Cơ mà sao không dùng 7n không chia hết cho 10 luôn hả bạn
mà mình không hiểu mấy bạn thử lấy ví dụ ở khoảng từ 1 tới 100 xem nào

jetli123 đã viết:
Cơ mà sao không dùng 7n không chia hết cho 10 luôn hả bạn
mà mình không hiểu mấy bạn thử lấy ví dụ ở khoảng từ 1 tới 100 xem nào

Không chia hết cho 10 hoàn toàn khác với việc không chia hết cho 2 và không chia hết cho 5.
Ví dụ: 15 không chia hết cho 10, nhưng vẫn chia hết cho 5.

Chứng minh nhận xét trên:
Gọi:
Tập điều kiện (Tập tổng) = T(S) - khác rỗng.
Tập hợp số không chia hết cho 10 = T(0-10)
Tập hợp số chia hết cho cả 2 và 5 = T(2&5) = Tập hợp số chia hết cho 10 = T(10)
Tập hợp số không chia hết cho 2 và 5 = T(0-2&5)
Tập hợp số chia hết cho 2 mà không chia hết cho 5 = T(2-05)
Tập hợp số chia hết cho 5 mà ko chia hết cho 2 = T(5-02)

Có T(0-10) = T(S) - T(10).
T(0-2&5) = T(S) - T(2-05)- T(5-02) - T(2&5)
T(0-2&5) = T(S) - T(2-05)- T(5-02) - T(10)..
Hiển nhiên thấy: T(2-05) + T (5-02) > 0 - trừ trường hợp xét T(S) = {1}.
=> T(0-10) Khác T(0-2&5).(đpcm)