Kỹ thuật lập trình đệ quy

Kỹ thuật đệ quy

Khi một hàm đệ quy gọi đến chính nó thì mỗi lần gọi máy sẽ tạo ra tập các biến cục bộ mới hoàn toàn độc lập với biến cục bộ đã tạo ra trong lần gọi trước. Có một sự tương ứng giữa các lời gọi hàm và lần thoát khỏi hàm theo thứ tự ngược lại: lần ra khỏi hàm đầu tiên tương ứng với lần gọi hàm cuối cùng.

Xây dựng một chương trình đệ quy

 Đệ quy gián tiếp : trong một hàm có lời gọi hàm đến một hàm khác và bên trong hàm này lại có lời gọi hàm đến hàm ban đầu. Thụng thường những dạng chương trỡnh đệ quy giỏn tiếp thỡ khú theo dừi và gỡ rối, nên khi xây dựng chương trình loại này phải hết sức cẩn thận.

Các ví dụ đệ quy

Với B2 thì đơn giản do chuyển 1 đĩa, còn bước B1 và B3 phải di chuyển nhiều hơn 1 đĩa nên chúng sẽ bao gồm nhiều bước nhỏ trong đó. Ta thử phân tích như sau: ý tưởng là đi từ phần đuôi và so sánh với phần tử cuối cùng của mảng với biến tạm m, chọn ra phần tử lớn nhất ⇒ lưu lại vào m.

Khử đệ quy

Cấu trúc dữ liệu ngăn xếp lưu trữ theo kiểu Last In First Out thoả các yêu cầu trên nên được sử dụng để lưu trữ thông tin trạng thái của quá trình xử lý đệ quy. Quá trình trên gọi là khử đệ quy, đôi khi việc khử đệ quy cũng không dễ dàng gì, nên nhiều khi cũng phải chấp nhận chương trình đệ quy!.

Phương pháp sinh

Như vậy nếu ta đang có một dãy x đại diện cho tập con, nếu x là cấu hình kết thúc thì có nghĩa tất cả các phần tử trong x đều đạt tới giới hạn trên thì quá trình sinh kết thúc. Khi đó hoán vị kế tiếp sinh ra phải lớn hơn hoán vị hiện tại, và hơn nữa nó phải đủ lớn hơn hoán vị hiện tại theo nghĩa không có hoán vị nào khác chen vào giữa nó khi sắp theo thứ tự từ điển.

Thuật toán quay lui (Back Tracking)

Mô hình chung của thuật toán quay lui xác định thành phần thứ i được mô tả tổng quát như sau: (thuật toán này thử cho xi nhận lần lượt những giá trị mà nó có thể nhận). Đầu tiên các giá trị trong B này phải được khởi tạo là true, sau khi gán j cho xi thì ghi nhận Bj = false, sau khi gọi xong thủ tục Try(i+1) thì thiết lập lại Bj = true, để đánh dấu nó chưa được dùng để cho bước thử tiếp theo. Để dễ phân tích ta mô tả quân hậu theo dòng; quân hậu 1 ở dòng 1, quân hậu i ở dòng i…Do mỗi quân hậu chắc chắn nằm trên các dòng khác nhau nên ta chỉ cần xác định vị trí cột của mỗi quân hậu là xong.

Các đường chéo Trên Trái - Dưới Phải như hình vẽ dưới, mỗi đường chéo này sẽ đi qua các ô, các ô này có tính chất: dòng - cột = C (hằng số). Yêu cầu: Cho một bàn cờ tổng quát dạng nxn, hãy chỉ ra một hành trình của một quân Mã, xuất phát từ một vị trí bắt đầu đi qua tất cả các ô còn lại của bàn cờ, mỗi ô đi đúng một lần. Ngoài ra, nếu tại một bước tìm đường đi, nếu không tìm được đường đi tiếp thì thuật toán sẽ quay lui lại nước đi trước và tìm đường đi khác….

Tìm kiếm

Ý tưởng chính: duyệt tuần tự từ phần tử đầu tiên, lần lượt so sánh khóa tìm kiếm với khoá tương ứng của các phần tử trong danh sách (trong trường hợp mô tả trên là so sánh x và a[i]). Cho đến khi gặp phần tử cần tìm hoặc đến khi duyệt hết danh sách.

Một số phương pháp sắp xếp cơ bản

Sau lần duyệt như vậy, khóa nhỏ nhất trong dãy khóa sẽ được chuyển về vị trí đầu tiên và vấn đề trở thành sắp xếp dãy khoá từ k[n] đến k[2]. Ý tưởng chính: xuất phát từ đầu dãy, tìm những phần tử còn lại không thoả thứ tự sắp xếp với phần tử đang xét, hoán vị các phần tử tương ứng để thỏa thứ tự. Tư tưởng chính của thuật toán ShellSort là: với mỗi bước h, áp dụng thuật toán sắp xếp kiểu chèn từng dãy con độc lập để làm mịn dần các phần tử trong dãy chính.

