3.4.1 Bài toỏn ủếm
Bài toỏn: Cho một dóy n cỏc phần tử a1, a2,…, an. Hóy ủếm xem trong dóy cú bao nhiờu phần tử thoả món ủiều kiện nào ủú.
Một cỏch tự nhiờn thỡ ủể giải bài toỏn trờn, ta thực hiện duyệt qua từng phần tử. Với mỗi phần tử thoả món ủiều kiện thỡ tăng biến ủếm lờn một ủơn vị.
Thuật toán
Bước 1. Xỏc ủịnh n và cỏc phần tử a1, a2, ... an
Bước 2. Khởi tạo một biến ủếm với giỏ trị là 0
Bước 3. Thực hiện duyệt qua từng phần tử. Với mỗi phần tử ủược duyệt, thực hiện kiểm tra xem nú cú thoả món ủiều kiện bài toỏn khụng?. Nếu thoả món thỡ tăng biến ủếm lờn một ủơn vị. Nếu khụng thoả món thỡ duyệt phần tử tiếp theo.
Mụ tả thuật toỏn bằng sơ ủồ khối
Ví dụ 1: Cho một dãy n số nguyên. ðếm xem trong dãy có bao nhiêu số chẵn.
Thuật toán
Sử dụng phương phỏp ủặc tả tự nhiờn mụ tả thuật toỏn
n
i = 1, 2, .., n
ai
Dem = 0
i = 1, 2, .., n
Bt Lôgíc
Dem
S ð
Dem = Dem +1 Begin
End
http://www.ebook.edu.vn 28
Bước 1. Xỏc ủịnh n và cỏc phần tử a1, a2, ... an Bước 2. Khởi tạo một biến ủếm với giỏ trị là 0
Bước 3. Thực hiện duyệt qua từng phần tử. Với mỗi phần tử ủược duyệt, thực hiện kiểm tra: Nếu ai chia hết cho 2 thỡ tăng biến ủếm lờn một ủơn vị. Ngược lại, duyệt phần tử tiếp theo.
Sử dụng sơ ủồ khối mụ tả thuật toỏn
Mụ tả thuật toỏn ủếm cỏc số chẵn trong một dóy số
3.4.2 Bài toán tìm giá trị lớn nhất, giá trị nhỏ nhất
Trong cuộc sống thực tế, hàng ngày chỳng ta luụn phải ủi tỡm giỏ trị lớn nhất, nhỏ nhất trong một tập phần tử. Ví dụ như tìm người có chiều cao cao nhất (thấp nhất) trong lớp; tìm sinh viờn cú ủiểm tổng kết cao nhất (thấp nhất) trong lớp, trong khoa, trong trường; …. Như vậy nếu cú một thuật toỏn giải bài toỏn này và cài ủặt nú trờn mỏy tớnh ủể mỏy giải giỳp chỳng ta thỡ ủú thực sự là một ứng dụng cú ớch. Bài toỏn cụ thể ủược phỏt biểu như sau:
Bài toỏn: Cho một dóy n số bất kỳ. Hóy tỡm giỏ trị lớn nhất (nhỏ nhất) của dóy số ủú.
ðể tìm giá trị lớn nhất (nhỏ nhất) của các phần tử trong dãy. Ta thực hiện so sánh các phần tử trong dóy với nhau sẽ tỡm ra ủược giỏ trị mong muốn. Quỏ trỡnh tỡm ủược thể hiện bằng thuật toỏn sau ủõy.
Thuật toán
Sử dụng phương phỏp ủặc tả tự nhiờn mụt tả thuật toỏn Bước 1. Xỏc ủịnh n và cỏc số a1, a2, …, an
Bươc 2. Sử dụng Max lưu giá trị lớn nhất. Giả sử giá trị lớn nhất là a1 (tức là Max = a1).
Bước 3. Duyệt lần lượt qua các phần tử a2, a3, …, an. So sánh giá trị của phần tử ai với Max. Nếu ai > Max (i=2..n) thì gán giá trị của ai cho Max (Max = ai). Nếu ai < Max thì chuyển xét phần tử tiếp theo.
Giá trị cuối cùng lưu trong Max chính là giá trị lớn nhất của dãy số.
Input: n
i = 1, 2, .., n
Input: ai
Dem = 0
i = 1, 2, .., n
aiM 2
Dem = Dem +1
Output: Dem
S ð
Begin
End
http://www.ebook.edu.vn 29
Sử dụng sơ ủồ khối mụ tả thuật toỏn
Thuật toán tìm giá trị lớn nhất của một dãy số.
ðối với bài toán tìm giá trị nhỏ nhất cũng tương tự, nhưng trong phép so sánh ta phải thay dấu “<” bằng dấu “>” và thay tờn Max thành Min ủể phự hợp với ý nghĩa kết của kết quả lưu trong nó.
Một số bài toán qui về bài toán tìm max, min Bài 1. Cho tọa ủộ của một dóy n ủiểm { i, i}n1
x y i= trong mặt phẳng. Tỡm diện tớch ủường trũn tõm O(0,0) cú bỏn kớnh nhỏ nhất chứa n ủiểm trờn.
Gợi ý: Bài toán này qui về bài toán tìm Max Bài 2. Cho tọa ủộ của một dóy n ủiểm { i, i}n1
x y i= trong mặt phẳng. Tìm hình chữ nhật có diện tớch nhỏ nhất và cỏc cạnh song song với cỏc trục toạ ủộ chứa n ủiểm trờn.
Gợi ý: Bài toán này qui về bài toán tìm cả Min và Max.
3.4.3 Bài toán tính tổng một dãy số
Bài toán: Cho 1 dãy n số. Tính tổng tất cả các phần tử của dãy.
Thuật toán
Sử dụng phương phỏp ủặc tả tự nhiờn mụ tả thuật toỏn Bước 1. Xỏc ủịnh n, a1, a2, …, an
Bước 2 .Khởi tạo S = 0
Bước 3. Duyệt qua từng phần tử của dãy số. Với phần tử ai của dãy thực hiện S = S + ai. Sau khi duyệt qua hết cỏc phần tử ta ủược tổng của dóy lưu trong S.
Sử dụng sơ ủồ khối mụ tả thuật toỏn
i = 2, 3,..., n Input: n
i = 1, 2, .., n
Input: ai
Max = a1
Max<ai
Output: Max
S ð
Max = ai
Begin
End
http://www.ebook.edu.vn 30
Một số bài toán qui về bài toán tính tổng
Bài 1. Tớnh giỏ trị của ủa thực Pn(x) = a0 + a1x + a2x2 + … +anxn Bài 2. Tính tổng theo công thức (công thức tổng quát dạng S = f(x) +
n
i=1
f(x,n)
∑ )
Ví dụ 1: Cho x là số thực, n là số nguyên dương. Tính S = ex + 1
2 +x
+ 1 2
3 +x
+ … + 1 1 xn
n +
+ Ví dụ 2: Cho x là số thực, n là số nguyên dương. Tính
S = | x+ (1+x)3 + (2+x)3 + … +(n+x)3| Ví dụ 3: Cho x là số thực, n là số nguyên dương. Tính
1 2
2006 ... ( 1)
1! 2! !
x x n x n
s n
+ + +
= − + − + −
Ví dụ 4: Cho x là số thực, n là số nguyên dương. Tính
2
2006 ...
2! !
x xn
S x
= + + + + n
Vớ dụ 5: Cho n ủiểm trờn mặt phẳng tọa ủộ ðề cỏc xOy: M1, M2, ... Mn. Tớnh ủộ dài ủường gấp khỳc lần lượt ủi qua cỏc ủiểm trờn theo thứ tự tự M1 ủến Mn ?
Input: n
i = 1, 2, .., n
Input: ai
S = 0
i = 1, 2,..., n
S = S + ai
Output: S Begin
End
http://www.ebook.edu.vn 31
3.4.4 Bài toán tính tích một dãy số
Bài toán: Cho 1 dãy n số. Tính tích tất cả các phần tử của dãy.
Thuật toán tính tích của một dãy số cũng tương tự như thuật toán tổng. Tuy nhiên khác với thuật toỏn tớnh tổng là khi khởi gỏn cho ủại lượng lưu trữ tớch là 1 thay vỡ khởi gỏn 0 và thay phép + bằng phép * (nhân).
Các bài toán qui về thuật toán tính tích Bài 1. Cho số tự nhiên n. Tính S = n!
Bài 2. Cho số thực x, số tự nhiên n. Tính S = xn
http://www.ebook.edu.vn 32
PHẦN 2