Cơ bản về cấu trúc dữ liệu và giải thuật – Phần một: Đệ quy

Cấu trúc dữ liệu và giải thuật đóng vai trò quan trọng trong việc kết hợp thuật toán để đưa ra cách giải quyết bài toán. Một bài ...



Cấu trúc dữ liệu và giải thuật đóng vai trò quan trọng trong việc kết hợp thuật toán để đưa ra cách giải quyết bài toán. Một bài toán bất kỳ đều bao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên những đối tượng đó. Do đó cần phải xây dựng lên một cấu trúc dữ liệu phù hợp trên các đối tượng nhằm phản ánh quan hệ giữa các đối tượng và hình thành giải thuật là các thao tác trên các đối tượng dữ liệu.

Giải thuật đệ quy
Đệ quy (Recursion) là một trong những giải thuật rất quen thuộc trong lập trình. Một số bài toán buộc phải dùng đệ quy mới giải quyết được (như bài toán duyệt cây). Đệ quy là một giải thuật chứa thao tác gọi lại chính nó. Điều này giúp mô tả một dãy lớn các thao tác bằng một số thao tác ngắn gọn trong đó chứa thao tác gọi lại chính nó.

Hôm nay, chúng ta sẽ cùng tìm hiểu một số khái niệm cơ bản về giải thuật đệ quy và một số bài toán kinh điển sử dụng đệ quy.

Định nghĩa hàm đệ quy
Trong lập trình, một hàm được gọi là đệ quy khi nó gọi chính nó trong thân hàm.
Một hàm đệ quy f(n) được xác định dựa trên giản đồ sau:
Phần cơ bản: Điều kiện thoát khỏi đệ quy, bao gồm một giá trị hoặc một tập giá trị ban đầu: f(0),f(1),..
Phần đệ quy: Tính f(n+1) dựa trên một giá trị f(k) đã biết trước đó
Ví dụ:
Tính n! = (n-1)! * n
Dãy fibonacy: f(n) = f(n-1)+ f(n-2)

Giải thuật đệ quy
Là thuật toán gọi lại chính nó với tham số nhỏ hơn.
Phù hợp để xử lý các đối tượng định nghĩa đệ quy
Ngôn ngữ lập trình cấp cao cho phép người lập trình thiết kế các hàm và thủ tục đệ quy.
Thuật toán: RecAlg(n)
Giả sử giá trị f(một),f(2),..f(k) ban đầu đã biết
If n
Hôm nay, chúng ta sẽ tìm hiểu sâu hơn về 2 kỹ thuật đệ quy nâng cao hơn. Đó là Đệ quy có nhớ và Quay lui (Backtracking)

Đệ quy có nhớ:
Xét bài toán tính C(k,n) đã trình bày giải thuật ở phần trước
Ta có sơ đồ như sau với C(3,5)
[​IMG]

Ở đây có thể thấy có 1 vài công thức bị lặp lại như C(2,3), C(1,2),…
Nếu dùng đệ quy để tính lại các công thức này sẽ mất rất nhiều thời gian
Để giảm bớt thời gian tính toán, ta có thể lưu lại các giá trị đã biết vào 1 mảng để sau này khi gặp lại chỉ việc lấy giá trị ra chứ không cần tính lại.
Như ví dụ trên có thể lưu vào 1 mảng 2 chiều n*n :

