Bài 11: Sử dụng cấu trúc điều khiển để giải quyết bài toán

Bảng bài tập về cấu trúc điều khiển

Thứ tự bài	Nội dung bài
Bài tập 1	Giải phương trình bậc hai
Bài tập 2	Xếp loại học lực môn học
Bài tập 3	Tính tiền điện theo bậc giá
Bài tập 4	In ra các số chẵn liên tiếp
Bài tập 5	Đếm số lượng ước

Bài tập 1

Viết chương trình giải và biện luận nghiệm của phương trình bậc hai khi biết các hệ số a, b, c.

Phân tích bài toán

Phương trình bậc hai có dạng: $ax^{2}+bx+c=0\quad (a\neq 0)$

Để kết luận nghiệm của phương trình trên, ta dựa vào biểu thức $\Delta =b^{2}-4ac$ :

• Nếu $\Delta <0$, phương trình vô nghiệm
• Nếu $\Delta =0$, phương trình có nghiệm kép $x_{1}=x_{2}={\frac {-b}{2a}}$
• Nếu $\Delta >0$, phương trình có hai nghiệm phân biệt $x_{1}={\frac {-b+{\sqrt {\Delta }}}{2a}}$ và $x_{2}={\frac {-b-{\sqrt {\Delta }}}{2a}}$

Sơ đồ thuật toán

Mã chương trình

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    float a, b, c;
    
    cout << "Nhap a, b, c: ";
    cin >> a >> b >> c;
    
    float delta = b*b - 4*a*c;
    
    if (delta < 0) 
        cout << "Phuong trinh vo nghiem";
    else if (delta == 0) 
        cout << "Phuong trinh co nghiem x = " << -b/(2*a);
    else 
        cout << "Phuong trinh co hai nghiem"
             << endl << "x1 = " << ( -b + sqrt(delta) ) / (2*a)
             << endl << "x2 = " << ( -b - sqrt(delta) ) / (2*a);

    return 0;
}

Nhap a, b, c: 1 3 2
Phuong trinh co hai nghiem
x1 = -1
x2 = -2

Bài tập 2

Nhà trường dựa vào điểm số để xếp loại học lực của học sinh. Từ 8 điểm trở lên là loại Giỏi, từ 6.5 điểm trở lên là loại Khá, từ 5 điểm trở lên là Trung bình, từ 3.5 điểm trở lên là Yếu và dưới 3.5 điểm là Kém. Hãy viết chương trình xếp loại học lực của học sinh khi nhập vào điểm số.

Sơ đồ thuật toán

Mã chương trình

#include <iostream>
using namespace std;

int main() {
    float diem;
    cout << "Nhap diem: ";
    cin >> diem;
    
    if (diem >= 8) cout << "Gioi";
    else if (diem >= 6.5) cout << "Kha";
    else if (diem >= 5) cout << "Trung binh";
    else if (diem >= 3.5) cout << "Yeu";
    else cout << "Kem";
        
    return 0;
}

Bài tập 4

Viết chương trình in ra các số chẵn liên tiếp trong khoảng từ M tới N.

Bài tập 5

Cho trước một số nguyên N. Viết chương trình đếm số lượng ước dương của N (bao gồm cả 1 và N).

Phân tích bài toán

Một số được gọi là ước của N khi và chỉ khi N chia hết cho số đó.

Như vậy, cách đơn giản nhất là duyệt tìm từ 1 đến N, số nào mà N chia hết thì đếm vào bộ đếm. Cách làm này đơn giản nhưng không hiệu quả về mặt thời gian, nhất là với số có nhiều chữ số (9 chữ số trở lên). Lấy ví dụ đơn giản là đếm ước của 1.000.000, chúng ta sẽ lãng phí gần 500.000 lần lặp khi duyệt qua từ trên 500.000 đến dưới 1.000.000 vì trong khu vực này chắc chắn không có số nào là ước của 1.000.000.

Để hiệu quả và tối ưu về mặt thời gian, ta sẽ xem xét một số đặc điểm của ước. Ta nhận thấy nếu A chia hết cho B bằng C, thì A cũng chia hết cho C và bằng B. Ví dụ: 20 chia hết cho 2 bằng 10, thì 20 cũng chia hết cho 10 bằng 2. Như vậy khi ta tìm thấy một ước nào đó, ta không chỉ đếm được 1 mà còn là 2 ước. Bằng cách này, chúng ta chỉ cần duyệt từ 1 đến căn bậc hai của N, nhanh hơn rất nhiều so với cách trên.

Giải thích thêm về cách thứ hai, một số nguyên N luôn có thể viết dưới dạng $A.B$. Nếu quy định A là ước nhỏ, B là ước lớn thì theo toán học, $A\leqslant {\sqrt {A.B}}\leqslant B$. Dấu bằng xảy ra khi và chỉ khi $A=B$ (N là số chính phương), trong trường hợp này nếu có tìm được A thì ta chỉ đếm là 1 ước.

Hai cách làm cho một bài toán vừa được trình bày. Trong đó cách 1 là cách đơn giản, dành cho học sinh phổ thông; cách 2 là cách mở rộng và tối ưu, dành cho những ai có định hướng tham gia các cuộc thi về lập trình.

Cách làm đơn giản

Phương pháp giải: Duyệt từ 1 đến N và đếm những số mà N chia hết

#include <iostream>
using namespace std;

int main() {
    int N, count = 0;
    cout << "Nhap N: "; cin >> N;
    
    for (int i = 1; i <= N; i++)
        if (N % i == 0) count++;
        
    cout << "So luong uoc: " << count;
    
    return 0;
}

Cách làm mở rộng

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int N, count = 0;
    cout << "Nhap N: "; cin >> N;
    
    int sq = sqrt(N);
    for (int i = 1; i <= sq; i++) {
        if (N % i == 0) count += 2;
    
    if (sq*sq == N) count--;
        
    cout << "So luong uoc: " << count;
    
    return 0;
}