Mở đầu, Nội dung và Kết luận. Trong phần Nội dung (và cũng là phần chính của chuyên đề) chúng tôi đề cập tới các vấn đề chính: Số nguyên tố, Ước số, Bội số, Số Fibonacci, Số Catalan, Xử lí số nguyên lớn,. Do chuyên đề này là các bài toán số học nên kiến thức cơ sở sẽ được ứng dụng trong từng bài tập cụ thể. Về mặt lí thuyết số học có rất nhiều tài liệu đã trình bày, ngay cả trong cuốn tài liệu giáo khoa chuyên Tin quyển 1 đã hệ thống rất cụ thể.
Chuyên đề là sự sưu tầm, chọn lọc, sắp xếp và hệ thống những vấn đề cơ bản của các bài toán số học theo một mạch kiến thức nhất định dựa trên một số nguồn tài liệu đã có. Cùng với đó, chúng tôi có đưa ra những phân tích, đánh giá để làm sáng tỏ cho mỗi vấn đề được đề cập tới. Với cách tiếp cận mở như vậy, hy vọng chuyên đề này sẽ giúp các em học sinh có được một hệ thống những kiến thức cần thiết, các thầy cô giáo có một chuyên đề chuyên môn bổ ích và thiết thực. Số nguyên tố 1.
Định nghĩa Một số tự nhiên p (p>1) là số nguyên tố nếu p có đúng hai ước số là 1 và p. Ví dụ các số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, … 1. Kiểm tra tính nguyên tố theo định nghĩa. Ý tưởng chính để kiểm tra số nguyên dương N (N>1) có là số nguyên tố hay không, ta kiểm tra xem có tồn tại số nguyên mà k là ước của N (N chia hết cho k) thì N không phải là số nguyên tố, ngược lại N là số nguyên tố.
bool IsPrime(int N) { if (N < 2) return flase; for(int i = 2; i < sqrt(N); i++) if(N%i==0) return flase; return true; } Tuy nhiên ta thấy cách này không hiệu quả khì thời gian kiểm tra lâu. Cải tiến kiểm tra tính nguyên tố của số N bằng cách kiểm tra xem N có chia hết cho số 2, số 3 và các số có dạng trong đoạn. bool IsPrime (int N) { if (N==2 || N==3) return true; if (N==1 || N%2==0 || N%3==0) return false; int k=-1; while (k<=int(sqrt(N))) { k+=6; if (N%k==0 || N% (k+2)==0) break; } return k>int(sqrt(N)); } 2 skkn 1. Kiểm tra số nguyên tố theo xác suất 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. m n Định lý Fermat còn được tổng quát hóa bởi Định lý Euler: với modulo n bất kỳ (n) và số nguyên a bất kỳ là số nguyên tố cùng nhau với n, ta có: a 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.
Liệt kê các số nguyên tố trong đoạn [1,N]. Thử lần lượt các số m trong đoạn [1,N], rồi kiểm tra tính nguyên tố của m. void OutPrime(int N) { for(int i = 2; i <= N; i++) if(IsPrime(i)) printf("%d\t", i); } Ta thấy: Cách này đơn giản nhưng chạy chậm, để cải tiến có thể sử dụng các tính chất của số nguyên tố để loại trước những số không phải là số nguyên tố và không cần phải kiểm tra trước các số này. Sử dụng sàng số nguyên tố sàng Eratosthene.
Giả sử tất cả đều là số nguyên tố, trước tiên xóa bỏ số 1 ra khỏi tập các số nguyên tố. Số tiếp theo số 1 là số 2, là số nguyên tố, xóa tất cả các bội số của 2 ra khỏi bảng, xét lên 3, loại tất cả các bội số của 3,… thuật toán tiếp tục cho đến khi gặp số nguyên tố lớn hơn thì dừng lại. Kết thúc quá trình các số chưa bị loại là số nguyên tố. 3 skkn void Eratosthene(int N) { int a[1000] = {0}; //Tạo mảng và gán tất cả bằng 0 for(int i = 2; i*i <= N;i++) if(!a[i]) //Nếu là số nguyên tố //Duyệt các phần tử là bội số của i for(int j = i*i; j <= N; j+=i) a[j]=1; //Đánh dấu các phần tử là bội số.
//In các phần tử là số nguyên tố ra màn hình for (int i=2;i<=N;i++) if(!a[i]) printf("%d ",i); } 2. ƯỚC SỐ, BỘI SỐ 2. Số các ước của một số Giả sử N được phân tích thành thừa số nguyên tố như sau: Ước số của N có dạng: trong đó. Do đó: Số các ước của N là:.
Ví dụ: , số các ước của 100 là: (các ước của số đó là: 1, 2, 3, 4, 5, 10, 20, 50, 100). Tổng các ước của một số Đặt Gọi là tổng các ước của t, ta có: 4 skkn Ví dụ: Tổng các ước của 24 là: 2. Ước chung lớn nhất của hai số Ước số chung lớn nhất (USCLN) của hai số được tính theo thuật toán Euclid int gcd(int a, int b) { int tmp; while(b != 0) { tmp = a % b; a = b; b = tmp; } return a; } Chú ý: Để có thể sử dụng hàm tìm UCLN trong C++ ta cần thêm thư viện algorithm. Ví dụ: int main(){ int a = 5, b = 9; printf("\ngcd(%d, %d) = %d", a, b, std::__gcd(a,b)); } 2.
Bội chung nhỏ nhất của hai số Bội số chung nhỏ nhất (BSCNN) của hai số được tính theo công thức: 5 skkn 3. Dãy số Fibonacci Dãy số Fibonacci được xác định bởi các công thức sau: với n ≥ 2 Một số phần tử đầu tiên của dãy số Fibonacci: n 0 1 2 3 4 5 6 … Fibonaccin 0 1 1 2 3 5 8 … Số Fibonacci là đáp án của các bài toán: a) Bài toán cổ về sự sinh sản của các cặp thỏ với các giả thiết như sau: - Các con thỏ không bao giờ chết; - Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái); - Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới. Giả sử từ đầu tháng 1 có một cặp mới thì đến giữa tháng thứ n sẽ có bao nhiêu cặp? b) Đếm số cách xếp n-1 quân domino kích thước phủ kín bảng có kích thước. Hàm tính số Fibonaci thứ n bằng phương pháp lặp sử dụng công thức với.
Dãy số CATALAN Số Catalan được xác định bởi công thức sau: với n ≥ 0. Một số phần tử đầu tiên của dãy số Catalan là: n 0 1 2 3 4 5 6 … Catalann 1 1 2 5 14 42 132 … Số Catalan là đáp án của các bài toán: a) Có bao nhiêu cách khác nhau đặt n dấu ngoặc mở và n dấu ngoặc đóng đúng đắn? Ví dụ: n=3 ta có 5 cách sau: ((())), (()()), (())(), ()(()), ()()() b) Có bao nhiêu cây nhị phân khác nhau có đúng n+1 lá? Ví dụ: n=3 7 skkn c) Cho một đa giác lồi (n+2) đỉnh, ta chia thành các tam giác bằng nhau vẽ các đường chéo không cắt nhau trong đa giác. Hỏi có bao nhiêu cách chia như vậy? Ví dụ: n=4 5. Xử lí số nguyên lớn 5.
Cộng 2 số nguyên lớn Phân tích thuật toán - Bước 1: Chuẩn hóa hai xâu a, b để có độ dài bằng nhau. Nếu xâu nào có độ dài ngắn hơn thì thêm các ‘0’ vào đầu xâu đó. - Bước 2: Duyệt từ cuối hai xâu về đầu xâu: + Tạo xâu kết quả c=a; + Tách từng phần tử của hai xâu chuyển sang kiểu số; + Tính tổng: tổng = số 1 + số 2 + nhớ (ban đầu nhớ bằng 0); nhớ = tổng / 10; tổng = tổng % 10; + Chuyển đổi giá trị tổng tính được sang ký tự rồi gán vào xâu kết quả. + Lưu ý cộng thêm giá trị nhớ lần cuối nếu nhớ khác ‘0’.
Chương trình tham khảo string Congxau(string a, string b) { string c; 8 skkn long n1=a. Trừ 2 số nguyên lớn (Trừ số lớn cho số bé) Phân tích thuật toán - Bước 1: Chuẩn hóa hai xâu a, b để có độ dài bằng nhau. Nếu xâu nào có độ dài ngắn hơn thì thêm các ‘0’ vào đầu xâu đó. - Bước 2: Duyệt từ cuối hai xâu về đầu xâu: + Tạo xâu kết quả c=a; + Tách từng phần tử của hai xâu chuyển sang kiểu số; + Tính hiệu: hiệu = số 1 - số 2 - mượn (ban đầu mượn bằng 0); Nếu hiệu<0 thì {hiệu=hiệu+10; mượn=1;} Nếu hiệu>0 thì mượn =0; + Chuyển đổi giá trị hiệu tính được sang ký tự rồi gán vào xâu kết quả.
9 skkn + Xử lý xâu kết quả nếu xâu có độ dài lớn hơn 1 mà phần tử đầu tiên của mảng xâu là ‘0’. Chương trình tham khảo string Truxau(string a, string b) { string c=""; long n1=a. Nhân một số nguyên lớn với một nguyên số nhỏ Phân tích thuật toán - Bước 1: Duyệt từ cuối xâu số lớn về đầu xâu - Bước 2: + Tách từng phần tử của xâu chuyển sang kiểu số và tính tích: tích = số nhỏ * tg + nhớ (tg là số được tách từ xâu số lớn); nhớ = tích /10; Tích = tích % 10; + Chuyển đổi giá trị tích tính được sang ký tự rồi gán vào xâu kết quả. 10 skkn + Lưu ý cộng thêm giá trị nhớ lần cuối nếu nhớ khác ‘0’.
Chương trình tham khảo string Nhan1so(string a, int k) { string b; long i,Nho=0,Tich; for(i=a. Nhân 2 số nguyên lớn Phân tích thuật toán - Duyệt từ cuối xâu a về đầu xâu. - Tách từng phần tử của xâu a nhân với xâu b (Thuật toán nhân với số nhỏ). - Cộng liên tiếp các kết quả thu được (lưu ý trước khi cộng 2 xâu thêm ký tự “0” vào sau xâu thứ 2).
- Xử lý các ký tự “0” trước xâu sau khi cộng. Chương trình tham khảo string Nhanxau(string a, string b) { 11 skkn string x,Tg1="0",Tg2,c; long i,j=0; for(i=b.length(),j,'0'); j++; c=Congxau(Tg1,Tg2); Tg1=c; } return c; } 5. Chia số nguyên lớn cho số nguyên nhỏ Phân tích thuật toán - Bước 1: Duyệt từ đầu xâu số nguyên lớn - Bước 2: + Tách từng phần tử của xâu đem chia cho số nguyên nhỏ: chia = số + dư * 10 (dư ban đầu bằng 0); thương = chia / số nhỏ; dư = chia % 10; + Cộng liên tiếp các thương được phần nguyên; + Lưu lại giá trị dư cuối cùng được phần dư; + Lưu ý: xóa các “0” ở đầu mảng xâu kết quả.