Chào mừng!

ĐĂNG KÝ THÀNH VIÊN MỚI TẢI ĐƯỢC TÀI LIỆU! Đăng ký ngay!

KHÁCH VÀ THÀNH VIÊN CÓ THỂ TẢI MIỄN PHÍ HƯỚNG DẪN ĐĂNG KÝ THÀNH VIÊN VÀ TẢI » THƯ MỤC MIỄN PHÍYOPOVN
ĐĂNG KÝ NÂNG CẤP THÀNH VIÊN VIP ĐĂNG KÝ NÂNG CẤP THÀNH VIÊN VIP » ĐĂNG KÝ NGAYĐĂNG KÝ NÂNG CẤP THÀNH VIÊN VIP

Yopovn

Ban quản trị Team YOPO
Thành viên BQT
Tham gia
28/1/21
Bài viết
81,456
Điểm
113
tác giả
CHUYÊN ĐỀ TIN HỌC 2021 - 2022: toán học rời rạc ứng dụng trong tin học, CHUYÊN ĐỀ SỐ HỌC

CHUYÊN ĐỀ SỐ HỌC



Bài 1 : Amount of Degrees



Một số A gọi là có bậc K đối với cơ số B nếu như :

A = Bx1 + Bx2 + … + Bxk

( trong đó x1 ¹ x2 ¹ x3 … ¹ xk )

Ví dụ :

17 có bậc 2 đối với cơ số 2 vì 17 = 24 + 20 .

151 có bậc 3 đối với cơ số 5 vì 151 = 53 + 52 + 50.

Yêu cầu : Cho trước 1 đoạn [X,Y] . Hãy xác định xem trong đoạn này có bao nhiêu số có bậc K đối với cơ số B.

Giới hạn : + 1 £ X £ Y £ 109.

+ 1 £ K £ 20, 2 £ B £ 9.

+ Bộ nhớ : 200KB.

+ Time limit : 1 s.

Input

X Y K B

Output

Gồm 1 số duy nhất là kết quả tìm được .

Ví dụ

Input

15 20 2 2

Output

3

( Giải thích : Đó là các số 17 = 24 + 20 .

18 = 24 + 21.

20 = 24 + 22. )



Thuật giải :

Ta sẽ đưa bài toán này về một bài toán nhỏ hơn đó là cho biết trong đoạn [1,A] có bao nhiêu số có bậc K đối với cơ số B.

Với mỗi giá trị A ta đều xác định được Bn sao cho Bn+1 > A . Áp dụng tính chất: Bn > Bn-1 + Bn-2 + … B0 ® A > Bn-1 + Bn-2 + … B0.

® Tổng bất kỳ của 1 tổ hợp K phần tử của (n-1) phần tử này cũng đều < A ( tức là : A > Bx1 + Bx2 + …+ Bxi +… + Bxk ( với mọi xi £ n–1 ) ).

® Như vậy ta đã giải quyết xong vấn đề với các số mà không chứa Bn, nếu như không chứa Bn thì số lượng số thoả mãn sẽ = Tổ hợp chập K của (n-1) . Ta sẽ tiếp tục giải quyết vấn đề với các số mà có dạng = Bn + Bx2+…+Bxk.Dễ thấy vấn đề ở đây lại quay về là tìm số lượng các số có bậc (K-1) đối với cơ số B trong đoạn [1,A-Bn] và không chứa Bn, vậy thì ở đây ta chỉ cần xác định lại n mà thôi, n(mới) £ n (cũ) – 1.

Như vậy bài toán đã được giải quyết. Nói tóm lại đây là một bài khá đặc trưng cho QHĐ = Đệ quy với công thức truy hồi đơn giản :

Cal(A,K,B) = Tổ hợp chập K của (N-1) + Cal(A-Bn,K-1,B).



Bài 2 : Nikifor – 2
1634653810700.png

 

DOWNLOAD FILE

  • YOPOVN.COM_Tin học SoHoc.doc
    62.5 KB · Lượt xem: 23
Nếu bạn cảm thấy nội dung chủ đề bổ ích , Hãy LIKE hoặc bình luận để chủ đề được sôi nổi hơn
  • Từ khóa
    báo cáo chuyên đề môn tin học thcs báo cáo chuyên đề tin học các chuyên đề tin học 6 chuyên de tin học lớp 3 chuyên de tin học thcs chuyên đề bồi dưỡng học sinh giỏi tin 8 chuyên đề bồi dưỡng học sinh giỏi tin học 12 chuyên đề bồi dưỡng học sinh giỏi tin học thcs chuyên đề bồi dưỡng học sinh giỏi tin học thpt chuyên đề bồi dưỡng hsg tin học thcs chuyên đề bồi dưỡng hsg tin học thpt chuyên đề bồi dưỡng tin học trẻ thcs chuyên đề môn tin học chuyên đề môn tin học lớp 10 chuyên đề môn tin học lớp 9 chuyên đề môn tin học thcs chuyên đề môn tin học tiểu học chuyên đề ôn thi học sinh giỏi tin học 11 chuyên đề tin học chuyên đề tin học 10 chuyên đề tin học 11 chuyên đề tin học 6 chuyên đề tin học 7 chuyên đề tin học 8 chuyên đề tin học 9 chuyên đề tin học lớp 11 chuyên đề tin học lớp 12 chuyên đề tin học lớp 4 chuyên đề tin học lớp 5 chuyên đề tin học lớp 6 chuyên đề tin học tiểu học chuyên đề tin học trẻ không chuyên chuyên đề tin học và xã hội chuyên đề xâu bồi dưỡng hsg tin học một số chuyên đề tin học lớp 6 đề chuyên tin quốc học huế đề chuyên tin quốc học huế 2019 đề chuyên tin quốc học huế 2020 đề thi chuyên tin khoa học tự nhiên đề thi chuyên viên tin học ngành thuế đề thi olympic tin học không chuyên đề thi tin học chuyên ngành đề thi tin học chuyên viên chính đề thi tin học chuyên viên chính 2017 đề thi tin học nâng ngạch chuyên viên chính đề thi tin học trẻ không chuyên cấp tỉnh đề thi tin học trẻ không chuyên lớp 5 đề thi tin học trẻ không chuyên thcs đề thi tin học trẻ không chuyên thcs pascal đề tin học trẻ không chuyên thcs đề tin học trẻ không chuyên thpt
  • HỖ TRỢ ĐĂNG KÝ VIP

    Liên hệ ZALO để được tư vấn, hỗ trợ: GỬI FILE THEO YÊU CẦU, ĐĂNG KÝ TÀI KHOẢN VIP
    ZALO:0979702422

    BÀI VIẾT MỚI

    Thống kê

    Chủ đề
    34,454
    Bài viết
    35,924
    Thành viên
    135,589
    Thành viên mới nhất
    Bùi Ngọc Tới
    Top