Giới thiệu về thuật toán trong tin học

Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắcnhằm xác định một dãy các thao tác trên những đối tượng, saocho sau một số hữu hạn bước thực hiện các thao tác ta đạt đượcmục tiêu định trước.
Nội dung trích xuất từ tài liệu:
Giới thiệu về thuật toán trong tin học Giới thiệu về thuật toán trong tin học 1. Khái niệm thuật toán Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắcnhằm xác định một dãy các thao tác trên những đối tượng, saocho sau một số hữu hạn bước thực hiện các thao tác ta đạt đượcmục tiêu định trước. Để giải các bài toán bằng máy tính chúng ta thường phải cómột quan niệm rộng rãi hơn về thuật toán cụ thể là lưu ý đến cácđặc điểm sau: a) Không cần xác định toàn bộ lời giải, các thao tác theo từng bước một cách chính xác, đơn vị và rõ ràng.Thay vào đó chỉ cần chỉ ra một cách chuyển từ một bước giải i tới bước giải kế tiếp i+1, và tìm cách cắt nhỏ bài toán thành các bài toán con, đó chính là thuật toán đệ quy rất quan trọng để giải các bài toán tổng quát. b) Có nhiều bài toán không có cách giải đúng, hoặc cách giải đúng không thể chấp nhận được do hạn chế về thời gian chạy và kích thước bộ nhớ. Nhưng nếu ta chấp nhận kết quả gần đúng thì có thể tồn tại nhiều cách giải đỡ phức tạp và có hiệu quả hơn, đó chính là các thuật toán Heuristic để giải các bài toán gần đúng. 2. Khái niệm bài toán: Trong phạm vi tin học ta có thể quan niệm bài toán là mộtviệc nào đó ta muốn máy tính thực hiện. Các bài toán được cấutạo bởi 2 thành phần cơ bản Input và Output. Thuật toán cũng cóthể được hiểu là một dãy các thao tác được sắp xếp theo trình tựxác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input củabài toán ta nhận được Output cần tìm. 3. Một số ví dụ: Bài toán 1:Tìm giá trị lớn nhất của một dãy số nguyên Xác định bài toán Input: Số nguyên dương N và dãy N số nguyên a1,a2,...,aN Output: Giá trị lớn nhất Max của dãy số. Ý tưởng: Chọn Max=a1 Lần lượt với i từ 2 đến N, so sánh ai với a1, nếu ai>a1 thìgán Max=aiThuật toán giải được mô tả như sau:  Nhập N>0 và dãy a1,a2,…,aN.  Max  a1, i  2;  Nếu i > N thì đưa giá trị Max rồi kết thúc;  Nếu ai > Max thì Max  ai i  i + 1 rồi quay lại bước 3.Bài toán 2: Tìm UCLN của hai số nguyên dương m,n.Xác định bài toán: Input : 2 số nguyên dương m,n. Output : UCLN của 2 số.Ý tưởng 01: UCLN(m,n)=UCLN(m,m-n) (Giả sử m>n)Thuật toán giải được mô tả như sau:  Nhập 2 số m,n > 0.  Nếu m=n thì đưa ra UCLN(m,n)=m;  Nếu m > n thì m  m-n rồi quay lại bước 2.  Nếu n>m thì n  n-m rồi quay lại bước 2.  Đưa ra kết quả UCLN khi một trong m hoặc n=0 (Nếu m=0 thì UCLN(m,n)=n còn nếu m≠0 thì UCLN(m,n)=m)Ý tưởng 02: UCLN(m,n) = UCLN(n,m mod n)Thuật toán giải 02 : dành cho bạn đọc.Bài toán 3: Cho dãy A gồm N số nguyên a1,a2,…,aN. Sắp xếpcác số hạng để dãy A là trở thành dãy không giảm (tức là sốhạng sau luôn lớn hơn hoặc bằng số hạng trước)Xác định bài toán: Input: Dãy A gồm N số nguyên a1,a2,…,aN. Output: Dãy A đã được sắp xếp trở thành dãy khônggiảmÝ tưởng 01: Với mỗi cặp số hạng đứng liền kề nhau trong dãy, nếusố đứng trước lớn hơn số đứng sau thì ta đổi chỗ hai số chonhau. Quá trình lặp lại cho đến khi không còn sự đổi chỗ xảyra.Thuật toán giải được mô tả như sau:  Nhập N>0 và dãy a1,a2,…,aN.  MN  Nếu M < 2 thì đưa ra dãy A được sắp xếp rồi kết thúc.  Nếu M ≥ 2 thì M  M-1, i  0  i  i+1  Nếu i > M thì quay lại bước 3.  Nếu ai > ai+1 thì tráo đổi vị trí ai và ai+1  Quay lại bước 5. Ý tưởng 02 : Chia dãy cần sắp xếp thành 2 phần, lấy thành phần giữa X làm chuẩn để so sánh. • Tìm một phần tử A ở dãy trên có giá trị lớn hơn X • Tìm một phần tử B ở dãy dưới có giá trị nhỏ hơn X • Hoán vị A và B. • Tiếp tục như vậy cho đến khi ta đạt được dãy trên chỉ gồm các phần tử nhỏ hơn X, dãy dưới chỉ gồm các phần tử lớn hơn X. • Áp dụng thuật toán trên vào dãy trên và dãy dưới (đệ quy) cho đến khi không chia được nữa. Thuật toán giải 02: bạn thử mô tả xem sao, đây coi như là một bài tập nhỏ cho các bạn yêu thích lập trình. Bài toán 4: Cho dãy A gồm N số nguyên a1,a2,…,aN và một số X. Hãy xác định xem giá trị của X có nằm trong dãy A không? Nếu có thì nằm ở đâu ? Xác định bài toán: Input: dãy A gồm N số nguyên a1,a2,…,aN và số X. Output: X có thuộc A không? Nếu có thì nằm ở vị trí nào? Ý tưởng: So sánh từng phần tử của dãy với X. Nếu có phần tử ai = X thì đưa ra thứ tự của phần tử thứ i thỏa ai = X. Thuật toán giải được mô tả như sau :  Nhập N>0 ,dãy a1,a2,…,aN ,và số X  i  1.  Nếu i > N thì kết thúc và đưa kết quả ...