BÀI TẬP Ở NHÀ

Đây là câu 1 của đề thi học sinh giỏi tỉnh môn tin học năm 2015 - 2016. Mặc dù là câu 1 nhưng đây là một câu không phải quá dễ. Để xử lý được câu này thì cần có kỹ năng xử lý xâu. Trong bài này baitaponha.com xin trình bày cho các bạn các cách xử lý xâu. Vì bài dễ nên sẽ trình bày chi tiết nhằm cho các bạn mới tìm hiểu về Python cũng có thể hiểu được. Qua lời giải các bạn sẽ thấy điểm mạnh của Python là xử lý trong 1 dòng code.

Đây là câu 4 nên là một câu khó. Thoạt đầu đọc đề thì có vẻ rất dễ hiểu, nhưng khi xử lý code thì sẽ gặp nhiều khó khăn. Bởi theo định nghĩa tích riêng của một số là tích của số đó với các chữ số của nó. Và bài toán yêu cầu đếm các số có tích riêng thuộc khoảng [A; B] với 1 <= A, B <= 10¹⁸ , Như vậy A, B rất lớn. Một điều khó khăn nữa là: nếu a < b nhưng chúng ta sẽ không biết được TR(a) và TR(b) số nào lớn hơn. Ví dụ khi A = 20; B = 30 thì ta sẽ tìm được những số có tích riêng nằm trong khoảng [20; 30] là 5 và 12, có nghĩa trong khoảng này chỉ có 2 số cần tìm. Vậy công thức để máy tính tìm được 5 và 12 là gì, mời các bạn cùng tham khảo lời giải.

Đây là một bài khá hay, một bài toán thách thức về thuật toán. Xử lý thuật toán tốt thì mới ăn full test bài này, còn không thì chỉ ăn được 60% test. Trong bài này chúng ta sẽ sử dụng thuật toán Rabin-Karp để tìm xâu con có độ dài bằng K xuất hiện trong xâu ban đầu, đây là thuật toán sử dụng mã băm. Thuật toán Rabin-Karp là thuật toán tương đối khó giải thích, các bạn có thể tự tìm hiểu thêm. Ngoài việc sử dụng thuật toán Rabin-Karp thì ta còn phài dùng thêm thuật toán TÌM KIẾM NHỊ PHÂN thì mới chạy full test bài này.
Ngoài ra trong bài này các bạn sẽ thấy được yếu điểm của Python về tốc độ xử lý thuật toán. Cùng một thuật toán, nhưng Python xử lý chậm hơn Pascal rất nhiều lần! Đừng quên theo dõi Fanpage và đăng ký kênh YOTUBE của admin để xem như lời cảm ởn!