Tiêu đề Chuyen de 2 - SGK chuyen tin quyen 1.pdf ✅

13 Chuyên ñề 2 CÁC KIẾN THỨC CƠ BẢN 1. Hệ ñếm Hệ ñếm ñược hiểu là tập các kí hiệu và quy tắc sử dụng tập các kí hiệu ñó ñể biểu diễn và xác ñịnh giá trị các số. Trong hệ ñếm cơ số 9 9 & 1, các kí hiệu ñược dùng có các giá trị tương ứng 0, 1, . . , 9 1. Giả sử : có biểu diễn: 1 2 ... 1 0 , 1 2 ... trong ñó , 1 số các chữ số bên trái, là số các chữ số bên phải dấu phân chia phần nguyên và phần phân của số : và các ; phải thoả mãn ñiều kiện 0 + < = 9 + ; + . Khi ñó giá trị của số : ñược tính theo công thức: : ( 79 7 , 7> 9 7> ,. . . , 9 , > 9 > , . . . , >.9 >. 1 Chú ý: ðể phân biệt số ñược biểu diễn ở hệ ñếm nào người ta viết cơ số làm chỉ số dưới của số ñó. Ví dụ: :? là biểu diễn : ở hệ ñếm 9. 1.1. Các hệ ñếm thường dùng: Hệ thập phân (hệ cơ số 10) dùng 10 kí hiệu 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Ví dụ: 28,910 = 2 × 101 + 8 × 100 + 9 × 10-1 Hệ nhị phân (hệ cơ số 2) chỉ dùng hai kí hiệu 0, 1 Ví dụ: 102= 1 × 21 + 0 × 20 = 210 101,12= 1 × 22 + 0 × 21 + 1 × 20 + 1 × 2-1 =5,5 Hệ cơ số mười sáu, còn gọi là hệ hexa, sử dụng các kí hiệu 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, trong ñó A, B, C, D, E, F có các giá trị tương ứng 10, 11, 12, 13, 14, 15 trong hệ thập phân Ví dụ: AF016 = 10 × 162 + 15 × 161 + 0 × 160 =280010
14 1.2. Chuyển ñổi biểu diễn số ở hệ thập phân sang hệ ñếm cơ số khác ðể chuyển ñổi biểu diễn một số ở hệ thập phân sang hệ ñếm cơ số khác, trước hết ta tách phần nguyên và phần phân rồi tiến hành chuyển ñổi từng phần, sau ñó ghép lại. Chuyển ñổi biểu diễn phần nguyên: Từ (1) ta lấy phần nguyên: @ ( 79 7 , 7> 9 7> ,. . . , AB 2 đó 0 + < = 9. Do 0 + = 9 nên khi chia @ cho 9 thì phần dư của phép chia ñó là 0 còn thương số @1 sẽ là: 9 1 , 19 2 ,. . . , 1 . Tương tự 1 là phần dư của phép chia @1 cho 9. Quá trình ñược lặp cho ñến khi nhận ñược thương bằng 0. Chuyển ñổi biểu diễn phần phân: Từ (1) ta lấy phần sau dấu phẩy: E ( > 9 > , . . . , >.9 >.. E1 ( E 9 ( > , >9 > , . . . , >.9 >.> Ta nhận thấy 1 chính là phân nguyên của kết quả phép nhân, còn phần phân của kết quả là E2 ( >9 > , . . . , >.9 >.> . Quá trình ñược lặp cho ñến khi nhận ñủ số chữ số cần tìm. 2. Số nguyên tố Một số tự nhiên F F & 1 là số nguyên tố nếu F có ñúng hai ước số là 1 và F. Ví dụ các số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, ... 2.1. Kiểm tra tính nguyên tố a) ðể kiểm tra số nguyên dương & 1 có là số nguyên tố không, ta kiểm tra xem có tồn tại một số nguyên 2 + + 1) mà là ước của ( chia hết ) thì không phải là số nguyên tố, ngược lại là số nguyên tố. Nếu & 1 không phải là số nguyên tố, ta luôn có thể tách ( à 2 + + + 1. Vì + ( nên + √. Do ñó, việc kiểm tra với từ 2 ñến 1 là không cần thiết, mà chỉ cần kiểm tra từ 2 ñến √. function is_prime(n:longint):boolean; var k :longint; begin if n=1 then exit(false);
15 for k:=2 to trunc(sqrt(n)) do if (n mod k=0) then exit(false); exit(true); end; Hàm is_prime(n) trên tiến hành kiểm tra lần lượt từng số nguyên trong ñoạn [2, √], ñể cải tiến, cần giảm thiểu số các số cần kiểm tra. Ta có nhận xét, ñể kiểm tra số nguyên dương & 1 có là số nguyên tố không, ta kiểm tra xem có tồn tại một số nguyên tố 2 + + √) mà là ước của thì không phải là số nguyên tố, ngược lại là số nguyên tố. Thay vì kiểm tra các số là nguyên tố ta sẽ chỉ kiểm tra các số có tính chất giống với tính chất của số nguyên tố, có thể sử dụng một trong hai tính chất ñơn giản sau của số nguyên tố: 1) Trừ số 2 và các số nguyên tố là số lẻ. 2) Trừ số 2, số 3 các số nguyên tố có dạng 6 K 1 (vì số có dạng 6 K 2 thì chia hết cho 2, số có dạng 6 K 3 thì chia hết cho 3). Hàm is_prime2(n) dưới ñây kiểm tra tính nguyên tố của số bằng cách kiểm tra xem có chia hết cho số 2, số 3 và các số có dạng 6 K 1 trong ñoạn [5, √ ]. function is_prime2(n:longint):boolean; var k,sqrt_n:longint; begin if (n=2)or(n=3) then exit(true); if (n=1)or(n mod 2=0)or(n mod 3=0) then exit(false); sqrt_n:=trunc(sqrt(n)); k:=-1; repeat inc(k,6); if (n mod k=0)or(n mod (k+2)=0) then break; until k>sqrt_n; exit(k>sqrt_n); end; b) Phương pháp kiểm tra số nguyên tố theo xác suất Từ ñịnh lí nhỏ Fermat: nếu F là số nguyên tố và / là số tự nhiên thì / L F ( / Ta có cách kiểm tra tính nguyên tố của Fermat:
16 nếu 2 7 M 2 thì không là số nguyên tố nếu 2 7 ( 2 thì nhiều khả năng là số nguyên tố Ví dụ: 2 N 9 ( 512 9 ( 8 M 2, do ñó số 9 không là số nguyên tố. 2 3 ( 8 3 ( 2, do ñó nhiều khả năng 3 là số nguyên tố, thực tế 3 là số nguyên tố. 2 11 ( 2048 11 ( 2, do ñó nhiều khả năng 11 là số nguyên tố, thực tế 11 là số nguyên tố. 2.2. Liệt kê các số nguyên tố trong ñoạn Q, RS Cách thứ nhất là thử lần lượt các số trong ñoạn Q1, :S, rồi kiểm tra tính nguyên tố của . procedure generate(N:longint); var m :longint; begin for m:=2 to N do if is_prime(m) then writeln(m); end; 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 bỏ trước những số không phải là số nguyên tố và không cần kiểm tra các số này. Cách thứ hai là sử dụng sàng số nguyên tố, như sàng Eratosthene, liệt kê ñược các số nguyên tố nhanh, tuy nhiên nhược ñiểm của cách này là tốn nhiều bộ nhớ. Cách làm ñược thực hiện như sau: Trước tiên xoá 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ố, xoá tất cả các bội của 2 ra khỏi bảng. Số ñầu tiên không bị xoá sau số 2 (số 3) là số nguyên tố, xoá các bội của 3... Giải thuật tiếp tục cho ñến khi gặp số nguyên tố lớn hơn √: thì dừng lại. Tất cả các số chưa bị xoá là số nguyên tố. {$M 1100000} procedure Eratosthene(N:longint); const MAX = 1000000; var i,j :longint; Prime :array [1..MAX] of byte; begin