Sáng kiến kinh nghiệm THPT: Vận dụng kiến thức Số học trong việc lập trình giải các bài toán bằng ngôn ngữ C++

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:46

Thêm vào BST

Báo xấu

26
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu sáng kiến "Vận dụng kiến thức Số học trong việc lập trình giải các bài toán bằng ngôn ngữ C++" nhằm trao đổi cùng với các đồng nghiệp về việc vận dụng các kiến thức Số học trong việc lập trình giải một số bài toán; là tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng HSG.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Vận dụng kiến thức Số học trong việc lập trình giải các bài toán bằng ngôn ngữ C++

SÁNG KIẾN KINH NGHIỆM ĐỀ TÀI VẬN DỤNG KIẾN THỨC SỐ HỌC TRONG VIỆC LẬP TRÌNH GIẢI CÁC BÀI TOÁN BẰNG NGÔN NGỮ C++ Người thực hiện: Trần Đức Sáu Phạm Thị Thu Hường Đơn vị : Tổ Toán – Tin Số điện thoại : 0912128454 0975483338 NĂM HỌC 2021 – 2022
MỤC LỤC ĐẶT VẤN ĐỀ ....................................................................................................... 2 1. Lý do cho ̣n đề tài........................................................................................ 2 2. Cấu trúc nội dung ....................................................................................... 2 Phầ n 1. Lý thuyết cơ bản ................................................................................. 2 Phầ n 2. Hệ thống các bài tập ............................................................................ 2 3. Mu ̣c đić h nghiên cứu .................................................................................. 2 4. Phương pháp nghiên cứu. ........................................................................... 2 5. Giới hạn phạm vi nghiên cứu của đề tài ..................................................... 2 NỘI DUNG ............................................................................................................ 4 Phần I. Lý thuyết cơ bản ..................................................................................... 4 1.1. Các dấu hiệu chia hết cho các số ............................................................... 4 1.2. Số nguyên tố ............................................................................................. 4 1.3. Lý thuyết đồng dư ..................................................................................... 5 Phần II. Bài tập ................................................................................................... 6 KẾT QUẢ ÁP DỤNG ........................................................................................ 444 KẾT LUẬN ........................................................................................................ 444 TÀI LIỆU THAM KHẢO ................................................................................. 455 1
ĐẶT VẤN ĐỀ 1. Lý do cho ̣n đề tài Số học là kiến thức Toán học được các em học sinh làm quen khá nhiều từ thời cấp 2. Ví dụ như các dấu hiệu chia hết cho các số, cách tìm chữ số tận cùng của một số,... Trong nhiều bài toán Tin học, việc vận dụng kiến thức số học giúp đưa ra được những thuật toán tối ưu hơn. Mặt khác, những bài toán Tin học có sự vận dụng kiến thức số học cơ bản, đòi hỏi sự cài đặt không quá phức tạp, và các em có nền tảng Toán học tốt có thể dễ dàng suy luận được. Từ đó, kích thích niềm yêu thích của các em trong việc lập trình, đồng thời hình thành kỹ năng phải luôn tối ưu hóa thuật toán, ngay từ khi các em làm quen với việc lập trình. Qua quá trình tham gia giảng dạy, bồi dưỡng học sinh giỏi và việc nghiên cứu các vấn đề về những bài toán Tin học có sự vận dụng kiến thức số học cơ bản. Chúng tôi đưa ra đề tài “Vận dụng kiến thức Số học trong việc lập trình giải các bài toán bằng ngôn ngữ C++”, với mong muốn phần nào giúp học sinh cũng như giáo viên có tài liê ̣u tham khảo phu ̣c vu ̣ cho viê ̣c ho ̣c tâ ̣p và giảng da ̣y. 2. Cấu trúc nội dung Phầ n 1. Lý thuyết cơ bản 1. Các dấu hiệu chia hết cho các số 2. Số nguyên tố 3. Lý thuyết đồng dư Phầ n 2. Hệ thống các bài tập 3. Mu ̣c đích nghiên cứu Trong quá trình nghiên cứu và giảng dạy, chúng tôi nhận thấy việc vận dụng các kiến thức số học vào việc giải một số bài toán rất hiệu quả. Vì vậy, chúng tôi viết đề tài này với mục đích: - Thứ nhất, trao đổi cùng với các đồng nghiệp về việc vận dụng các kiến thức Số học trong việc lập trình giải một số bài toán. - Thứ hai, là tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng HSG. 4. Phương pháp nghiên cứu. Kinh nghiệm bản thân, thảo luận, sưu tầm tài liệu, thử nghiệm thực tế, rút kinh nghiệm từ các tiết dạy trên lớp. 5. Giới hạn phạm vi nghiên cứu của đề tài Đề tài chủ yếu nghiên cứu hệ thống bài tập có vận dụng kiến thức số học vào việc tối ưu hóa thuật toán; chỉ ra được thuật toán tối ưu trong việc giải quyết bài toán, và cài đặt chương trình bằng ngôn ngữ lập trình C++ 2
Đề tài có khả năng áp dụng rộng rãi vào giảng dạy, bồi dưỡng học sinh giỏi Tin học cho giáo viên và học sinh THCS, THPT trên địa bàn toàn tỉnh Nghệ An. 3
NỘI DUNG Việc nắm vững các kiến thức về số học là điều rất quan trọng, đó là cơ sở để các em học sinh vận dụng và giải quyết các bài toán cụ thể. Sau đây, chúng tôi xin trình bày một số kiến thức về số học và hệ thống các bài tập mà chúng tôi đã tìm hiểu và vận dụng có hiệu quả trong quá trình giảng dạy Phần I. Lý thuyết cơ bản 1.1. Các dấu hiệu chia hết cho các số  Các chữ số tận cùng là 0,2,4,6,8 thì chia hết cho 2, hoặc các số chẵn thì chia hết cho 2.  Các số có tổng các chữ số chia hết cho 3 thì số đó chia hết cho 3.  Các số có hai chữ số cuối tạo thành một số chia hết cho 4 thì số đó chia hết cho 4  Các số có tận cùng là 0 hoặc 5 thì chia hết cho 5,…… 1.2. Số nguyên tố a) Định lý cơ bản của số học Mọi số tự nhiên lớn hơn 1 có thể viết một cách duy nhất (không kể sự sai khác về thứ tự các thừa số) thành tích các thừa số nguyên tố. Mọi số tự nhiên n lớn hơn 1, có thể viết duy nhất dưới dạng: n  p11 p2 2 ............. pk k Trong đó p1 , p2 ,...., pk là các số nguyên tố và 1 , 2 ,....., k là các số tự nhiên nguyên dương. Dựa vào định lý này, ta có thể chứng minh định lý sau:  Mọi hợp số phải có ước nguyên tố nhỏ hơn hay bằng căn bậc hai của nó Chứng minh: Giả sử n=ab(1
 Ước số nguyên dương bé nhất khác 1 của một hợp số a là một số nguyên tố không vượt quá a ,….. 1.3. Lý thuyết đồng dư Các khái niệm, tính chất của đồng dư thức, và định lý cần nhớ như định lý Ferma. Ở đây tôi đề cập đến định lý Ferma nhỏ và tổng quát hóa của định lý Ferma: Định lý Ferma nhỏ Nếu p là một số nguyên tố, thì với số nguyên a bất kỳ, ap-a sẽ chia hết cho p. Nghĩa là a p  a(mod p) Một dạng tổng quát của định lý này là: nếu p là số nguyên tố và m và n là các số nguyên dương thỏa mãn m  n(mod p  1) , thì a  Z : a m  a n (mod p) Định lý Fermat còn được tổng quát hóa bởi Định lý Euler: với modulo n bất kỳ và số nguyên a bất kỳ là số nguyên tố cùng nhau với n, ta có: a ( n )  1(mod n) Trong đó  (n) là kí hiệu của hàm phi Euler đếm số các số nguyên giữa 1 và n nguyên tố cùng nhau với n. Đây là tổng quát hóa của định lý nhỏ Fermat vì nếu n=p là số nguyên tố thì  ( p)  n  1 5
Phần II. Bài tập Bài 1. Cho 4 số nguyên dương a, b, c và d. Đếm số lượng số thuộc đoạn [a, b] chia hết cho cả c và d (a ≤ b). Input: Gồm một dòng duy nhất chứa 4 số nguyên dương a, b, c, d. Output: Đưa ra kết quả bài toán Ví dụ: Input Output 1 20 2 3 3  40% số test có a, b, c, d ≤ 106  60% số test còn lại có a, b, c, d ≤ 109 Thuật toán: Với a, b, c, d ≤ 106, ta chỉ việc cho một biến i chạy từ a -> b và đếm số lượng số chia hết cho cả c và d là được. Với a, b, c, d ≤ 109, ta thấy rằng việc chia hết cho cả c và d chẳng qua chính là chia hết cho bội chung nhỏ nhất của c và d. Như vậy công thức tính sẽ là 𝑏 𝑎−1 [ ]–[ ] → O(1). [𝑐,𝑑] [𝑐,𝑑] Chương trình: 1. #include 2. using namespace std; 3. long long a,b,c,d; 4. long long lcm(long long X, long long Y) 5. { 6. return (X/__gcd(X,Y)*Y); 7. } 8. int main(){ 9. ios::sync_with_stdio(0); 10. cin.tie(0);cout.tie(0); 11. cin>>a>>b>>c>>d; 12. cout
Bài 2. Cho dãy số nguyên dương a1, a2, … , an và số nguyên K. Hãy đếm xem có bao nhiêu cặp chỉ số i, j thỏa mãn: o 1  i=k) res++ Chương trình: 1. #include 2. using namespace std; 3. #define li long long 4. li n, k,i,j,res, a[1005]; 5. li lcm(li a, li b) { return a / __gcd(a, b) * b; } 6. int main() { 7. cin >> n >> k; 8. for(i=1; i> a[i]; 9. for(i=1; i
Bài 3. Cho 3 số nguyên dương a, b, c. Tính ab mod c. Input: Gồm một dòng duy nhất chứa 3 số nguyên dương a, b và c. Output: In ra kết quả bài toán Ví dụ: Input Output 533 2  30% số test có a, b, c ≤ 10  30% số test khác có a, b, c ≤ 106  40% số test còn lại có a, b, c ≤ 109 Thuật toán: Với a, b, c ≤ 10. Ta cần một biến ans = 1, sau đó chạy một biến i từ 1 → b và tăng biến ans = ans * a, kết quả chính là (ans % c). Với a, b, c ≤ 106. Một tính chất toán học đúng đắn đó là : (a.b) % c = (a % c) . (b % c) Do đó đầu tiên ta gán một biến ans = 1, sau đó chạy một biến i từ 1 → b và cứ mỗi lần ta lại gán ans = (ans*a) % c. Việc mod c ngay lập tức sẽ khiên cho giá trị ans luôn nhỏ hơn c và sẽ tránh được việc tràn số. Cả 2 trường hợp trên độ phức tạp thuật toán là O(b). Với a, b, c ≤ 109. Ở đây ta sẽ dùng đến thuật toán chia để trị, ta có tính chất:  ab % c = (ab/2 % c) . (ab/2 % c) nếu b chẵn.  ab % c = (ab/2 % c) . (ab/2 % c) .a nếu b lẻ. gọi F(a, b, c) = ab % c sẽ gọi đến hàm F(a, b/2, c). Do đó ta có thể dùng đệ qui để tính (ab % c) với đpt O(log(b)). Chương trình: 1. #include 2. using namespace std; 3. long long a,b,c; 4. long long pw(long long A,long long B,long long C) 5. { 6. if (B==0) return 1; 7. long long tmp=pw(A,B/2,C); 8. tmp=(tmp*tmp)%C; 8
9. if (B%2==1) tmp=(tmp*A)%C; 10. return tmp; 11. } 12. int main() 13. { 14. ios::sync_with_stdio(0); 15. cin.tie(0);cout.tie(0); 16. cin>>a>>b>>c; 17. cout
Với a, b ≤ 10100000. Ta đọc hai số a và b dưới dạng xâu (string). Nhận thấy a chỉ cần lấy chữ số cuối cùng (%10), và b chỉ cần lấy 2 chữ số cuối cùng. Ta thấy tất cả mọi số nguyên dương khi mũ 4 lên thì sẽ có chữ số tận cùng là 0, 1, 5 hoặc 6. Sau đó thì những số có chữ số tận cùng là 0, 1, 5, 6 này có mũ bao nhiêu thì chữ số tận cùng cũng không đổi. Dựa vào tính chất đó để làm được subtask này. Ta chỉ lấy 2 chữ số tận cùng của b để tính cho nên độ phức tạp sẽ rất nhỏ. Chương trình: 1. #include 2. using namespace std; 3. string a,b; 4. long long x,y; 5. long long pw(long long A,long long B,long long C){ 6. if (B==0) return 1; 7. long long tmp=pw(A,B/2,C); 8. tmp=(tmp*tmp)%C; 9. if (B%2==1) tmp=(tmp*A)%C; 10. return tmp; 11. } 12. int main(){ 13. ios::sync_with_stdio(0); 14. cin.tie(0);cout.tie(0); 15. cin>>a>>b; 16. x=y=0; 17. x=a[a.size()-1]-48; 18. if (b.size()==1) y=b[b.size()-1]-48; 19. else y=(b[b.size()-2]-48)*10+b[b.size()-1]-48; 20. cout
 40% số test có a, b ≤ 1000  30% số test khác có a, b ≤ 105  30% số test còn lại có a, b ≤ 107 Thuật toán: Với a, b ≤ 1000. Ta chỉ việc chạy một biến i từ a → b, với mỗi biến i kiểm tra chúng có phải là số nguyên tố hay không mất O(i), do đó đpt bài toán được tính trong trường hợp xấu nhất là O((b – a).b). Với a, b ≤ 105. Ta cũng chạy một biến i từ a → b, với mỗi biến i kiểm tra chúng có phải là số nguyên tố hay không cải tiến thêm là O(√𝑖), do đó đpt bài toán được tính trong trường hợp xấu nhất là O((b – a).√𝑏). Với a, b ≤ 107. Ở đây ta cần sử dụng kiến thức sàng nguyên tố, ta sẽ dựng sàng nguyên tố với đpt O(107), sau đó sẽ kiểm tra một số có phải là số nguyên tố hay không với đpt O(1). Như vậy đpt bài toán được tính lúc này là O(107 + (b –a)). Chương trình: 1. #include 2. #define LL long long 3. using namespace std; 4. const int maxn=1e7; 5. bool F[maxn+5]; 6. int a,b,ans; 7. void sieve(){ 8. memset(F,true,sizeof(F)); 9. for(int i=2;i*ia>>b; 17. ans=0; 18. for(int i=a;i
Bài 6. Số thân thiện là những số mà số đó và số đảo ngược của số đó nguyên tố cùng nhau. Đếm xem trong đoạn [a, b] có bao nhiêu số thân thiện. Input: Gồm một dòng duy nhất chứa 2 số nguyên dương a và b (a ≤ b ≤ 30000). Output: Đưa ra số lượng số thân thiện trong đoạn [a, b]. Ví dụ: Input Output 20 30 3 Thuật toán: Bài toán này ta cứ làm theo đề, chỉ việc chạy một biến i từ a → b, sau đó với mỗi biến i làm một hàm đảo ngược số i lại, rồi tính gcd(i, rev(i)), nếu chúng nguyên tố cùng nhau thì ta tăng kết quả lên 1 → O((b – a).log(b)). Chương trình: 1. #include 2. using namespace std; 3. int rev( int n ) 4. { 5. int res = 0; 6. while(n) { 7. res = res * 10 + n % 10; 8. n /= 10; 9. } 10. return res; 11. } 12. int gcd( int a, int b ) { 13. while(b) { 14. int t = b; 15. b = a % b; 16. a = t; 17. } 18. return a; 19. } 20. int main() { 21. int a, b; 12
22. cin>>a>>b; 23. int count = 0; 24. for( int i = a; i
5. void init() { a. for( int i = 1; i l>>r; 11. int res = 0; 12. for( int i = l; i i; 13. cout
Với N ≤ 1015. Ở đây ta cần tính xem có bao nhiêu TSNT 5 trong (N!). Đây là bài toán đếm xem (N!) có chứa bao nhiêu TSNT P. Ta sẽ có công thức tính như sau: 𝑁 𝑁 𝑁 SUM (P) = [ ] +[ 2 ] + … + [ 𝑘 ] (pk > N). Công thức này ta có thể giải thích 𝑃 𝑃 𝑃 𝑁 như sau: [ ] là số số chia hết cho P từ 1 → N, ta sẽ cộng vào kết quả bài toán, nhưng 𝑃 vẫn chưa hết, những số chia hết cho P2 sẽ phải được tính 2 lần như vậy, tiếp tục cộng 𝑁 𝑁 thêm [ 2 ] và cứ như thế cho đến lúc [ 𝑘 ] = 0. Ta có thể tính nhanh công thức này với 𝑃 𝑃 đpt O(logp(N)). Kết quả bài toán chính là SUM(5). Chương trình: 1. #include 2. #define LL long long 3. using namespace std; 4. LL n; 5. LL cnt(LL N,LL P){ 6. LL sum=0; 7. while (N>0){ 8. sum+=(N/P); 9. N/=P; 10. } 11. return sum; 12. } 13. int main() 14. { 15. ios::sync_with_stdio(0); 16. cin.tie(0);cout.tie(0); 17. cin>>n; 18. cout
Input Output 2 140 7 14 3  50% số test có T, N ≤ 103  50% số test còn lại có T, N ≤ 105 Thuật toán: Với N, T ≤ 1000. Ta duyệt thông thường, đpt O(N.T). 𝑁.(𝑁+1).(2𝑁+1) Với N, T ≤ 105. Ta sẽ chứng minh rằng: 12 + 22 + … + N2 = 6 Ta có: X = X.(X – 1) + X 2 S = 12 + 22 +… + N2 = 0.1 + 1 + 1.2 +2 + … + N.(N – 1) + N = (0.1 + 1.2 + … + N.(N – 1)) + (1 + 2 + … + N) 𝑁.(𝑁+1) =P+ (trong đó P = 1.2 + … + N.(N – 1)) 2 Ta lại có 3P = 1.2.3 + 2.3.3 + … + N.(N – 1).3 = 1.2.3 + 2.3.4 – 1.2.3 +… +(N – 1).N.(N+1) – (N – 2).(N – 1).N = (N – 1).N.(N+1) (𝑁−1).𝑁.(𝑁+1)  P= 3 𝑁.(𝑁+1) (𝑁−1).𝑁.(𝑁+1) 𝑁.(𝑁+1) 𝑁.(𝑁+1).(2𝑁+1)  S=P+ = + = . 2 3 2 6 𝑁.(𝑁+1).(2𝑁+1) Vậy với mỗi số nguyên dương N ta sẽ đưa ra công thức , sẽ 6 chỉ mất O(1) với mỗi truy vấn, do đó đpt bài toán sẽ là O(T). Chương trình: 1. #include 2. #define LL long long 3. using namespace std; 4. LL T,n; 5. int main(){ 6. cin>>T; 7. while (T--){ 8. cin>>n; 9. cout
10. } 11. return 0; 12. } Bài 10. Input: Gồm một dòng chứa số nguyên n (1  n  1018 ) Ouput: Đưa ra một số nguyên, đó là là số lượng các số từ 1 tới n, thỏa mãn: số đó không chia hết cho bất kỳ số nào trong các số từ 2 đến 10 Ví dụ: Input Output 12 2 Từ 1 tới 12 có 2 số không chia hết cho bất kỳ số nào từ 2 đến 10, đó là: 1 và 11 Thuật toán: Số lượng các số từ 1 tới n không chia hết cho bất kỳ số nào từ 2 đến 10 bằng số lượng các số từ 1 tới n trừ đi số lượng các số từ 1 tới n chia hết cho một vài số từ 2 đến 10 Tập các số từ 1 tới n chia hết bởi một vài số từ 2 đến 10 có thể quan niệm là hợp của tập các số từ 1 tới n chia hết cho 2, tập các số từ 1 tới n chia hết cho 3, và cho tới 10 Lưu ý rằng tập của các số chia hết cho 4,6,8 là tập con của tập các số chia hết cho 2, và tập của các số chia hết cho 6,9 là tập con của tập các số chia hết cho 3. Vì vậy ta chỉ cần 2,3,5,7 là đủ. Số lượng các số từ 1 tới n chia hết cho một vài số 2,3,5,7 có thể được tính bằng nguyên lý bù trừ Số lượng các số từ 1 tới n chia hết cho 2 là [n/2] Số lượng các số từ 1 tới n chia hết cho 2 và 3 là [n/(2.3)] Cứ thế. Công thức cuối cùng là n  [n / 2]]n / 3]  [n / 5]  [n / 7]  [n / 2.3]  [n / (2.5)]  [n / (2.7)] [n / (3.5)]  [n / (3.7)]  [n / (5.7)]  [n / (2.3.5)]  [n / (2.3.7)] [n / (2.5.7)]  [n / (3.5.7)]  [n / (2.3.5.7)] 17
Chương trình: 1. #include 2. using namespace std; 3. int main() 4. { freopen ("chiahet.inp","r",stdin); 5. freopen("chiahet.out","w",stdout); 6. long long s,n; 7. cin>>n; 8. s=n-n/2-n/3-n/7-n/5+n/6+n/14+n/10+n/21+n/35+n/15- n/42-n/70-n/30-n/105+n/210; 9. cout
Do đó kết quả sẽ là F[b] – F[a – 1], mỗi cặp (a, b) ta sẽ đưa ra kết quả với tốc độ O(1), do đó đpt bài toán sẽ là O(T). Chương trình: 1. #include 2. using namespace std; 3. long long a,b,c; 4. long long pw(long long A,long long B,long long C) 5. { 6. if (B==0) return 1; 7. long long tmp=pw(A,B/2,C); 8. tmp=(tmp*tmp)%C; 9. if (B%2==1) tmp=(tmp*A)%C; 10. return tmp; 11. } 12. int main() 13. { 14. ios::sync_with_stdio(0); 15. cin.tie(0);cout.tie(0); 16. cin>>a>>b>>c; 17. cout