Violet
Giaoan

Tin tức thư viện

Khắc phục hiện tượng không xuất hiện menu Bộ công cụ Violet trên PowerPoint và Word

12099162 Kính chào các thầy, cô. Khi cài đặt phần mềm , trên PowerPoint và Word sẽ mặc định xuất hiện menu Bộ công cụ Violet để thầy, cô có thể sử dụng các tính năng đặc biệt của phần mềm ngay trên PowerPoint và Word. Tuy nhiên sau khi cài đặt phần mềm , với nhiều máy tính sẽ...
Xem tiếp

Quảng cáo

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (024) 66 745 632
  • 096 181 2005
  • contact@bachkim.vn

Tìm kiếm Giáo án

Thuật toán Pascal rất hay!

Wait
  • Begin_button
  • Prev_button
  • Play_button
  • Stop_button
  • Next_button
  • End_button
  • 0 / 0
  • Loading_status
Nhấn vào đây để tải về
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Nguyễn Huy Sỹ
Ngày gửi: 21h:31' 29-06-2008
Dung lượng: 185.5 KB
Số lượt tải: 2581
Số lượt thích: 0 người
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  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
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ố đó vào tổng. (Chú ý cách tính này chưa xét n cũng là ước số của n).
function tongus(n : integer): integer;
var i,s : integer;
begin
s := 0;
for i := 1 to n div 2 do
if n mod i = 0 then s := s + i;
tongus := s;
end;
Chú ý: Dựa trên thuật toán tính tổng ước số, ta có thể kiểm tra được 1 số nguyên có là số hoàn thiện không: số nguyên gọi là số hoàn thiện nếu nó bằng tổng các ước số của nó.
CÁC THUẬT TOÁN VỀ VÒNG LẶP
THUẬT TOÁN TÍNH GIAI THỪA MỘT SỐ NGUYÊN
Giai thừa n! là tích các số từ 1 đến n. Vậy hàm giai thừa viết như sau:
function giaithua(n : integer) : longint;
var i : integer; s : longint;
begin
s := 1;
for i := 2 to n do s := s * i;
giaithua := s;
end;
THUẬT TOÁN TÍNH HÀM MŨ
Trong Pascal ta có thể tính ab bằng công thức exp(b*ln(a)). Tuy nhiên nếu a không phải là số dương thì không thể áp dụng được.
Ta có thể tính hàm mũ an bằng công thức lặp như sau:
function hammu(a : real; n : integer): real;
var s : real; i : integer;
begin
s := 1;
for i := 1 to n do s := s * a;
hammu := s;
end;
THUẬT TOÁN TÍNH CÔNG THỨC CHUỖI
Thuật toán tính hàm ex:

Đặt:  và , ta được công thức truy hồi:

Khi đó, ta có thể tính công thức chuỗi trên như sau:
function expn(x: real; n : integer): real;
var s,r : real; i : integer;
begin
s := 1; r := 1;
for i := 1 to n do begin
r := r * x / i;
s := s + r;
end;
expn := s;
end;
CÁC BÀI TẬP VỀ MẢNG 1 CHIỀU VÀ 2 CHIỀU
BÀI TẬP 1
Nhập vào một số n (5<=n<=10) và n phần tử của dãy a, 1In ra các phần tử là số nguyên tố của dãy.
Tính ước chung lớn nhất của tất cả các phần tử của dãy.
Tính biểu thức sau:

Sắp xếp dãy tăng dần và in ra dãy sau sắp xếp.
HƯỚNG DẪN
Ta nên chia chương trình thành các chương trình con, mỗi chương trình thực hiện một yêu cầu. Ngoài ra ta cũng viết thêm các hàm kiểm tra nguyên tố, hàm mũ, hàm UCLN để thực hiện các yêu cầu đó.
Chương trình như sau:
Khai báo dữ liệu:
uses crt;
var n : integer;
a : array[1..10] of integer; {n<=10 nên mảng có tối đa 10 phần tử}



Thủ tục nhập dữ liệu, có kiểm tra khi nhập.
procedure nhap;
var i : integer;
begin
clrscr;
write(`NHAP VAO SO PHAN TU N = `);
repeat
readln(n);
if (5<=n) and (n<=10) then break; {nếu thoã mãn thì dừng vòng lặp}
writeln(`Khong hop le (5<=n<=10). Nhap lai!!!`); {ngược lại thì báo lỗi}
until false;