Giải thuật mới :
Mã:
long D[100][100] ;
long C( int k , int n ) {
     if ( k == 0 | | k == n ) D[k][n] = 1 ;
else {
     if (D[k][n]


https://whitehat.vn/threads/co-ban-ve-cau-truc-du-lieu-va-giai-thuat-%E2%80%93-de-quy-p2.8287/





COMMENTS

Tên

.:: Connect Trojan ::.,111,.htaccess,2,0-day,3,2017,2,Add-on,16,Anotador,1,AutoIT,17,Ấn Độ,1,BackDoor,1,Bán Sách,13,banhangonline,1,Bảo Mật,96,Bất Động Sản Tại Tiền Giang,4,Bestsellers,13,Binder,1,blog,31,Blogger,4,Blogger Template,1,Botnet,3,Brute,1,Bypass,10,ceh,1,Châu Tinh Trì,2,Checked,6,Chiến tranh,2,Chrome,21,Code,5,coin hive,1,Coin-Hive,2,CoinHive,1,Connect Trojan,342,Connect Trojan ::.,1,Cổ Tích,2,Cổ Trang,11,Crack,3,Crypto,5,CSRF,5,CSS,2,Cuộc Sống,1,DDoS,6,Designer,1,Dich vụ,1,DNS,4,Download,2,du-an,1,DVD LUMION Tiếng Việt của anh Dũng Già Pro,1,Đam Mỹ,1,Đồ Họa,215,Đô Thị,16,e11.me,1,ebook,13,ebook free,286,eBook Phệ Hồn Nghịch Thiên,1,eBook Thịnh Thế Địch Phi,1,Encrypt,1,Encryption,1,epub,77,epub [Tiên hiệp],1,ET-Logger,1,exploit,23,Exploitation,1,Extractor,2,facebook,68,FireFox,15,Flood,2,Forensic,7,full prc,2,game,177,Gerador,3,Gerenciador,1,Get Root,3,GHDB,3,Giả Tưởng,1,giaitri,1,Google,15,H&Y Shop,2,Hacker,3,Hacking,10,Hacking and Security,6,Hacking Tools,36,Hài hước,8,Hành Động,9,He Thong Site Phim,25,Hijacking,6,Hình Sự,5,hivecoin.hive coin,1,Hỏi Xoáy Đáp Xoay Trên VTV3,1,Hồng Kông,3,HTML,1,Huyền Ảo,92,Hướng dẫn Internet cơ bản,1,IFTTT,703,Imgur,2,Infographic,1,Information Disclosure,1,Internet Explorer,3,IT News,39,J2TeaM,29,J2TeaM Tools,9,JavaScript,6,Javascript Injection,3,Juno_okyo's Blog,23,Khóa Học,27,khoá học miễn phí,16,Khóa học Photoshop,19,Khóa học sử dụng mã độc và phòng chống mã độc,1,Khoa Huyễn,6,kiemhiep,9,Kiếm Hiệp,20,Kiếm Tiền MMO,31,kiếm tiền rút gọn link,1,KilerRat,1,Kinh Dị,25,Kinh Dị - Ma,6,Kinh Doanh,73,kinhdi,1,kinhdoanh,5,KRACK Attacks,1,Lãng mạn,1,Lập trình,1,Lịch Sử,5,Linux,1,Local Attack,2,Logins/Cadastro,1,Lỗi Web,1,Lồng Tiếng,6,Lược Sử Hacker,2,Mã Giảm Giá,1,Mã Hóa,48,Malware,3,Master-Code,31,Máy Tính,1,Metasploit,2,Microsoft,4,mobile hacking,2,monero,1,Movie,25,MySQL,1,NEW PRODUCTS,19,NGHỆ THUẬT ẨN MÌNH,13,ngontinh,10,Ngôn Tình,151,Nhân Vật Lịch Sử,2,Nhật Bản,1,Nhựt Trường Group,1,NjRat,5,Nước,1,open redirect,1,Oracle,1,Path Disclosure,2,pdf,77,Pen-Test,6,Pentest Box,9,phanmem,22,phanmemdienthoai,3,phanmemmaytinh,10,phần mềm,10,Phim 18,2,Phim 2012,1,Phim 3D,1,Phim Âm Nhạc,2,Phim Bộ,58,Phim Chiến Tranh,5,Phim Dã Sử - Cổ Trang,6,Phim Đài Loan,6,Phim Đang Cập Nhập,5,Phim Đề Cử,4,Phim Hài Hước,26,Phim Hàn Quốc,33,Phim HD Chất Lượng Cao,5,Phim Hoàn Thành,7,Phim Hoạt Hình,2,Phim Hot,2,Phim Hồng Kông,20,Phim HQ,15,Phim Kinh Dị,8,Phim lẻ,7,Phim Mới 2007,1,Phim Mới 2010,1,Phim Mới 2011,4,Phim Mới 2012,2,Phim Mới 2013,2,Phim Mới 2014,6,Phim Mới 2015,4,Phim Nhật Bản,4,Phim SD,12,Phim Thái Lan,6,Phim Thần Thoại,4,Phim Tình Cảm,35,Phim Trung Quốc,37,Phim Truyền Hình,32,Phim Viễn Tưởng,1,Phim Võ Thuật,36,Phim Xã Hội Đen,1,Phishing,5,PHP,16,Plugin,1,Port,1,prc,79,Programming,15,Python,1,Quảng Cáo,1,rat,457,Recovery,3,Remote Code Execution,1,Remote Desktop,1,Reverse Engineering,6,rút gọn link,1,sach,46,Sách,33,Sách Nghệ Thuật Sống,12,Sách Tâm Linh,1,Sách Tiếng Anh,2,sachiep,2,Sản Phẩm,1,Sắc Hiệp,16,Scam,1,Scanner,10,Security,66,SEO,5,share,1,Shell,5,Social Engineering,4,Software,22,Source Unity,1,SQL injection,21,Sức Khỏe,1,Symlink,3,Tài Liệu,1,Tản mạn,7,Taudio,2,Tâm lý xã hội,1,Testador,1,Thái Lan,2,Tham Khảo,3,thamkhao,11,Thành Long,1,them,1,Thiết Kế Web,28,Thời Trang,2,Thủ Thuật Hacking,53,Thuyết Minh,5,tienhiep,5,Tiên Hiệp,123,Tiểu Thuyết,100,TIL,8,Tin Tức,49,Tình Cảm - Tâm Lý,16,Tips,39,tool,1,Tool Hack,14,Tools,9,Tổng Hợp,1,Tricks,26,Trinh thám,1,Trinh Thám - Hình Sự,8,trojan original,48,Trọng sinh,11,Trộm mộ,1,Trung Quốc,9,Truyện,1,Trương Định,110,Tu Chân,2,TUTORIALS,124,TVB,3,Twitter,1,Ung_Dung,4,Upload,1,usb,1,vanhoc,11,văn học,6,vBulletin,7,video,16,Vietsub,3,Việt Nam,14,Virus,4,Võ Thuật,12,Võng Du,5,Vulnerability,19,Web Developer,15,webmau,5,WHMCS,3,WiFi,2,wiki lỗi máy tinh,1,wiki lỗi NTG,3,Windows,12,WordPress,43,Write-up,11,XSS,16,Yahoo,1,yeah1offer,1,youtube,11,
ltr
item
NhutTruong.Com - Dịch Vụ CNTT: Cơ bản về cấu trúc dữ liệu và giải thuật – Phần một: Đệ quy
Cơ bản về cấu trúc dữ liệu và giải thuật – Phần một: Đệ quy
https://1.bp.blogspot.com/-Me4uGTX0lns/WiAIeF_f1GI/AAAAAAAAAG8/Uz0P1DMLLZUqDcRPHTCk0xeGncVmw3i2wCLcBGAs/s320/1489939954ckn.png
https://1.bp.blogspot.com/-Me4uGTX0lns/WiAIeF_f1GI/AAAAAAAAAG8/Uz0P1DMLLZUqDcRPHTCk0xeGncVmw3i2wCLcBGAs/s72-c/1489939954ckn.png
NhutTruong.Com - Dịch Vụ CNTT
https://www.nhuttruong.com/2017/11/co-ban-ve-cau-truc-du-lieu-va-giai.html
https://www.nhuttruong.com/
https://www.nhuttruong.com/
https://www.nhuttruong.com/2017/11/co-ban-ve-cau-truc-du-lieu-va-giai.html
true
7607280272436897486
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow Đây là nội dung quý hiếm để tránh google quét chết link Vui lòng đăng nhập Facebook hoặt Tweet để like và share để hiện link Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy