Lý thuyết cấu trúc lặp - Tài liệu Tin học

Đăng bởi Admin

Tháng 10 1, 2022

Xét hai bài toán sau:

Bài toán 1: Tính giá trị tổng $S$ biết:
$S = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N}S$
Bài toán 2: Tính giá trị tổng $S$ biết:
$S = 1+2+3+\cdots +S$

Xét các ví dụ sau:

Một trường đại học cần tuyển 1000 người, trong đó số lượng thi là 10 nghìn người. Khi thi xong, phòng đào tạo sẽ cần phải duyệt từ 1 đến 10 nghìn người để lấy ra 1000 người đạt điều kiện vào trường.
Trong danh sách sinh viên để xem ai là người có kết quả học tập cao nhất. Chúng ta phải xem từ người đầu đến cuối để chọn ra người cao điểm.
Hàng tuần sẽ có từ Thứ 2 đến hết Chủ Nhật sau đó lại lặp lại chỉ khác nhau về số lần.
Chạy bền vòng quanh sân vận động, cứ hết vòng thì trở lại vạch xuất phát chỉ khác số vòng tăng lên

Nhìn chung, trong mọi thuật toán đều sẽ có những thao tác phải lặp đi lặp lại nhiều lần. Đối với con người, khi số lần lặp lại công việc quá lớn, việc thực hiện sẽ là bất khả thi. Nhưng với máy tính, khả năng tính toán cực kỳ nhanh chóng sẽ khiến cho việc thực hiện các thao tác lặp trở nên rất hiệu quả. Có hai dạng lặp là lặp với số lần biết trước và lặp với số lần không biết trước. C++ cung cấp cả hai cấu trúc lặp để biểu diễn hai thao tác lặp này.

Câu lệnh for (số lần lặp biết trước)

Dùng để thực hiện nhiều lần một công việc

for([Khởi_tạo_biến_đếm];[Điều_kiện_dừng];[Thay_biến_đếm]) {
     Khối lệnh;
}

Quy trình thực hiện của vòng lặp:

Bước 1 – {Khởi_tạo_biến_đếm}: Một lệnh khởi tạo ra một hoặc nhiều biến đếm bất kỳ trong vòng lặp, hoặc không khởi tạo biến nào cả (tuy nhiên vẫn phải có dấu chấm phẩy).
Bước 2 – {Điều_kiện_dừng}: Là một biểu thức logic xác định điều kiện khi nào vòng lặp sẽ dừng lại. Trước khi thực hiện {Khối_lệnh}, biểu thức sẽ kiểm tra kết quả, nếu là true thì |Khối lệnh| sẽ được thực hiện tiếp, ngược lại thì vòng lặp sẽ dừng.
Bước 3 – {Khối_lệnh}: Sau khi kiểm tra {Điều_kiện_dừng} và thấy kết quả là true, khối lệnh sẽ được thực hiện.
Bước 4 – {Thay đổi biến đếm}: Cập nhật giá trị biến đếm theo bất kỳ cách nào người dùng mong muốn (có thể không cập nhật gì cả nhưng vẫn phải có dấu chấm phẩy). Sau khi cập nhật xong, quá trình quay trở lại từ bước 2 cho tới khi {Điều_kiện_dừng} nhận giá trị false.

Ví dụ:

int i;
for(i = 0; i < 100; i++) Câu_lệnh;

int i;
for(i = 0; i < 100; i+=2) Câu_lệnh;

int i;
for(i = 100; i > 0; i--) Câu_lệnh;

Tìm các số nguyên lẻ nhỏ hơn 100:

#include<iostream>
using namespace std;

int main()
{
    for(int i=1;i<100;i++)
    {
        if(i%2==1)cout<<i<<" ";
        if((i+1)%20==0)cout<<"\n";
    }
    return 0;
}

1 3 5 7 9 11 13 15 17 19
21 23 25 27 29 31 33 35 37 39
41 43 45 47 49 51 53 55 57 59
61 63 65 67 69 71 73 75 77 79
81 83 85 87 89 91 93 95 97 99

Chú ý:

Không nhất thiết phải có đầy đủ các thành phần trong vòng lặp for.

int getchar(): đọc ký tự từ vùng đệm bàn phím. Nếu vùng đệm rỗng, đợi người dùng gõ dãy ký tự (cho tới khi ấn phím Enter), sẽ trả về ký tự đầu

putchar(int c): đưa ký tự ra màn hình

Thiếu biểu thức khởi tạo

char c; int i=0;
for( ; (c=getchar())! = '\n’ ; i++)
	putchar(c);
printf(“\nSo ky tu: %d”,i);

/*Hello world
Hello world
So ky tu: 11*/

Thiếu biểu thức điều kiện dừng

for(i=0 ; ; c=getchar(), i++)
	if(c==‘\n’) break; 
printf(“\nSo ky tu: %d”,i);

/*Hello world

So ky tu: 12*/

Thiếu thân vòng lặp

for(i=0 ; getchar() != ‘\n’, i++);
printf(“\nSo ky tu: %d”,i);

/*Hello world
So ky tu: 11*/

Cấu trúc lặp while (số lần lặp không biết trước)

Dùng để thực hiện lặp đi lặp lại một công việc nào đó tới khi điều kiện không thỏa mãn

while ({Điều_kiện_dừng})
{
    {Khối_lệnh};
}

Chương trình kiểm tra điều kiện trước khi lặp

Giá trị của biểu thức điều kiện là đúng thì thực hiện lệnh

Các lệnh của vòng lặp có thể không được thực hiện lần nào nếu Điều_kiện_dừng sai ngay từ đầu

Nếu Điều_kiện_dừng luôn đúng có thể gây lặp vô hạn

Ví dụ:

Nhập n và in ra tổng của n số nguyên đầu tiên

#include<iostream>
using namespace std;
int S,n;
int main()
{
    S = 0;
    cout<<"Nhap n: ";
    cin>>n;
    while(n > 0)
    {
        S = S+n;
        n = n-1;
    }
    cout<<"Ket qua la: "<<S;
    return 0;
}

Nhap n: 96
Ket qua la: 4656

Cấu trúc lặp do…while…

Dùng để thực hiện lặp đi lặp lại một công việc nào đó

do{
     Khối_lệnh;
}while(Điều_kiện_dừng);

Chương trình kiểm tra điều kiện sau khi lặp

Các lệnh được thực hiện ít nhất một lần

Điều kiện luôn đúng thì lặp vô hạn lần

Ví dụ:

Nhập n và đưa tổng n số nguyên đầu tiên:

#include<iostream>
using namespace std;
int S,n;
int main()
{
    S = 0;
    cout<<"Nhap n: ";
    cin>>n;
    do
    {
        S = S + n;
        n = n - 1;
    }while(n > 0);
    cout<<"Ket qua la: "<<S;
    return 0;
}

Nhap n: 96
Ket qua la: 4656

Lưu ý:

Cú pháp C++ cho phép người dùng có thể lồng nhiều vòng lặp vào nhau. Khi đó, ứng với mỗi lần lặp của vòng lặp bên ngoài thì vòng lặp bên trong sẽ được thực hiện đủ số lần lặp của nó.
Lệnh break: Sử dụng để ngắt vòng lặp. Khi gặp lệnh break, vòng lặp đang chứa lệnh đó sẽ ngay lập tức bị ngắt kể cả khi {Điều_kiện_dừng} vẫn đang nhận giá trị true. break cũng dùng để thoát ra khỏi lệnh rẽ nhánh switch.
Lệnh continue: Sử dụng để bỏ qua một lần lặp. Khi gặp lệnh continue, toàn bộ phần lệnh bên dưới lệnh này (thuộc cùng khối lệnh) sẽ bị bỏ qua và chuyển tới lần lặp tiếp theo trong vòng lặp đó. Đối với vòng lặp for, lệnh continue sẽ điều khiển tới phần {Thay_đổi_biến_đếm}; còn đối với lệnh while và do...while thì lệnh continue sẽ điều khiển tới phần {Điều_kiện_dừng}.