TAILIEUCHUNG - 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

• Toán học
• thuật toán
• khái niệm thuật toán
• toán rời rạc
• giáo trình toán rời rạc
• tài liệu toán rời rạc
• Thuật toán và tư duy thuật toán
• Đặc trưng cơ bản về thuật toán
• Thiết kế thuật toán
• Hiệu quả giảng dạy thuật toán
• Cài đặt thuật toán
• Vấn đề tư duy thuật toán
• Ngôn ngữ lập trình
• Bài giảng thuật toán
• Biểu diễn thuật toán
• Kỹ thuật thiết kế thuật toán
• Phân tích thuật toán
• Đáng giá thuật toán
• Thuật toán máy tính
• Thuật toán tham lam
• Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Bài toán sắp xếp
• Sắp xếp chèn
• Tự học lập trình
• Bài giảng Tin học 10
• Bài giảng Tin học 10 Bài 4
• Bài 4 Bài toán và thuật toán
• Bài giảng Bài toán và thuật toán
• Khái niệm bài toán
• Thuật toán tìm Max của một dãy số
• Cẩm nang thuật toán
• Phương pháp giải thuật toán
• Thuật toán thông dụng
• Thuật toán sắp xếp
• Thuật toán tìm kiếm
• Thuật toán xử lý chuỗi
• Thuật toán chuyên dụng
• Một số vấn đề về thuật toán
• Độ phức tạp thuật toán
• Phương pháp trong thuật toán
• Tính đúng đắn của thuật toán
• thuật toán DDA
• thuật toán bresenham
• thuật toán đường tròn
• thuật toán MidPoint
• thuật toán vẽ Ellipse
• Thuật toán tô màu
• Bài giảng Phân tích thuật toán
• Tính chất cơ bản của thuật toán
• Độ phức tạp của thuật toán
• Ước lượng tiệm cận
• Thuật toán Google
• Thuật toán Sand
• Thuật toán chim ruồi
• Thuật toán ngựa vằn Zebra Box
• Thuật toán Chim cánh cụt
• Thuật toán Gấu trúc Panda
• Đề thi cuối kì môn Toán kỹ thuật
• Bài thi môn Toán kỹ thuật
• Ôn thi Toán kỹ thuật
• Luyện thi Toán kỹ thuật
• Tài liệu thi Toán kỹ thuật
• Hướng dẫn thi Toán kỹ thuật
• Lý thuyết thuật toán tìm đường
• Thuật toán tìm đường
• Thuật toán tìm đường đi ngắn nhất
• Thuật toán tìm đường đi
• Xây dựng thuật toán
• Thuật toán xử lý thông tin
• Đặc trưng của thuật toán
• Thuật toán Euclid cải tiến
• Ngôn ngữ thuật toán
• Diễn tả thuật toán
• Phân tích thiết kế thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Trình diễn thuật toán
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Tính chất của thuật toán
• Đặc tả thuật toán
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Quy hoạch động
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Khóa luận tốt nghiệp
• Khóa luận tốt nghiệp Kế toán Kiểm toán
• Kế toán Kiểm toán
• Kế toán thanh toán
• Nguyên tắc kế toán thanh toán với người mua
• Nguyên tắc kế toán thanh toán với người bán
• Thuật toán gần đúng
• Bài toán tối ưu tổ hợp
• Tối ưu tổ hợp
• Toán tối ưu tổ hợp
• Ứng dụng thuật toán gần đúng
• Tìm hiểu thuật toán gần đúng
• Tài liệu thuật toán gần đúng
• Sáng kiến kinh nghiệm
• Bài tập xây dựng thuật toán giải bài toán
• Thuật toán giải bài toán
• Xây dựng thuật toán máy tính
• Kỹ thuật kiểm toán
• tài liệu Kỹ thuật kiểm toán
• bài giảng Kỹ thuật kiểm toán
• kế toán kiểm toán
• nghiệp vụ kế toán
• kế toán tài chính
• kế toán doanh nghiệp