toan roi rac

1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy. (Cực đại tạm thời sẽ là số nguyên lớn nhất đã được kiểm tra ở một giai đoạn nào đó của thủ tục.)

2. So sánh số nguyên tiếp sau với giá trị cực đại tạm thời, nếu nó lớn hơn giá trị cực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đó.

3. Lặp lại bước trước nếu còn các số nguyên trong dãy.

4. Dừng khi không còn số nguyên nào nữa trong dãy. Cực đại tạm thời ở điểm này chính là số nguyên lớn nhất của dãy.

b) Dùng đoạn giả mã:

procedure max (a¬1, a2, ..., an: integers)

max:= a1

for i:= 2 to n

if max <ai then max:= ai

{max là phần tử lớn nhất}

Thuật toán này trước hết gán số hạng đầu tiên a1 của dãy cho biến max. Vòng lặp "for" được dùng để kiểm tra lần lượt các số hạng của dãy. Nếu một số hạng lớn hơn giá trị hiện thời của max thì nó được gán làm giá trị mới của max.

1.1.3. Các đặc trưng của thuật toán:

-- Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ.

-- Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán.

-- Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng.

-- Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn, trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của thuật toán phải cho những kết quả như nhau.

-- Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả như ý muốn.

-- Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ liệu khác nhau trong một miền xác định.

1.2. THUẬT TOÁN TÌM KIẾM.

1.2.1. Bài toán tìm kiếm: Bài toán xác định vị trí của một phần tử trong một bảng liệt kê sắp thứ tự thường gặp trong nhiều trường hợp khác nhau. Chẳng hạn chương trình kiểm tra chính tả của các từ, tìm kiếm các từ này trong một cuốn từ điển, mà từ điển chẳng qua cũng là một bảng liệt kê sắp thứ tự của các từ. Các bài toán thuộc loại này được gọi là các bài toán tìm kiếm.

Bài toán tìm kiếm tổng quát được mô tả như sau: xác định vị trí của phần tử x trong một bảng liệt kê các phần tử phân biệt a1, a¬2, ..., an hoặc xác định rằng nó không có mặt trong bảng liệt kê đó. Lời giải của bài toán trên là vị trí của số hạng của bảng liệt kê có giá trị bằng x (tức là i sẽ là nghiệm nếu x=ai và là 0 nếu x không có mặt trong bảng liệt kê).

1.2.2. Thuật toán tìm kiếm tuyến tính: Tìm kiếm tuyến tính hay tìm kiếm tuần tự là bắt đầu bằng việc so sánh x với a1; khi x=a1, nghiệm là vị trí a1, tức là 1; khi xa1, so sánh x với a2. Nếu x=a2, nghiệm là vị trí của a2, tức là 2. Khi xa2, so sánh x với a3. Tiếp tục quá trình này bằng cách tuần tự so sánh x với mỗi số hạng của bảng liệt kê cho tới khi tìm được số hạng bằng x, khi đó nghiệm là vị trí của số hạng đó. Nếu toàn bảng liệt kê đã được kiểm tra mà không xác định được vị trí của x, thì nghiệm là 0. Giả mã đối với thuật toán tìm kiếm tuyến tính được cho dưới đây: