Category: Lập trình


Đây là bài viết về cách sử dụng phương pháp đệ qui trong lập trình do mình tìm hiểu. Mình chỉ chia sẽ nhưng cái mà mình biết để chúng ta cùng trao đổi;

Theo mình thì, đệ quy và quy nạp gần như là tương đương nhau, bạn có thể dùng quy nạp để chứng minh hàm đệ quy của bạn viết là đúng.

Đệ quy là khái niệm không khó và rất phổ biến, giải thích lại thì tốn thời gian mà chưa chắc đã đầy đủ hơn sách vở hoặc các nguồn có sẵn và rất nhiều trên mạng, vì vậy bạn chịu khó google, wikipedia, hay đọc sách là sẽ rõ ngay.

Mình chỉ tập trung vào tính chất LIFO của đệ qui. Vì tôi là người mới học lập trình nên không cần quan tâm đến cách hàm đệ quy xử dụng bộ nhớ theo kiểu stack như thế nào mà có thể hình dung theo một hướng trừu tượng hơn. Ví dụ bạn viết 1 hàm tính giai thừa cho n (n!) . Tạm gọi là gt (n);

gt(n)
{
if
n = 0 return 1
else
return g(n-1)*n
}

Hàm sẽ gọi giai thừa của n-1, rồi sau đó nhân với n để ra giai thừa của n.
Bây giờ giả sử bạn gọi :

gt(5)
gt(5) sẽ gọi gt(4)
gt(4) sẽ gọi gt(3)
gt(3) sẽ gọi gt(2)
gt(2) sẽ gọi gt(1)
gt(1) sẽ gọi gt(0)
gt(0) trả về giá trị 1

gt(1) sẽ trả về 1*gt(0) = 1
gt(2) sẽ lấy 2*gt(1) = 2*1 = 2
gt(3) sẽ lấy 3*gt(2) = 3*2 = 6
gt(4) sẽ lấy 4*gt(3) = 4*6 = 24
gt(5) sẽ lấy 5*gt(4) = 5*24 = 120

bạn tưởng tượng mỗi lần gọi hàm sẽ chiếm 1 phần của bộ nhớ máy tính, quy trình gọi sẽ là
gt(5)->gt(4)->gt(3)->gt(2)->gt(1)->gt(0)
sau khi gt(0) trả về 1, nó sẽ bị tống khứ khỏi bộ nhớ (vì đã hoàn thành nhiệm vụ và giữ lại chẳng để làm gì), bộ nhớ lúc này chỉ còn:
gt(5)->gt(4)->gt(3)->gt(2)->gt(1)
sau khi gt(1) trả về 1, nó cũng sẽ bị tống khứ khỏi bộ nhớ, bây giờ là:
gt(5)->gt(4)->gt(3)->gt(2)
….
cho đến gt(5) và rồi ko còn gì.

gt(0) được gọi sau cùng, nhưng được giải phóng đầu tiên, gt(1) được gọi kế cuối nhưng được giải phóng khỏi bộ nhớ ngay sau khi giải phóng gt(0).

gt(5) được gọi đầu tiên, nhưng được giải phóng khỏi bộ nhớ sau cùng.

Đó là lý do tại sao đệ quy mang tính chất LIFO.
Đệ quy chỉ nên tránh khi chúng ta có thể dùng phép lặp, nhưng không phải lúc nào tránh đệ quy cũng đem lại lợi ích về bộ nhớ vì đôi lúc, bất chấp dùng đệ quy hay vòng lặp thì bộ nhớ vẫn bị chiếm dụng 1 lượng như nhau. Nếu mới học như mình thì bạn đừng ngại sử dụng đệ quy nhé.

Còn đây là link down 1 số bái toán đệ qui để bạn có thể luyện tay thêm :d:http://www.mediafire.com/?hvk3k3e92h2ncfk

Chúc bạn học tốt

Hôm nay, mình viết bài này để hướng dẫn một số bạn mới dùng thử OS Linux để lập trình. Trong Linux trình debug GDB chắc chắn sẽ rất hữu dụng cho nhưng bạn mới làm quen với Linux.Sau đây là bài hướng dẫn của mình.

Đầu tiên, chúng ta cần phải có hệ điều hành Linux, ở đây tôi sử dụng Ubuntu.

 

 

 

 

 

 

 

 

Bước 1: Viết 1 đoạn code trong editor và save lại dưới dạng file .c. Ở đây là file debug.c. Sau đó mở Terminal để chạy chương trình.

 

 

 

 

 

 

 

 

 

 

Bước 2: Compile chương trình bằng tùy chỉnh –g trong Terminal. Ở đây là:  gcc –g debug.c.Chúng ta sẽ được 1 file mặc định là a.out .  Nếu các bạn muốn tạo 1 file debug khác thì gõ lệnh: gcc -g -o filename debug.c sẽ ra được file filename.

 

 

 

 

 

 

 

 

 

 

Bước 3: Vào trình debug GDB bằng lệnh gdb [filename].

 

 

 

 

 

 

 

 

 

 

Bước 4: Đặt Breakpoint vào chương trình bằng lệnh: break [line number].

 

 

 

 

 

 

 

 

 

 

Bước 5: Sau khi đặt Breakpoint ta sẽ được như hình trên. Tiếp theo ta dùng lệnh run để bắt đầu chạy debug.

 

 

 

 

 

 

 

 

 

Sau khi nhập giá trị để chạy chương trình, chúng ta sẽ nhân được code của dòng mình đã đặt Breakpoint.

 

 

 

 

 

 

 

 

 

Bước 6: In giá trị của từng biến sau khi debug. Ở đây ta dùng lệnh print [tên biến] hoặc p [tên biến]. Ta sẽ nhận được giá trị i là 1, j là 1 và num là 3.

 

 

 

 

 

 

 

 

 

 

Bước 7: Dùng lệnh next hoặc n để chạy từng bước chương trình, sau khi chạy từng bước ta có thể in ra để kiếm tra các giá trị. Ở các hình bên trên, cho chạy từng bước đến khi đến thoát khỏi vòng lập ta sẽ được kết quá cuối cùng.

Bài này do mình tự tìm tòi tài liệu và làm thử nên có gì sai sót xin các bạn góp ý dùm mình qua Email:ka_lick@yahoo.com.

Chúc bạn học tốt :D.

Bài 1:Cho số tự nhiên A. Hãy tìm số tự nhiên N nhỏ nhất sao cho N lũy thừa N (nhân N cho chính nó N lần) chia hết cho A. Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị: 1 ≤ A ≤ 10^9.

Cách giải:

 

 

 

 

 

 

 

 

 

 

 

 

Bài 2:Xem công thức tính sau đây (đề thi tuyển sinh cao học ngành KHMT, năm 2011):  

 

 

 

Trong đó Max, Min lần lượt là giá trị lớn nhất, nhỏ nhất của n số thực (được nhập vào từ
thiết bị nhập chuẩn) a0, a1, …, an-1.
Chỉ dùng duy nhất 1 vòng lặp (for hoặc while), đề xuất cách thức để nhập n số thực như
trên và tính giá trị  của biểu thức Aver, xuất kết quả  tính ra thiết bị  xuất chuẩn. Viết
chương trình để minh họa đề xuất đó.

Cách giải:

Vì chỉ dùng 1 vòng lập nên chúng ra cần phân tích biểu thức ra.

Sau khi phân tích và biến đổi ta sẽ được biểu thức sau:

Đặt:

Link Source Code bài 1:

http://www.mediafire.com/?nfvc7zhuwmrrcjw

Link Source Code bài 2:

http://www.mediafire.com/?4y670ztqb45op62