Có một vấn đề nan giải đối với những bạn mới học lập trình web. Vì nó được sử dụng ở trong các ứng dụng như đệ quy menu đa cấp, chuyên mục đa cấp nhưng thực sự người nắm được giải thuật này không nhiều. Vì thế trong loạt series PHP căn bản này chúng ta sẽ tìm hiểu thêm về giải thuật này nhé.
Bài 12: Giải thuật đệ quy trong PHP
Nội dung bao gồm:
Đệ quy là gì?
Đệ quy tuyến tính
Đệ quy nhị phân
Đệ quy hổ tương
Khử đệ quy
1. Giải thuật đệ quy là gì ?
Đệ quy liên quan đến rất nhiều trong toán học, vì vậy ta quay lại toán học một chút. Có một tính chất trong toán học được gọi là đệ quy. Nếu trong đó là một lớp các đối tượng có các tính chất giống nhau và có mối liên hệ với nhau. kết quả của bước 1 là một thành phần của bước 2, bước 2 là thành phần bước 3, ….
Ví dụ: Bố của tôi là ông A, Bố của Bố tôi là ông B, … Cứ như vậy đệ quy n lần sẽ tìm được nguồn gốc của tôi ( 
hơi căng ). Và đây có thể gọi là chương trình đệ quy nhằm tìm ra nguồn gốc của tôi. Giải thuật đệ quy cũng có thể được gọi là phương pháp chia để trị.
Muốn dùng được đệ quy thì bạn phải biết viết hàm vì mỗi lần đệ quy là hàm gọi lại chính nó. Một chương trình đệ quy đều phải có điều kiện dừng. Vì nếu không có thì chương trình sẽ gọi vô hạn (lặp vô hạn). Vd tính tổng từ 1 -> n thì điều kiện dừng là khi tới n rồi thì không được tính nữa. còn nếu tính từ n quay về 1 thì điều kiện dừng là: n = 1.
2. Đệ quy tuyến tính
Đây là loại đệ quy mà ở bên trong hàm đệ quy chỉ gọi duy nhất 1 lần đến chính nó.
Ví dụ: Cho n = 100, tính tổng các số từ 1 tới 100.
Ở bài này nếu dùng vòng lặp thì đơn giản. Chúng ta lặp từ 1 đến 100 và mỗi vòng lặp cộng dồn lại sẽ ra tổng. Bài giải cho vòng lặp như sau:
Còn nếu với giải thuật đệ quy thì ý tưởng là ở mỗi lần đệ quy ta sẽ lấy số đó cộng với hàm chính nó và biến truyền vào là số đó trừ đi 1. Với điều kiện dừng là nếu số đó = 1 thì dừng vòng lặp và trả kết quả về. Phân tích thêm kỹ hơn tức là mỗi bước đệ quy chính là một lần lặp. Cộng dồn tổng tất cả các lần đệ quy chính là cộng dồn tổng các lần lặp nên kết quả nó sẽ thương đương với bài giải bằng vòng lặp trên.
Với giải thuật đệ quy này thì trong hàm gọi lại chính nó chỉ 1 lần. (tức là chỉ có 1 đoạn code tinhtong($n-1)). Trong mỗi bước đệ quy sẽ lấy giá trị $n truyền vào cộng với giá trị của tinhtong($n-1). Cứ lặp đệ quy như vậy cho tới khi biến $n truyền vào hàm = 1 thì dừng đệ quy. bài toán được mô phỏng như sau:
Biến $n truyền vào bằng 100; giá trị return bằng 100 + đệ quy lần 2 với tham số như sau: tinhtong(100-1). Cứ như vậy mỗi một lần đệ quy quy sẽ bằng biến truyền vào + lần đệ quy tiếp.
Luồng cộng như sau: 100 + ( 100-1 = 99 ) + (99 – 1 = 98) + …. + (2-1 = 1) tương đương 100 + 99 + 98 + …. + 1.
3. Đệ quy nhị phân
Đệ quy nhị phân là loại đệ quy mà thân hạm gọi lại chính nó lần 2
Ví dụ: Xuất ra màn hình phần tử thứ 100 của dãy Fibonacci.
Dãy Fibonacci là dãy bắt đầu từ 1 đến n trong đó phần tử thứ $i trong dãy. sẽ bằng tổng 2 phần tử trước nó cộng lại. Vd viết ra dãy từ Fibonacci của 8 phần tử đầu tiên thì ta viết như sau: 1 – 1 – 2 – 3 – 5 – 8 – 13 – 21.
Trong dãy Fibonacci phần tử thứ 1 và thứ 2 có giá trị bằng 1. Đây cũng chính là điêu kiện dừng của dãy.
Bài giải:
4. Đệ quy phi tuyến
Đây là loại đệ quy mà trong hàm có dùng vòng lặp để gọi lại chính nó.
VD: Tính phần tử thứ 8 của dãy được tính theo công thức :
Ý nghĩa của dãy như sau:
- Nếu n nhập vào mà bé hơn 6 thì trả về chính nó.
- Nếu n nhập vào mà lớn hơn hoặc bằng 6 thì trả về kết quả bằng tổng các số từ 1 tới n-1. với mỗi số lại tính theo quy luật trên. Có nghĩa rằng ví dụ tôi có hàm
phep_tinhvà nhập giá trị 6 vào thì dãy được tính như sau: pheptinh(5) + pheptinh(4) + pheptinh(3) + pheptinh(2) + pheptinh(1)
Bài giải:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | function pheptinh($n){ // Neeus $n < 6 thì trả về chính nó if ($n < 6){ return $n; } else{ // Ngược lại tính tổng từ 1 tới $n - 1, và mỗi phần tử lại gọi làm hàm chính nó $tong = 0; for ($i = 1; $i < $n; $i++){ $tong += pheptinh($n - $i); } return $tong; }} echo pheptinh(6); |
5. Đệ quy hỗ tương
Nghe cái tên thôi cũng hiểu được phần nào. Ta nói đến đệ quy hỗ tương là đệ quy một hàm A gọi sang một hàm B. Trong hàm B lại gọi sang hàm A. Như vậy là chúng gọi lẫn nhau nên người ta gọi là hỗ tương.
Cũng như là các loại đệ quy trên kia, nếu cả 2 hàm A, B đều không có điều kiện dừng thì sẽ bị lặp vô hạn. Điều này rất nguy hiểm nên các bạn phải chú ý.
Ví dụ: Tính giá trị của dãy sau
Ta thấy rằng 2 hàm đệ quy có gọi lẫn nhau và mỗi hàm đều có điều kiện dừng. Đến đây tôi hy vọng không cần giải thích ý nghĩa của 2 hàm này nữa. Dựa vào cấu trúc của 2 hàm này tôi có bài giải như sau:
6. Khử đệ quy
Giải thuật đệ quy rất hay nhưng chi phí để tính toán cho nó thì rất cao. Vì thế người ta thường hay tìm những giải thuật khác để thay thế cho nó. Tuy nhiên trên thực tế chưa có một giải thuật nào chắc chắn cho điều này, có nghĩa là không phải bài nào cũng chuyển được.
Phần này là một quá trình nên tôi không có thời gian cũng như là không đủ trình độ để giải hết các bài đệ quy được. Như ví dụ ở phần đệ quy tuyến tính các bạn thấy tôi đã dùng vòng lặp for để giải bài toán tính tổng và đó cũng là một cách dùng vòng lặp để khử đệ quy.
Trong bài tiếp theo chúng ta sẽ tìm hiểu một thuật toán khác liên quan đến sắp xếp, đó là thuật toán sắp xếp nổi bọt.
Bài 13: Thuật toán sắp xếp nổi bọt trong PHP
Sắp xếp là một công việc rất quan trọng trong việc quản lý dữ liệu. Vì nó giúp chúng ta tìm kiếm thông tin một cách nhanh chóng. Tuy nhiên với lập trình Web thì chúng ta lại rất ít đụng đến các thuật toán sắp xếp. Và PHP cũng đã có cung cấp một số hàm sắp xếp sẵn rất tiện lợi. Nhưng chúng ta đang học lập trình nên bạn cũng không nên bỏ qua các kiến thứ về thuật toán này.
Ở bài này chúng ta sẽ nghiên cứu một thuật toán sắp xếp đơn giản nhất đó là: thuật toán sắp xếp nổi bọt (bubble sort). Ý tưởng của thuật toán bắt nguồn từ việc so sánh 2 phần tử cạnh nhau và hoán vị chúng nếu không đúng vị trí. Ta có thể tiến hành từ trái qua phải hoặc từ phải qua trái tùy vào nhu cầu của mình.
Note: Để tiện việc giảng giải tôi gọi
$nlà tổng số phần tử của mảng. 1 là vị trí phần tử đầu tiên của mảng. (trong mảng bắt đầu từ 0 nhưng tôi gắn nó bằng 1 để dễ dung hơn)
Nội dung chính
1. Sắp xếp nổi bọt tăng dần
2. Sắp xếp nổi bọt giảm dần
3. Đưa thuật toán sắp xếp nổi bọt vào hàm
1. Sắp xếp nổi bọt tăng dần
Thuật toán sắp xếp nổi bọt tăng dần được xử lý như sau:
Cho vòng lặp $i chạy từ 1 tới ($n-1):
Lần lặp 1: $i = 1. Lần lược so sánh với các vị trí khác bắt đầu từ ($i + 1) tức là vị trí 2. Nếu phần tử thứ 1 lớn hơn các phần tử đứng sau bắt đầu từ 2 thì hoán vị chúng.
Lần lặp 2: $i = 2. Lần lược so sánh với các vị trí khác bắt đầu từ ($i + 1) tức là vị trí 3. Nếu phần tử thứ 2 lớn hơn phần tử đứng sau nó bắt đầu từ 3 thì hoán vị chúng.
Cứ như vậy cho đến khi ta lặp lần thứ ($n – 1). Lúc này biến $i = ($n-1). Chúng ta so sánh với phần tử cuối cùng ($n) và hoán vị nếu không thỏa mãn.
Ví dụ: Cho mảng sau: $mang = array(1, 5, 9, 2, 4, 9). Bạn Hãy dùng thuật toán sắp xếp nổi bọt để sắp xếp mảng theo thứ tự tăng dần.
Mảng này có 6 phần tử bắt đầu từ 0 -> 5. Vì thế ta có bài giải như sau:
ví dụ minh họa
Trong bài này ta sử dụng vòng lặp for lồng nhau để duyệt các phần tử. Với mỗi vòng lặp $i. Ta sẽ dùng vòng lặp $j để duyệt từ vị trí tiếp ($i + 1) theo đến cuối mảng. Nếu không đúng vị trí thì thực hiện đổi vị trí cho nhau.
2. Sắp xếp nổi bọt giảm dần
Thuật toán sắp xếp nổi bọt giảm dần thì ý tưởng cũng tương tự như so sánh tăng dần. Chỉ có khác khi so sánh 2 phần tử với nhau thì nếu phần tử thứ $i bé hơn phần tử ($i + 1)thì hoán vị 2 vị trí đó. Với ví dụ trên ta có bài giải như sau:
ảnh ví dụ minh họa
3. Đưa thuật toán sắp xếp nổi bọt vào hàm
Tôi có thắc mắc là tại sao chúng ta lại code một cách không chuyên nghiệp gì hết vậy. Trong khi chúng ta đã được học bài xây dựng hàm trong php? Để chương trình có tính mở rộng và dễ quản lý, bảo trì thì chúng ta nên đưa đoạn code sắp xếp vào một hàm.
ảnh ví dụ minh họa
Thuật toán sắp xếp nổi bọt trong php rất đơn giản và dễ cài đặt. Vì thế nó được sử dụng rât rộng rãi trong các chương trình học lập trình ở các trường đại học ở bộ môn cấu trúc dữ liệu căn bản.
0 Lời bình