Xét trong ví dụ trên, nếu chúng ta dùng phương pháp chèn thì với phần tử a[5] = 2 là phần tử nhỏ nhất trong dãy, do đó nó phải chèn vào vị trí thứ 1, tức là phải chèn trước 4 phần tử trước nó. Ta có nhận xét khi đó dãy con thứ 2 đã có thứ tự, nếu dãy con 1 và dãy con 3 có một phần tử thì chúng cũng đã có thứ tự, khi đó dãy ban đầu đã được sắp.  Lần lượt phân loại các chữ số theo hàng đơn vị, hàng chục, hàng trăm..Tại mỗi bước phân loại ta sẽ nối các dãy con từ danh sách đã phân loại theo thứ tự 0 → 9.

Giới thiệu Stack – ngăn xếp

 Trong trình biên dịch, stack dùng để lưu trữ các lời gọi hàm, ví dụ như hàm A gọi hàm B, hàm B lại gọi hàm C, khi hàm C thực hiện xong thì sự điều khiển chương trình sẽ trở về thực hiện chương trình B. Tức là đưa vào thông tin: di chuyển N-1 đĩa từ cọc trung gian đến cọc đích, di chuyển 1 đĩa từ nguồn sang đích, và cuối cùng đưa N-1 đĩa từ cọc nguồn sang trung gian. Khi đó lấy từ stack ra chúng ta sẽ có thứ tự ngược lại là: di chuyển N-1 đĩa từ cọc nguồn sang trung gian, di chuyển 1 đĩa từ cọc nguồn sang đích và cuối cùng di chuyển N-1 đĩa từ cọc trung gian sang đích.

Khi đó chúng ta sẽ đưa vào stack đoạn bên phải, nếu đoạn bên trái nhiều hơn một phần tử ta cập nhật lại right = i, khi đó chúng ta sẽ lặp lại với đoạn [left..i] một cách tương tự, khi đoạn bên trái hết thì chúng ta sẽ lấy từ trong stack ra những đoạn được lưu giữ để thực hiện tiếp tục..quá trình thực hiện cho đến khi stack rỗng. Như chúng ta đã biết một biểu thức được biểu diễn dưới dạng hậu tố hay còn gọi là ký pháp nghịch đảo Ba Lan RPN (Reverse Polish Notation) giúp ích rất nhiều cho việc tính toán giá trị biểu thức tốt hơn là biểu thức dạng trung tố. Các trình biên dịch máy tính thường chuyển những biểu thức trung tố sang hậu tố để dễ xử lý hơn. Trong phần này chúng ta sẽ tìm hiểu thuật toán để chuyển một biểu thức dạng trung tố đơn giản sang biểu thức hậu tố tương ứng. Chúng ta có thể thấy cách biểu diễn của trung tố cần phải xử lý dấu ngoặc trong khi biểu thức hậu tố thì không cần sử dụng. Đây là ưu điểm của biểu thức hậu tố. Để chuyển đổi chúng ta sử dụng một Stack dùng lưu trữ các toán tử và dấu ngoặc mở. Duyệt qua từng phần tử trong biểu thức trung tố, gọi C là phần tử đang xét:. Sau đó đưa C vào stack. Cuối cùng lấy tất cả những phần tử còn lại trong stack xuất ra ngoài. Thuật toán chuyển đổi từ trung tố sang hậu tố:. // stack lớn hơn thì lấy ra. Đọc Xử lý Stack Output. ) Lấy trong stack ra cho đến khi gặp ngoặc (. Trong những năm đầu 1950 nhà logic học người Ba Lan Jan Lukasiewicz đã chứng minh rằng: biểu thức hậu tố không cần có dấu ngoặc vẫn có thể tính đúng bằng cách đọc lần lượt biểu thức từ trái qua phải và dùng một stack để lưu trữ kết quả trung gian.

Giới thiệu Queue – hàng đợi

Để sử dụng cấu trúc dữ liệu mảng mô tả Queue người ta dùng hai chỉ số là Front và Rear để đánh dấu vị trí đầu và cuối của hàng đợi trong mảng. Tương tự như phần Stack ở đây sẽ xây dựng một cấu trúc Queue chứa các phần tử có kiểu dữ liệu là Data, Data là kiểu dữ liệu do người dùng định nghĩa có thể số nguyên, thực, ký tự hoặc một cấu trúc dữ liệu nào đó tùy ý. Thông thường các vấn đề liên quan đến cơ chế “vào trước ra trước” đều có thể dùng cấu trúc dữ liệu Queue.

Đây là dạng bài toán sản xuất & tiêu dùng, mặt hàng được sản xuất ra sẽ được lưu vào kho, hàng hóa từ kho này sẽ được xuất ra ngoài cho nhà phân phối. Việc duyệt một đỉnh v sẽ cho phép chúng ta đi duyệt tiếp với những đỉnh kề của nó sao cho thỏa thứ tự ưu tiên theo chiều rộng, tức là đỉnh nào gần với v nhất sẽ được duyệt trước. Khi đó tại mỗi bước xét một đỉnh v ta có một danh sách các đỉnh kề của nó, những đỉnh này chờ được duyệt do đó ta sẽ đưa những đỉnh này vào cuối danh sách chờ được duyệt, khi đó những đỉnh nào vào danh sách chờ trước thì sẽ được duyệt trước.