Ktl-icon-tai-lieu

Hướng dẫn ôn tập pascal

Được đăng lên bởi Nguyễn Lê Thái Hoàng
Số trang: 20 trang   |   Lượt xem: 813 lần   |   Lượt tải: 2 lần
Hướng dẫn ôn tập Lập trình Pascal cơ bản và nâng cao

CÁC THUẬT TOÁN VỀ SỐ
THUẬT TOÁN KIỂM TRA SỐ NGUYÊN TỐ
Thuật toán của ta dựa trên ý tưởng: nếu n >1 không chia hết cho số nguyên nào trong tất
cả các số từ 2 đến n thì n là số nguyên tố. Do đó ta sẽ kiểm tra tất cả các số nguyên từ 2
đến có round(sqrt(n)), nếu n không chia hết cho số nào trong đó thì n là số nguyên tố.
Nếu thấy biểu thức round(sqrt(n)) khó viết thì ta có thể kiểm tra từ 2 đến n div 2.
Hàm kiểm tra nguyên tố nhận vào một số nguyên n và trả lại kết quả là true (đúng) nếu n là
nguyên tố và trả lại false nếu n không là số nguyên tố.
function ngto(n:integer):boolean;
var i:integer;
begin
ngto:=false;
if n<2 then exit;
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then exit; {nếu n chia hết cho i thì n không là nguyên tố => thoát luôn}
ngto:=true;
end;

Chú ý: Dựa trên hàm kiểm tra nguyên tố, ta có thể tìm các số nguyên tố từ 1 đến n bằng
cách cho i chạy từ 1 đến n và gọi hàm kiểm tra nguyên tố với từng giá trị i.
THUẬT TOÁN TÍNH TỔNG CÁC CHỮ SỐ CỦA MỘT SỐ NGUYÊN
Ý tưởng là ta chia số đó cho 10 lấy dư (mod) thì được chữ số hàng đơn vị, và lấy số đó div
10 thì sẽ được phần còn lại. Do đó sẽ chia liên tục cho đến khi không chia được nữa (số đó
bằng 0), mỗi lần chia thì được một chữ số và ta cộng dồn chữ số đó vào tổng.
Hàm tính tổng chữ số nhận vào 1 số nguyên n và trả lại kết quả là tổng các chữ số của nó:
function tongcs(n:integer): integer;
var s : integer;
begin
s := 0;
while n <> 0 do begin
s := s + n mod 10;
n := n div 10;
end;
tongcs := s;
end;

Chú ý: Tính tích các chữ số cũng tương tự, chỉ cần chú ý ban đầu gán s là 1 và thực hiện
phép nhân s với n mod 10.
THUẬT TOÁN EUCLIDE TÍNH UCLN
Ý tưởng của thuật toán Euclide là UCLN của 2 số a,b cũng là UCLN của 2 số b và a mod
b, vậy ta sẽ đổi a là b, b là a mod b cho đến khi b bằng 0. Khi đó UCLN là a.
Hàm UCLN nhận vào 2 số nguyên a,b và trả lại kết quả là UCLN của 2 số đó.
function UCLN(a,b: integer): integer;
var r : integer;
begin
while b<>0 do begin

Nguyễn Thanh Tùng - Khoa CNTT, Đại học Sư phạm Hà Nội

1

Hướng dẫn ôn tập Lập trình Pascal cơ bản và nâng cao
r := a mod b;
a := b;
b := r;
end;
UCLN := a;
end;

Chú ý: Dựa trên thuật toán tính UCLN ta có thể kiểm tra được 2 số nguyên tố cùng nhau
hay không. Ngoài ra cũng có thể dùng để tối giản phân số bằng cách chia cả tử và mẫu cho
UCLN.
THUẬT TOÁN TÍNH TỔNG CÁC ƯỚC SỐ CỦA MỘT SỐ NGUYÊN
Để tính tổng các ước số của số n, ta cho i chạy từ 1 đến n div 2, nếu n chia hết cho số nào
thì ta cộng số...
Hướng dẫn ôn tập Lập trình Pascal cơ bản và nâng cao
CÁC THUẬT TOÁN VỀ SỐ
THUẬT TOÁN KIỂM TRA SỐ NGUYÊN TỐ
Thuật toán của ta dựa trên ý tưởng: nếu n >1 không chia hết cho số nguyên nào trong tất
cả các số từ 2 đến
n
thì n là số nguyên tố. Do đó ta sẽ kiểm tra tất cả các số nguyên từ 2
đến có round(sqrt(n)), nếu n không chia hết cho số nào trong đó thì n là số nguyên tố.
Nếu thấy biểu thức round(sqrt(n)) khó viết thì ta có thể kiểm tra từ 2 đến n div 2.
Hàm kiểm tra nguyên tố nhận vào một số nguyên n và trả lại kết quả là true (đúng) nếu n là
nguyên tố và trả lại false nếu n không là số nguyên tố.
function ngto(n:integer):boolean;
var i:integer;
begin
ngto:=false;
if n<2 then exit;
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then exit; {nếu n chia hết cho i thì n không là nguyên tố => thoát luôn}
ngto:=true;
end;
Chú ý: Dựa trên hàm kiểm tra nguyên tố, ta thể tìm các số nguyên tố từ 1 đến n bằng
cách cho i chạy từ 1 đến n và gọi hàm kiểm tra nguyên tố với từng giá trị i.
THUẬT TOÁN TÍNH TỔNG CÁC CHỮ SỐ CỦA MỘT SỐ NGUYÊN
Ý tưởng là ta chia số đó cho 10 lấy dư (mod) thì được chữ số hàng đơn vị, và lấy số đó div
10 thì sẽ được phần còn lại. Do đó sẽ chia liên tục cho đến khi không chia được nữa (số đó
bằng 0), mỗi lần chia thì được một chữ số và ta cộng dồn chữ số đó vào tổng.
Hàm tính tổng chữ số nhận vào 1 số nguyên n và trả lại kết quả là tổng các chữ số của nó:
function tongcs(n:integer): integer;
var s : integer;
begin
s := 0;
while n <> 0 do begin
s := s + n mod 10;
n := n div 10;
end;
tongcs := s;
end;
Chú ý: Tính tích các chữ số cũng tương tự, chỉ cần chú ý ban đầu gán s 1 thực hiện
phép nhân s với n mod 10.
THUẬT TOÁN EUCLIDE TÍNH UCLN
Ý tưởng của thuật toán Euclide UCLN của 2 số a,b cũng UCLN của 2 số b a mod
b, vậy ta sẽ đổi a là b, b là a mod b cho đến khi b bằng 0. Khi đó UCLN là a.
Hàm UCLN nhận vào 2 số nguyên a,b và trả lại kết quả là UCLN của 2 số đó.
function UCLN(a,b: integer): integer;
var r : integer;
begin
while b<>0 do begin
Nguyễn Thanh Tùng - Khoa CNTT, Đại học Sư phạm Hà Nội
1
Hướng dẫn ôn tập pascal - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Hướng dẫn ôn tập pascal - Người đăng: Nguyễn Lê Thái Hoàng
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
20 Vietnamese
Hướng dẫn ôn tập pascal 9 10 790