tailieunhanh - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG I: THUẬT TOÁN_5

. THUẬT TOÁN ĐỆ QUY. . Khái niệm đệ quy: Đôi khi chúng ta có thể quy việc giải bài toán với tập các dữ liệu đầu vào xác định về việc giải cùng bài toán đó nhưng với các giá trị đầu vào nhỏ hơn. Chẳng hạn, bài toán tìm UCLN của hai số a, b với a b có thể rút gọn về bài toán tìm ƯCLN của hai số nhỏ hơn, a mod b và b. Khi việc rút gọn như vậy thực hiện được thì lời giải bài toán ban đầu có thể tìm được. | CHƯƠNG I THUẬT TOÁN . THUẬT TOÁN ĐỆ QUY. . Khái niệm đệ quy Đôi khi chúng ta có thể quy việc giải bài toán với tập các dữ liệu đầu vào xác định về việc giải cùng bài toán đó nhưng với các giá trị đầu vào nhỏ hơn. Chẳng hạn bài toán tìm UCLN của hai số a b với a b có thể rút gọn về bài toán tìm ƯCLN của hai số nhỏ hơn a mod b và b. Khi việc rút gọn như vậy thực hiện được thì lời giải bài toán ban đầu có thể tìm được bằng một dãy các phép rút gọn cho tới những trường hợp mà ta có thể dễ dàng nhận được lời giải của bài toán. Ta sẽ thấy rằng các thuật toán rút gọn liên tiếp bài toán ban đầu tới bài toán có dữ liệu đầu vào nhỏ hơn được áp dụng trong một lớp rất rộng các bài toán. Định nghĩa Một thuật toán được gọi là đệ quy nếu nó giải bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn. Thí dụ 10 Tìm thuật toán đệ quy tính giá trị an với a là số thực khác không và n là số nguyên không âm. Ta xây dựng thuật toán đệ quy nhờ định nghĩa đệ quy của an đó là an 1 với n 0 và khi n 0 thì a0 1. Vậy để tính an ta quy về các trường hợp có số mũ n nhỏ hơn cho tới khi n 0. 4 procedure power a số thực khác không n số nguyên không âm if n 0 then power a n 1 else power a n a power a n-1 Thí dụ 11 Tìm thuật toán đệ quy tính UCLN của hai số nguyên a b không âm và a b. procedure UCLN a b các số nguyên không âm a b if b 0 then UCLN a b a else UCLN a b UCLN a mod b b Thí dụ 12 Hãy biểu diễn thuật toán tìm kiếm tuyến tính như một thủ tục đệ quy. Để tìm x trong dãy tìm kiếm a1 a2 . an trong bước thứ i của thuật toán ta so sánh x với ai. Nếu x bằng ai thì i là vị trí cần tìm ngược lại thì việc tìm kiếm được quy về dãy có số phần tử ít hơn cụ thể là dãy ai 1 . an. Thuật toán tìm kiếm có dạng thủ tục đệ quy như sau. Cho search i j x là thủ tục tìm số x trong dãy ai ai 1 . aj. Dữ liệu đầu vào là bộ ba 1 n x . Thủ tục sẽ dừng khi số hạng đầu tiên của dãy còn lại là x hoặc là khi dãy còn lại chỉ có một phần tử khác x. Nếu x