SGK Tin Học 11 - Bài 10. Cấu trúc lặp
§10 . CẤU TRÚC LẶP
1.
Lặp
Với a là số nguyên và a > 2, xét các bài toán sau đây: Bài toán 1. Tính và đưa kết quả ra màn hình tổng
s — H
a a + ì a + 2
+ ... +
ữ + 100
Bài toán 2. Tính và đưa kết quả ra màn hình tổng
s = - +
a a + I a + 2
1 1.1,1 + —-— + ... + —-— +
cho đến Khi ——— < 0,0001. a + N
Với cả hai bài toán, dễ thấy cách để tính tổng 5 có nhiều điểm tương tự:
• Xuất phát, s được gán giá trị —;
a
• Tiếp theo, cộng vào tổng s một giá trị ——— với N = 1, 2, 3, 4, 5,...
a + N
Việc cộng này được lặp lại một số lần.
Đối với bài toán 1, số lần lặp là 100 và việc cộng vào tổng s sẽ kết thúc khi đã thực hiện việc cộng 100 lần.
Đối với bài toán 2, số lần lặp chưa biết trước nhưng việc cộng vào tổng s sẽ
kết thúc khi điều kiện ——- < 0,0001 được thoả mãn. a + N
Nói chung, trong một số thuật toán có những thao tác phải thực hiện lặp đi lặp lại một số lần. Một trong các đặc trưng của máy tính là có khả năng thực hiện hiệu quả các- thao tác lặp. Cấu trúc lặp mô tả thao tác lặp và có hai dạng là lặp với số lần biết trước và lặp với số lần chưa biết trước.
Các ngôn ngữ lập trình đều có các câu lệnh để mô tả cấu trúc lặp.
Lặp vỏi số lần biết trưốc và câu lệnh for-do
Có hai thuật toán Tong_la và Tong_lb để giải bài toán 1 như sau:
Thuật toán Tong_la
Bước 1. s <— 1/a; N <— 0; {Khởi tạo s và N}
Bước 2. N <^N + 1;
Bước 3. Nếu N > 100 thì chuyển đến bước 5;
Bước 4. s <—S + l/(a + N) rồi quay lại bước 2;
Bước 5. Đưa s ra màn hình, rồi kết thúc.
Thuật toán Tong_lb
Bước 1. s <— 1/a; N <— 101; {Khởi tạo s và N}
Bước 2. N <r-N - 1;
Bước 3. Nếu N < 1 thì chuyển đến bước 5;
Bước 4. s <- s + l/(ứ + N) rồi quay lại bước 2;
Bước 5. Đưa s ra màn hình rồi kết thúc.
Lưu ý, số lần lặp của cả hai thuật toán trên là biết trước và như nhau (100 lần).
Trong thuật toán Tong_la, giá trị N khi bắt đầu tham gia vòng lặp là 1 và sau mỗi lần lặp N tăng lên 1 cho đến khi N > 100 (2V = 101) thì kết thúc lặp (thực hiện đủ 100 lần). Trong thuật toán Tong_lb, giá trị 7V bắt đầu tham gia vòng lặp là 100 và sau mỗi lần lặp N giảm đi 1 cho đến khi N < 1 (N = 0) thì kết thúc lặp (thực hiện đủ 100 lần). Ta nói cách lặp trong thuật toán Tong_la là dạng tiến và trong thuật toán Tong_lb là dạng lùi.
Để mô tả cấu trúc lặp với số lần biết trước, Pascal dùng câu lệnh lặp for-do với hai dạng tiến và lùi như sau:
Dạng lặp tiến:
for := to do ỉ
Dạng lặp lùi:
for := downto do ; trong đó:
Biến đếm là biến đơn, thường có kiểu nguyên.
Giá trị đầu, giá trị cuối là các biểu thức cùng kiểu với biến đếm và giá trị đầu phải nhỏ hơn hoặc bằng giá trị cuối. Nếu giá trị đầu lớn hơn giá trị cuối thì vòng lặp không được thực hiện.
Hoạt động của lệnh for-do:
ở dạng lặp tiến, câu lệnh viết sau từ khoá do được thực hiện tuần tự, với biến đếm lần lượt nhận các giá trị liên tiếp tăng từ giá trị đầu đến giá trị cuối.
ở dạng lặp lùi, câu lệnh viết sau từ khoá do được thực hiện tuần tự, với biến đếm lần lượt nhận các giá trị liên tiếp giảm từ giá trị cuối đến giá trị đầu.
Chú ý: Giá trị của biến đếm được điều chỉnh tự động, vì vậy câu lệnh viết sau do không được thay đổi giá trị biến đếm.
Ví dụ 1. Sau đây là hai chương trình cài đặt các thuật toán Tong_la và Tong_lb.
program Tong_la; uses crt; var S: real;
a, N: integer; begin
clrscr;
write('Hay nhap gia tri a vao!'); readln(a) ;
S:=1.0/a;
for N:= 1 to 100 do
{Buoc 1}
(Buoc
(Buoc
(Buoc
2, Buoc 3}
4}
5}
S: = S.+ 1.0/(a+N) ;
: 8 : 4) ;
writeln('Tong s
readln
la: S:
end.
program Tong lb;
uses crt;
var S: real;
a, N: integer;
begin
. clrscr;
write (‘Hay nhap
gia tri
a vao!'
);
readln(a);
{Buoc 1}
{Buoc 2 va Buoc 3}
{Buoc 4} {Buoc 5}
S:=1.0/a;
for N:= 100 downto 1 do
S:= s+l.0/(a+N); writeln('Tong s la: ', S:8:4); readln
end.
Ví dụ 2. Chương trình sau thực hiện việc nhập từ bàn phím hai số nguyên dương M và N (M < N), tính và đưa ra màn hình tổng các số chia hết cho 3 hoặc 5 trong phạm vi từ M đến N.
program Vi_du_2; uses crt;
var M, N, I: integer;
T: longint;
begin
clrscr;
writeln ('Nhap so M nho hpn N'); write('M = ');readln(M); write('N = ');readln(N);
T: = 0;
for I:= M to N do
if (I mod 3=0) or (I mod 5=0) then •
T:=T+I;
writelnt'KET QUA: T);
readln
end.
Lập vói số lần chưa biết trưóc và câu lệnh while-do
Có thể xây dựng thuật toán Tong_2 như sau để giải bài toán 2.
Thuật toán Tong_2
Bướt 7. s <—1/ữ; N <—0; {Khởi tạo S và 2V}
Bước 2. Nếu l/(<2 + N) < 0,0001 thì chuyển đến bước 5;
Bước 3. N <- N + 1;
Bước 4. s <—S + l/(ơ + N) rồi quay lại bước 2;
Bước 5. Đưa s ra màn hình, rồi kết thúc.
Như vậy, việc lặp với số lần chưa biết trước sẽ chỉ kết thúc khi một điều kiện cho trước được thoả mãn.
Để mô tả cấu trúc lặp như vậy, Pascal dùng câu lệnh whiỉe-do có dạng: while do;
trong đó:
Điều kiện là biểu thức lôgic;
Câu lệnh là một câu lệnh đơn hoặc ghép.
Việc thực hiện lệnh while-do được thể hiện trên sơ đồ ở hình 7.
Hình 7. Sơ đồ lặp với số lần lặp chưa biết trước Ví dụ 1. Saụ đây là sơ đồ khối và chương trình cài đặt thuật toán Tong_2.
Hình 8. Sơ đồ khối của thuật toán Tong 2
program Tong_2;
uses crt;
var S: real;
a, N: integer;
begin
write ('Hay nhap gia tri a vao!'); readln (a) ;
S: = 1.0/a; N; = 0;
{Buoc
1}
while not (1/(a+N)<0.0001) do
{Buoc
2}
begin
N: = N+Ị;
{Buoc
3}
S: = s+l.o/(a+N);
(Buoc
4}
end;
writeln('Tong s la: ', S:8:4);
{Buoc
5}
readln
end.
Ví dụ 2. Tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương M và N.
Có nhiều thuật toán khác nhau tìm ƯCLN của M và N. Sau đây là một thuật toán tìm ƯCLN.
Thuật toán Bước 1. Nhập M, N;
Bước 2. Nếu M = N thì lấy giá trị chung này làm ƯCLN rồi chuyển đến bước 5;
Bước 3. Nếu M > N ửù M <— M — N ngược lại N <— N - M;
Bước 4. Quay lại bước 2;
Bước 5. Đưa ra kết quả ƯCLN rồi kết thúc.
Hình 9. Sơ đồ khối của thuật toán tìm ước chung lớn nhất
Chương trình sau thể hiện thuật toán tìm ước chung lớn nhất.
program UCLN; uses crt; var M,N:integer; begin
clrscr;
write('M, N = '); readln(M,N);
while M N do
if M > N then M:= M-N else N;= N-M; writeln('UCLN = ', M) ; readln
end.
Chú ý: Các câu lệnh trong vòng lặp thường được lặp lại nhiều lẩn, vì vậy để tăng hiệu quả của chương trình thì những thao tác không cần lặp lại nên đưa ra ngoài vòng lặp.
TÓM TẮT
Các ngôn ngữ lập trình đều có câu lệnh thể hiện cấu trúc rẽ nhánh và câu trúc lặp.
Câu lệnh rẽ nhánh có hai dạng: o Dạng thiếu;
o Dạng đủ.
Có thể gộp dãy câu lệnh thành câu lệnh ghép.
Các câu lệnh mô tả cấu trúc lặp: o Lặp với số lần biết trước;
o Lặp với số lần chưa biết trước.
Định lí Bohn Jacopini (Bon Ja-co-pi-ni): Mọi quá trình tính toán đều có thể mô tả và thực hiện dựa trên ba câu trúc cơ bản là cấu trúc tuần tự, cẫu trúc rẽ nhánh và cấu trúc lặp.