Tin học đại cương - Chương 3: Lý thuyết thuật toán

TIN HỌC ĐẠI CƯƠNG 1 Chương 3: LÝ THUYẾT THUẬT TOÁN GV: Lê Nhật Tùng Bộ môn: Công nghệ Phần mềm Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Các cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 2 Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Các cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 3 3.1 Khái niệm thuật toán  Thuật toán là một tập hữu hạn các bước, các phép toán cơ bản được sắp xếp theo một trình tự nhất định để từ thông tin đầu vào của bài toán sau một tập hữu hạn các bước đó sẽ đạt được kết quả ở đầu ra như mong muốn. 4 AlgorithmInput Output 3.1 Khái niệm thuật toán o Thông thường một thuật toán không dùng để giải một bài toán cụ thể, mà dùng để giải một lớp các bài toán cụ thể thuộc cùng một thể loại. Hai thành phần chính để cấu thành một bài toán tin học thông thường là: o Thông tin đầu vào (input) o Là những thông tin bài toán đã cho. o Thông tin đầu ra (ouput) o Là các thông tin cần tìm hoặc câu trả lời cần thiết. o Ví dụ: o Giải bài toán tính diện tích hình chữ nhật với công thức S= a * b o Input: a,b o Output: là diện tích S hoặc thông báo dữ liệu không hợp lệ 5 S = a * b 3.1 Khái niệm thuật toán o Ví dụ 1: Thuật toán để giải phương trình bậc nhất P(x): ax + b = 0, (a, b là các số thực)  Input: a,b  Output: kết quả giải phương trình bậc nhất P(x)  Mô tả thuật toán:  Nếu a = 0  Nếu b = 0 thì P(x) có nghiệm bất kì  Nếu b 0 thì P(x) vô nghiệm  Nếu a 0  P(x) có duy nhất một nghiệm x = -b/a 6 3.1 Khái niệm thuật toán o Ví dụ 2: kiểm tra một số nguyên x có phải là số chẵn không?  Input: x  Output: kết quả kiểm tra result  Mô tả thuật toán: Bước 1: Tìm số dư r của phép chia x cho 2 Bước 2: Kiểm tra  Nếu r = 0 thì result = True  Nếu r 0 thì result = False 7 Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Các cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 8 3.2 Tính chất của thuật toán o Tính dừng o Tính xác định o Tính đúng o Ðầu vào và đầu ra (input/output) o Tính hiệu quả (effectiveness) o Tính tổng quát (generalliness) 9 3.2 Tính chất của thuật toán o Thuật toán phải có tính dừng: thuật toán phải bao đảm được kết thúc sau một số hữu hạn bước. Ta có thể tìm ở đâu một lời giải vấn đề - bài toán có vô số bước giải ? o Tính dừng là tính dễ bị vi phạm, thường là do sai sót khi trình bày thuật toán dẫn đến “lặp vô tận”. 10 3.2 Tính chất của thuật toán o Thuật toán phải có tính xác định: các bước trong thuật toán phải được xác định rõ ràng, có thể thực thi được, không gây mập mờ, nhập nhằn, tùy chọn. 11 B1: Lập danh sách các sản phẩm bán trong tháng B2: Sắp xếp thứ tự danh sách sản phẩm B3: Giảm giá 10% giá tiền 10 sản phẩm đứng đầu danh sách B1: Lập danh sách các sản phẩm bán trong tháng gồm: Mã sản phẩm, tên sản phẩm, giá tiền, số lượng bán trong tháng B2: Sắp xếp thứ tự danh sách sản phẩm tăng dần theo số lượng bán B3: Giảm giá 10% giá tiền 10 sản phẩm đứng đầu danh sách 3.2 Tính chất của thuật toán o Thuật toán phải có tính đúng đắn: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác. Trong một kỳ thi kiểm tra không phải tất cả các học sinh điều đưa ra được lời giải “đúng”. Khi thiết kế thuật toán cần kiểm nghiệm và chỉnh sửa nhiều lần để có được một thuật toán đúng. 12 3.2 Tính chất của thuật toán o Ðầu vào và đầu ra (input/output): mọi thuật toán điều có đại lượng vào và ra. o Tính hiệu quả (effectiveness): Một bài toán có thể có nhiều thuật toán khác nhau để giải, một thuật toán tốt thì nó phải hiệu quả, tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. o Tính tổng quát (generalliness): thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. 13 Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Các cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 14 3.3 Biểu diễn thuật toán o Biểu diễn thuật toán bằng phương pháp liệt kê từng bước. o Biểu diễn thuật toán bằng sơ đồ khối. o Biểu diễn thuật toán bằng mã giả. 15 3.3 (tt) - Phương pháp liệt kê từng bước o Đặc điểm: o Các thao tác của thuật toán được liệt kê từng bước. o Tại mỗi bước sử dụng ngôn ngữ tự nhiên để diễn tả công việc phải làm. o Các bước trong thuật toán được đánh số thứ tự, bước có số thứ tự nhỏ hơn được thực hiện trước. o Ưu điểm: Dễ hiểu, dễ thực hiện. o Khuyết điểm: phụ thuộc cách hành văn của người thiết kế thuật toán, khó áp dụng cho những thuật toán có tính phức tạp. 16 3.3 (tt) - Phương pháp liệt kê từng bước o Ví dụ 1: Giải phương trình bấc nhất P(x): ax +b = 0: Input: a,b Output: Kết quả giải phương trình. Bước 1: Nhập vào 2 số thực a, b Bước 2: Kiểm tra nếu a = 0 thực hiện: Bước 2.1: Nếu b = 0 thì phương trình vô số nghiệm Bước 2.2: Nếu b 0 thì phương trình vô nghiệm Bước 3: Khi a 0 phương trình có nghiệm x=-b/a Bước 4: Kết thúc thuật toán 17 3.3 (tt) - Phương pháp liệt kê từng bước o Ví dụ 2: Giải phương trình bấc hai P(x): ax2 + bx + c = 0. (a,b,c là số thực, a ≠ 0). Input: a,b,c Output: Kết quả giải phương trình. Bước 1: Nhập vào 3 số thực a, b, c Bước 2: Tính Bước 3: Kiểm tra ∆ Bước 3.1: Nếu ∆<0 kết luận phương trình vô nghiệm. Bước 3.2: Nếu ∆=0 kết luận phương có nghiệm x1 =x2=-b/(2a) Bước 3.3: Nếu ∆>0 kết luận phương trình có 2 nghiệm: Bước 4: Kết thúc thuật toán 18 abb 42  a b x 2 1   a b x 2 2   3.3 (tt) - Biểu diễn thuật toán bằng sơ đồ khối (flowchart) o Đặc điểm: o Sử dụng các hình khối để biểu diễn các lệnh hay thao tác. o Sử dụng mũi tên để biểu diễn thứ tự thực hiện. o Ưu điểm: diễn đạt khoa học, có tính nhất quán, dễ hiểu và dễ kiểm tra. o Khuyết điểm: phải vẽ nhiều hình, cồng kềnh, không phù hợp với các thuật toán phức tạp. 19 3.3 (tt) - Các hình cơ bản trong sơ đồ khối 20 3.3 (tt) - Các hình cơ bản trong sơ đồ khối 21 Hình Ý nghĩa Biểu diễn câu lệnh rẽ nhánh: - Nếu điếu kiện đúng thì thực hiện nhánh Đ - Nếu điều kiện sai thì thực hiện nhánh S Biểu diễn việc thực hiện công việc A Biểu diễn việc gọi chương trình con A Biểu diễn hướng thực hiện của thuật toán A Biểu thức Logic S Đ A 3.3 (tt) - Ví dụ biểu diễn thuật toán bằng sơ đồ khối 22 3.3 (tt) - Ví dụ biểu diễn thuật toán bằng sơ đồ khối 23 Begin Input: a,b,c Delta = Delta<0 Đ S Output: P(x) vô nghiệm Delta<0 Đ S x=-b/(2a) Output: P(x) có nghiệm kép x Output: P(x) có nghiệm x1, x2 End 3.3 (tt) - Biểu diễn thuật toán bằng mã giả 24 o Đặc điểm: o Dựa trên các ngôn ngữ lập trình bậc cao (Pascal, C, Java,..) o Sử dụng ngôn ngữ tự nhiên của con người. o Ưu điểm: tương tự ngôn ngôn ngữ lập trình và ngôn ngữ tự nhiên, chuyển từ thuật toán sang chương trình dễ dàng. o Khuyết điểm: phải vẽ nhiều hình, cồng kềnh, không phù hợp với các thuật toán phức tạp. 3.3 (tt) - Biểu diễn thuật toán bằng mã giả 25 o Ví dụ: Tính tổng n số tự nhiên đầu tiên Nhập n i:=0 s:=0 REPEAT s=s+i; i=i+1; UNTIL (i>n) Xuất s Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Các cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 26 3.4 Các cấu trúc cơ bản của thuật toán 27 o Cấu trúc tuần tự o Cấu trúc rẽ nhánh o Cấu trúc lặp 3.4 Cấu trúc tuần tự 28 o Là cấu trúc bao gồm nhiều bước. o Các bước được sắp xếp theo một trật tự nhất định. o Chương trình được thực hiện theo thứ tự các bước đã sắp xếp. o Trong biểu diễn thuật toán bằng phương pháp liệt kê từng bước cấu trúc tuần tự được thể hiện ở việc mô tả cụ thể bước thứ i thực hiện: Bước 1, Bước 2, Bước 2.1, . o Khi dùng sơ đồ khối ta sử dụng để biểu diễn thứ tự thực hiện của thuật toán. 3.4 (tt) - Cấu trúc rẽ nhánh 29 o Là cấu trúc kiểm tra một điều kiện, khi điều kiện đúng chương trình sẽ thực hiện theo nhánh đúng, khi điều kiện sai chương trình sẽ thực hiện theo nhánh sai. o Các dạng cấu trúc rẽ nhánh: 3.4 (tt) - Cấu trúc lặp 30 o Là cấu trúc lặp đi lặp lại một hành động nhiều lần có hai dạng: o Số lần lặp xác định trước. o Số lần lặp không xác định trước. Nội dung 1. Khái niệm thuật toán 2. Tính chất của thuật toán 3. Các cách biểu diễn thuật toán 4. Các cấu trúc cơ bản của thuật toán 5. Một số thuật toán cơ bản 6. Bài tập 31 3.5 (tt) - Các thuật toán căn bản 32 o In dãy số o Tính tổng dãy số o Tính tích dãy số o Tìm kiếm một số có trong dãy hay không o Đếm số lượng phần tử thỏa mãn điều kiện o Tìm giá trị max, min o Sắp xếp tăng, giảm dãy số 3.5 (tt) - In dãy số 33 o Cho dãy n phần tử a1,a2,a3,,an nhập từ bàn phím, hãy in ra dãy số trên. Begin Input: n i=1 i<=n Input: ai Đ j=1 tong = 0 j<=n S Đ S End j=j+1 i=i+1 Output: aj 3.5 (tt) - Tính tổng dãy số 34 o Cho dãy n phần tử a1,a2,a3,,an. Tính tổng dãy số trên. o Ý tưởng: - Sử dụng một biến để tính tổng các phần tử. Ban đầu biến này bằng 0. - Duyệt từng phần tử và cộng phần tử vào biến tổng. 3.5 (tt) - Tính tổng dãy số 35 o Sơ đồ khối thuật toán tính tổng dãy số. Begin Input: n i=1 i<=n Input: ai Đ j=1 tong = 0 j<=n S Đ S End j=j+1 i=i+1 tong = tong + aj Output: tong 3.5 (tt) - Tính tích dãy số 36 o Cho dãy n phần tử a1,a2,a3,,an. Tính tích dãy số trên. o Ý tưởng: tương tự như thuật toán tính tổng - Sử dụng một biến để tính tích các phần tử. Ban đầu biến này bằng 1 (nếu biến ban đầu bằng 0 thí tích sẽ bằng 0  sai). - Duyệt từng phần tử và nhân phần tử vào biến tích. 3.5 (tt) - Tính tích dãy số 37 o Sơ đồ khối thuật toán tính tích dãy số. Begin Input: n i=1 i<=n Input: ai Đ j=1 tong = 0 j<=n S Đ S End j=j+1 i=i+1 tong = tong + aj Output: tong 3.5 (tt) - Tìm kiếm một số trong dãy 38 o Cho dãy n phần tử a1,a2,a3,,an. Kiểm tra số X có nằm trong dãy trên hay không? o Ý tưởng: - Sử dụng một biến để đánh đánh dấu xem có tìm thấy phần tử X hay không. Ban đầu biến đánh dấu có giá trị là FALSE. - Duyệt từng phần tử, nếu phần tử thứ i có giá trị bằng X thì gán biến đánh dấu là TRUE. 3.5 (tt) - Tìm kiếm một số trong dãy 39 o Sơ đồ khối tìm một phần tử trong dãy Begin Input: n i=1 i<=n Input: ai Đ j=1 tim = FALSE j<=n X=aj tim = TRUE j=j+1 Output: tim End S Đ S S Đ i=i+1 3.5 (tt) - Thuật toán đếm 40 o Cho dãy n phần tử a1,a2,a3,,an. Đếm xem trong dãy có bao nhiêu phần tử thỏa mãn một điều kiện nào đó: o Ý tưởng: - Sử dụng một biến đếm số lượng phần tử - Duyệt từng phần tử. - Kiểm tra phần tử đó có thỏa điều kiện hay không, nếu thỏa điều kiện thì tăng biến đếm lên 1. 3.5 (tt) - Thuật toán đếm 41 o Sơ đồ khối thuật toán đếm: Begin Input: n i=1 i<=n Input: ai Đ j=1 dem=0 j<=n Biểu thức Logic dem=dem+1 j=j+1 Output: dem End S Đ S S Đ i=i+1 3.5 (tt) - Thuật toán đếm 42 o Ví dụ: cho dãy n số nguyên a1,a2,a3,,an. Đếm xem trong dãy có bao nhiêu số chẵn. Begin Input: n i=1 i<=n Input: ai Đ j=1 dem=0 j<=n dem=dem+1 j=j+1 Output: dem End S Đ S S Đ i=i+1 3.5 (tt) - Tìm giá trị max (min) 43 o Cho dãy n phần tử a1,a2,a3,,an. Tìm phần tử có giá trị max (min) trong dãy số. o Ý tưởng: - Sử dụng một biến lưu giá trị max (min), ban đầu max = a1 - Duyệt từng phần tử. - Kiểm tra phần tử đó có lớn hơn biến giá trị max (nhỏ hơn giá trị min) nếu thỏa điều kiện biến max bằng phần tử đó. 3.5 (tt) - Tìm giá trị max (min) 44 o Sơ đồ khối tìm phần tử max Begin Input: n i=1 i<=n Input: ai Đ j=1 max = a1 j<=n aj>max max = aj j=j+1 Output: max End S Đ S S Đ i=i+1 3.5 (tt) - Sắp xếp 45 o Cho dãy n phần tử a1,a2,a3,,an. Hãy sắp xếp dãy số tăng (giảm) o Ý tưởng: - Duyệt từng phần tử: - Phần tử đang duyệt được gọi là phần tử hiện tại - Thực hiện một vòng lặp con, duyệt các phần tử còn lại. Nếu giá trị của phần tử được duyệt trong vòng lặp con bé hơn phần tử hiện tại  thực hiện việc đổi chổ 2 phần tử. 3.5 (tt) - Sắp xếp 46 o Sơ đồ khối sắp xếp dãy tăng dần Begin Input: n i=1 i<=n Input: ai Đ j=1 j<n S Đ S i=i+1 k=j+1 k<=n ak<aj tam = ak ak= aj aj = tam k = k +1 End j = j + 1 S Đ Đ S Bài tập 47 1. Vẽ sơ đồ thuật toán nhập vào dãy a1,a2,a3,.,an và in ra dãy số trên một dòng. 2. Vẽ sơ đồ khối biểu diễn thuật toán tính trung bình cộng dãy số a1,a2,a3,.,an 3. Vẽ sơ đồ khối biểu diễn thuật toán tính trung bình cộng các số lẻ và chia cho 3 trong dãy số a1,a2,a3,.,an 4. Vẽ sơ đồ thuật toán nhập vào 3 điểm A(xa,ya), A(xa,ya), A(xa,ya) có là lập thành hình tam giác hay không, nếu có kiểm tra xem tam giác trên có phải là tam giác cân hay không? 5. Vẽ sơ đồ thuật toán kiểm tra xem số N có phải là số nguyên tố hay không? 6. Vẽ sơ đồ thuật toán kiểm tra số N có phải là số chính phương hay không? 7. Vẽ sơ đồ thuật toán nhập vào n điểm, xác định diện tích đường tròn tâm O(0,0) chứa tất cả các điểm trên. Bài tập 48 8. Vẽ sơ đồ thuật toán nhập vào dãy n điểm(xi,yi), tìm và in ra diện tích hình chữ nhật nhỏ nhất chứa tất cả các điểm trên. 9. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , sắp xếp và in ra màn hình dãy số tăng dần. 10. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , in ra màn hình dãy số theo chiều ngược lại. 11. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , tìm và in ra màn hình số xuất hiện nhiều lần nhất trong dãy trên. 12. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , tìm và in ra dãy con liên tiếp tăng dần dài nhất (ai <= ai+1) 13. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a1,a2,a3,.,an , xuất ra màn hình 3 số âm lớn nhất trong dãy.