writeln(`NHAP VAO N PHAN TU (1 for i := 1 to n do begin
write(`a`,i,`=`);
repeat
readln(a[i]);
if (1 writeln(`Khong hop le. Nhap lai!!!`);
until false;
end;
end;

function ngto(n : integer): boolean; {hàm kiểm tra nguyên tố, xem giải thích ở phần trên}
var i : integer;
begin
ngto := false;
if n < 2 then exit;
for i := 2 to round(sqrt(n)) do
if n mod i = 0 then exit;
ngto := true;
end;
Thủ tục in các số nguyên tố của một mảng
procedure inngto;
var i :integer;
begin
writeln(`CAC PHAN TU NGUYEN TO TRONG DAY:`);
for i := 1 to n do {duyệt qua mọi phần tử từ 1 đến n}
if ngto(a[i]) then writeln(a[i]); {nếu ai là nguyên tố thì in ra}
end;

function UCLN(a,b: integer): integer;
var r : integer;
begin
while b<>0 do begin
r := a mod b;
a := b;
b := r;
end;
UCLN := a;
end;

Thủ tục tính UCLN của các phần tử của một mảng
procedure TinhUC;
var i,u : integer;
begin
u := a[1]; {u là UCLN của các phần tử từ 1 đến i}
for i := 2 to n do u := UCLN(u,a[i]); {là UCLN của các phần tử từ 1 đến i-1 và ai}
writeln(`UCLN cua ca day la:`,u);
end;

function hammu(a : real; n : integer): real; {hàm mũ tính an}
var s : real; i : integer;
begin
s := 1;
for i := 1 to n do s := s * a;
hammu := s;
end;
Thủ tục tính tổng các phần tử có lấy mũ:
procedure tong;
var s : real; i : integer; {s phải khai báo là số thực để tránh tràn số}
begin
s := 0;
for i := 1 to n do s := s + hammu(a[i],i); {s := s + (ai)i}
writeln(`Tong can tinh:`,s:10:0);
end;
Thủ tục sắp xếp tăng dần các phần tử của một mảng:
procedure sxep;
var i,j,tg : integer;
begin
for i := 1 to n-1 do
for j := i + 1 to n do
if a[i] > a[j] then begin
tg := a[i]; a[i] := a[j]; a[j] := tg;
end;
writeln(`DAY SAU KHI SAP XEP TANG DAN:`);
for i := 1 to n do writeln(a[i]);
end;
Chương trình chính: lần lượt gọi từng thủ tục
BEGIN
nhap;
inngto;
tinhuc;
tong;
sxep;
END.


BÀI TẬP 2
Tìm phần tử nhỏ nhất, lớn nhất của một mảng (cần chỉ ra cả vị trí của phần tử).
HƯỚNG DẪN
Giả sử phần tử min cần tìm là phần tử k. Ban đầu ta cho k=1. Sau đó cho i chạy từ 2 đến n, nếu a[k] > a[i] thì rõ ràng a[i] bé hơn, ta gán k bằng i. Sau khi duyệt toàn bộ dãy thì k sẽ là chỉ số của phần tử min. (Cách tìm min này đơn giản vì từ vị trí ta cũng suy ra được giá trị).
procedure timmin;
var i, k : integer;
begin
k := 1;
for i := 2 to n do
if a[k] > a[i] then k := i;
writeln(`Phan tu nho nhat la a[`,k,`]=`,a[k]);
end;
Tìm max cũng tương tự, chỉ thay dấu so sánh.
procedure timmax;
var i, k : integer;
begin
k := 1;
for i := 2 to n do
if a[k] < a[i] then k := i;
writeln(`Phan tu lon nhat la a[`,k,`]=`,a[k]);
end;
Chú ý:
1. Nếu áp dụng với mảng 2 chiều thì cũng tương tự, chỉ khác là để duyệt qua mọi phần tử của mảng 2 chiều thì ta phải dùng 2 vòng for. Và vị trí một phần tử cũng gồm cả dòng và cột.
Ví dụ 1. Tìm phần tử nhỏ nhất và lớn nhất của mảng 2 chiều và đổi chỗ chúng cho nhau:
procedure exchange;
var i,j,i1,j1,i2,j2,tg : integer;
begin
i1 := 1; j1 := 1; {i1,j1 là vị trí phần tử min}
i2 := 1; j2 := 1; {i2,j2 là vị trí phần tử max}
for i := 1 to m do
for j := 1 to n do begin
if a[i1,j1] > a[i,j] then begin {so sánh tìm min}
i1 := i; j1 := j; {ghi nhận vị trí min mới}
end;
if a[i2,j2] < a[i,j] then begin {so sánh tìm max}
i2 := i; j2 := j; {ghi nhận vị trí max mới}
end;
end;
tg := a[i1,j1]; a[i1,j1] := a[i2,j2]; a[i2,j2] := tg; {đổi chỗ}
end;
2. Nếu cần tìm phần tử lớn nhất / nhỏ nhất hoặc sắp xếp 1 dòng (1 cột) của mảng 2 chiều thì ta cũng coi dòng (cột) đó như 1 mảng 1 chiều. Chẳng hạn tất cả các phần tử trên dòng k đều có dạng chỉ số là a[k,i] với i chạy từ 1 đến n (n là số cột).

Ví dụ 2. Tìm phần tử lớn nhất của dòng k và đổi chỗ nó về phần tử đầu dòng.
procedure timmax(k : integer);
var i, vt, tg : integer;
begin
vt := 1; {vt là vị trí của phần tử min dòng k}
for i := 1 to n do
if a[k,i] > a[k,vt] then vt := i; {các phần tử dòng k có dạng a[k,i]}
tg := a[k,1]; a[k,1] := a[k,vt]; a[k,vt] := tg;
end;
Ví dụ 3. Sắp xếp giảm dần cột thứ k.
procedure sapxep(k: integer);
var i,j,tg : integer;
begin
for i := 1 to m-1 do {mỗi cột có m phần tử, vì bảng có m dòng}
for j := i+1 to m do
if a[i,k] > a[j,k] then begin {các phần tử cột k có dạng a[i,k]}
tg := a[i,k]; a[i,k] := a[j,k]; a[j,k] := tg;
end;
end;
BÀI TẬP 3
Tìm các phần tử thoả mãn 1 tính chất gì đó.
HƯỚNG DẪN
Nếu tính chất cần thoả mãn là cần kiểm tra phức tạp (chẳng hạn: nguyên tố, hoàn thiện, có tổng chữ số bằng 1 giá trị cho trước…) thì ta nên viết một hàm để kiểm tra 1 phần tử có tính chất đó không. Còn tính chất cần kiểm tra đơn giản (chẵn / lẻ, dương / âm, chia hết, chính phương…) thì không cần.
Sau đó ta duyệt qua các phần tử từ đầu đến cuối, phần tử nào thoả mãn tính chất đó thì in ra.
Ví dụ 1. In ra các số chính phương của một mảng:
Để kiểm tra n có chính phương không, ta lấy căn n, làm tròn rồi bình phương và so sánh với n. Nếu biểu thức sqr(round(sqrt(n))) = n là true thì n là chính phương.
Vậy để in các phần tử chính phương ta viết:
for i := 1 to n do begin
if sqr(round(sqrt(a[i]))) = a[i] then writeln(a[i]);
Ví dụ 2. In ra các số hoàn thiện từ 1 đến n:
Để kiểm tra số có hoàn thiện ta dùng hàm tổng ước (đã có ở phần đầu).
for i := 1 to n do begin
if tongus(i) = i th
No_avatar

Có phải tài liệu này có tên cũ là "Ôn tập Turbo Pascal" không vậy?

Avatar

Tài liệu này Quang Duy cũng sưu tầm và đưa lên vào ngày 17.06.2008 với tên là Ôn tập Tubor pascal .

Avatar
Vậy à, thầy tặng mỗi mình Huy Sỹ sao? vậy mà dứa Bạn của Duy ở hà Nội cũng nói thầy tặng nó cơ đấy???vậy là sao nhỉ???
Avatar

Mà trên tài liệu có ghi là tặng cho riêng ai đâu? cũng chẳng nói là bản quyền thuộc về Huy Sỹ. Nếu Huy Sỹ có xác nhận của THầy Nguyễn Sỹ Tùng rằng bản quyền tài liệu ày thuộc về Huy Sỹ, Quang Duy sẽ xóa tài liệu ngay lập tức. Ok

No_avatar
Nếu tính về thời gian thì Duy gửi bài lên BK trước Huy Sỹ. Vậy ai phải suy nghĩ đây?
Avatar
Ai ai cũng háo danh!
Avatar
Trong 2 từ "Ai ai" có tên thầy Thảo không nhỉ?Cười. Thầy đừng vơ đũa cả nắm như vậy chứ! chỉ 2 từ đó mà thầy xúc phạm đến tất cả mọi người đấy. Thầy có thể rút lại câu nói vừa rồi, chẳng ai trách sự nông nổi của thầy đâu. Em xin lỗi vì đã nói thẳng hơi khó nghe, nhưng không thể không nói.
No_avatar
có thế thôi mà trang cãi sao? thật không đáng mặt đàn ông......Thè&nbsp;lưỡi
No_avatar
Tranh cãi cái gìd đấy
Avatar
Xin loi! Thay Thao bi ngoeo co a? 
 
Gửi ý kiến

↓ CHÚ Ý: Bài giảng này được nén lại dưới dạng ZIP và có thể chứa nhiều file. Hệ thống chỉ hiển thị 1 file trong số đó, đề nghị các thầy cô KIỂM TRA KỸ TRƯỚC KHI NHẬN XÉT  ↓