Luận văn Thạc sĩ Khoa học: Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng

Chia sẻ: Na Na | Ngày: | Loại File: DOC | Số trang:76

Thêm vào BST

Báo xấu

194
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Để đánh giá một thuật toán là tốt có rất nhiều tiêu chí trong đó không thể bỏ qua tính đúng của thuật toán. Và đây cũng là nội dung chính của luận văn này theo đề tài nghiên cứu: “Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng”. Luận văn nhằm tìm hiểu, nghiên cứu, tổng hợp phương pháp chứng minh tính đúng của thuật toán.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Bế Thị Hương MỘT SỐ PHƯƠNG PHÁP CHỨNG MINH TÍNH ĐÚNG CỦA THUẬT TOÁN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC 1
Hà Nội – Năm 2015 2
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Bế Thị Hương MỘT SỐ PHƯƠNG PHÁP CHỨNG MINH TÍNH ĐÚNG CỦA THUẬT TOÁN VÀ ỨNG DỤNG Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 60460110 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN THỊ HỒNG MINH
Hà Nội – Năm 2015 4
LỜI CẢM ƠN Lời đầu tiên em xin chân thành cảm ơn các thầy giáo, cô giáo giảng dạy lớp cao học Cơ sở Toán học cho Tin học, Khoa Toán – Cơ – Tin học, Trường Đại học Khoa học Tự nhiên – ĐHQGHN khóa 2012 – 2014. Các thầy cô đã rất nhiệt tình, tâm huyết trong giảng dạy cho em học tập, nghiên cứu bổ sung được thêm nhiều kiến thức mới quan trọng, hữu ích trong nghiên cứu và trong công tác giảng dạy ở trường THPT chuyên. Đồng thời kịp nhận ra và sửa đổi, bổ sung những kiến thức mình còn hiểu chưa thật chính xác giúp tăng cường năng lực và phát triển tư duy trong nghiên cứu khoa học. Đặc biệt, em gửi lời cảm ơn chân thành và sâu sắc tới cô giáo TS.Nguyễn Thị Hồng Minh (Khoa Sau Đại học – ĐHQGHN). Cô đã giảng dạy cùng với hướng dẫn luận văn cho em một cách rất khoa học, tận tâm, chu đáo và chi tiết để em có thể hoàn thành luận văn một cách tốt nhất. Cảm ơn gia đình đã cho em một chỗ dựa vững chắc để hoàn thành khóa học cũng như hoàn thành luận văn này. Mặc dù đã có rất nhiều cố gắng trong việc nghiên cứu khoa học để hoàn thành luận văn tuy nhiên do hạn chế cá nhân về mặt thời gian nên em khó có thể tránh được những thiếu sót. Kính mong thầy cô và các bạn đóng góp ý kiến quý báu để hoàn chỉnh luận văn này hơn nữa.
MỤC LỤC MỞ ĐẦU ............................................................................................................................... 1 CHƯƠNG 1. TỔNG QUAN VỀ PHÂN TÍCH THUẬT TOÁN ......................................... 4 1.1. Một số khái niệm cơ bản ........................................................................................... 4 1.1.1. Bài toán ................................................................................................................ 4 1.1.2. Thuật toán (Algorithm) ....................................................................................... 5 1.1.3. Cấu trúc dữ liệu (Data Structure) ..................................................................... 11 1.1.4. Chương trình (Program) .................................................................................... 11 1.2. Một số phương pháp thiết kế thuật toán ................................................................ 12 1.2.1. Kỹ thuật đệ quy ................................................................................................ 12 1.2.2. Phương pháp chia để trị (Divide and Conquer) ................................................ 15 1.2.3. Phương pháp quay lui (Backtracking) ............................................................... 16 1.2.4. Phương pháp nhánh cận .................................................................................... 19 1.2.5. Phương pháp quy hoạch động (Dynamic Programming ) ................................ 21 1.2.6. Phương pháp tham lam (Greedy Method) ......................................................... 22 1.3. Phân tích thuật toán .................................................................................................. 24 1.3.1. Tính đúng đắn của thuật toán ........................................................................... 24 1.3.2. Độ phức tạp thuật toán ..................................................................................... 25 a) Độ phức tạp về mặt thời gian ............................................................................ 25 b) Độ phức tạp về mặt không gian ........................................................................ 25 CHƯƠNG 2. MỘT SỐ PHƯƠNG PHÁP CHỨNG MINH TÍNH ĐÚNG CỦA THUẬT TOÁN ................................................................................................................................... 27 2.1. Các chiến lược chứng minh tính đúng thuật toán ................................................... 27 2.2. Các phương pháp chứng minh tính đúng (Correctness proofs) ............................... 28 2.2.1. Phương pháp quy nạp (induction) ..................................................................... 29 a) Phương pháp quy nạp toán học ......................................................................... 29 b) Chứng minh tính đúng của thuật toán bằng phương pháp quy nạp .................. 29 c) Một số ví dụ ........................................................................................................ 30 2.2.2. Phương pháp bất biến vòng lặp (loop invariant) ................................................. 35 a) Chứng minh tính đúng của thuật toán bằng phương pháp bất biến vòng lặp 36 ..... b) Các đặc trưng của bất biến vòng lặp ................................................................... 38
c) Một số ví dụ ............................................................................................................ 38 CHƯƠNG 3. ỨNG DỤNG CHỨNG MINH TÍNH ĐÚNG CỦA MỘT SỐ THUẬT TOÁN ................................................................................................................................... 48 3.1. Bài toán: Dãy con đơn điệu tăng dài nhất ........................................................... 48 3.2. Bài toán: Chia kẹo ................................................................................................ 57 3.3. Bài toán Cây bao trùm nhỏ nhất (Minimum spanning tree). ............................... 59 KẾT LUẬN .......................................................................................................................... 66 TÀI LIỆU THAM KHẢO .................................................................................................... 68 7
MỞ ĐẦU Thế kỷ XXI là thế kỷ của tri thức hiện đại, một nền tri thức không thể không kể đến công cụ hỗ trợ đắc lực của máy tính điện tử trong mọi lĩnh vực cuộc sống. Mặc dù công nghệ chế tạo ngày càng phát triển và phát triển với tốc độ nhanh nhưng để sử dụng máy tính điện tử một cách hiệu quả cao thì thuật toán (Algorithm) là thành phần luôn luôn quan trọng và không thể thiếu được kể từ khi máy tính điện tử ra đời. Theo lịch sử toán học nguồn gốc của từ thuật toán “Algorithm” là bắt nguồn từ “Algorism” tên của một nhà bác học nổi tiếng người Arập là Abu Jafar Mohammed ibn Musâ al Khowârizmi. (Phiên âm của từ al Khowârizmi chính là Algorism). Ông là người đã viết hai quyển sách nổi tiếng là “Sơ lược về các phép tính” và “Về hệ đếm ấn độ” vào khoảng năm 850. Đây là những quyển sách giáo khoa nổi tiếng về toán học. Lịch sử đã ghi nhận người được coi là nhà lập trình đầu tiên trên thế giới là nữ bá tước Ada Lovelace (10/12/1815 27/11/1852), tên khai sinh là Augusta Ada Byron. Các nhà khoa học về sau cho rằng thuật toán (viết năm 1842) của Ada Lovelace là những thuật toán máy tính đầu tiên do con người lập ra, vì nó lần đầu tiên thể hiện rõ từng bước phát triển logic, đặc trưng hoạt động xác định dành riêng cho máy tính. Với lịch sử lâu đời của thuật toán đã được nghiên cứu và phát triển cho tới tận ngày nay và sẽ vẫn còn tiếp tục được nghiên cứu và phát triển hơn nữa. Khi lập trình câu hỏi luôn luôn được đặt ra là thuật toán được thiết kế hoặc thuật toán được sử dụng có đúng hay không? Điều này đảm bảo cho một chương trình máy tính thực hiện có cho kết quả đúng hay không? (Chưa 1
kể đến các kỹ năng của người lập trình). Vì vậy việc xây dựng một thuật toán tốt để giải bài toán đã cho là bước quan trọng có thể nói là quan trọng nhất trong việc giải một bài toán trên máy tính điện tử. Để đánh giá một thuật toán là tốt có rất nhiều tiêu chí trong đó không thể bỏ qua tính đúng của thuật toán. Và đây cũng là nội dung chính của luận văn này theo đề tài nghiên cứu: “Một số phương pháp chứng minh tính đúng của thuật toán và ứng dụng”. Luận văn nhằm tìm hiểu, nghiên cứu, tổng hợp phương pháp chứng minh tính đúng của thuật toán. Cấu trúc luận văn gồm 3 chương, nội dung chính như sau: Chương 1. Tổng quan về phân tích thuật toán. Chương này nhằm tổng hợp lại một số kiến thức chung về bài toán, thuật toán, cấu trúc dữ liệu, chương trình và kiến thức về phân tích thuật toán. Gồm các định nghĩa, khái niệm và các ví dụ để minh họa. Trong chương này còn tổng hợp lại một số phương pháp thiết kế thuật toán thường sử dụng trong thực tế. Như kỹ thuật đệ quy, phương pháp chia để trị, phương pháp quay lui, phương pháp nhánh cận, phương pháp quy hoạch động và phương pháp tham lam. Chương 2. Một số phương pháp chứng minh tính đúng của thuật toán. Nội dung chương này gồm các chiến lược chứng minh tính đúng của thuật toán; các phương pháp cụ thể để chứng minh tính đúng của thuật toán như phương pháp quy nạp và phương pháp bất biến vòng lặp. Đây cũng chính là điểm mới của luận văn. Trong đó, phương pháp quy nạp chứng minh cho các thuật toán đệ quy, phương pháp bất biến vòng lặp chứng minh cho các thuật toán không đệ quy. Đối với mỗi phương pháp trình bày về đặc điểm, phương pháp chung đồng 2
thời nêu một số ví dụ về thuật toán và chứng minh tính đúng của các thuật toán đó. Đối với những thuật toán phức tạp có chứa cả đệ quy và lặp thì cần kết hợp khéo léo cả hai phương pháp chứng minh tính đúng của thuật toán là quy nạp và bất biến vòng lặp. Chương 3. Ứng dụng chứng minh tính đúng của một số thuật toán. Nghiên cứu một số bài toán có sử dụng các thuật toán kinh điển, thường sử dụng và vận dụng lý thuyết của chương 2 để chứng minh tính đúng của các thuật toán đó. Như bài toán dãy con đơn điệu tăng dài nhất; Chia kẹo; Cây bao trùm nhỏ nhất. 3
CHƯƠNG 1. TỔNG QUAN VỀ PHÂN TÍCH THUẬT TOÁN Để khẳng định được một thuật toán là tốt là một điều không dễ dàng gì. Thật vậy, để đánh giá một thuật toán tốt ta cần rất nhiều kỹ thuật từ thiết kế, phân tích đến đánh giá một thuật toán. Ở chương này đề cập tổng quát đến các vấn đề trong phân tích thuật toán và một số thuật toán cơ bản thường dùng trong khoa học tính toán hiện đại. 1.1. Một số khái niệm cơ bản 1.1.1. Bài toán Khoa học máy tính ngày nay giải quyết rất nhiều vấn đề trong thực tế trong nhiều lĩnh vự khác nhau, những vấn đề đó ta thường gọi là bài toán. Tuy nhiên bài toán ở đây không phải là một trường hợp cụ thể mà là bài toán mang tính tổng quát bao gồm hầu như tất cả các khả năng có thể của thế giới thực trong vấn đề cần giải quyết. Như vậy, nói một cách dễ hiểu thì bài toán là việc nào đó ta muốn máy tính thực hiện. Có thể là một yêu cầu đơn giản như in ra một dòng chữ trên màn hình, giải phương trình bậc hai, giải hệ phương trình bậc nhất hai ẩn hoặc kiểm tra một s ố là chẵn hay lẻ,... Nhưng cũng có thể là giải quyết những vấn đề rất phức tạp như tìm đường đi trong mê cung, tìm đường đi ngắn nhất, tìm cây bao trùm,... Điểm quan trọng đầu tiên khi giải một bài toán trên máy tính đó là cần xác định rõ những gì đã biết input (dữ liệu vào) và kết quả cần thu được output (dữ liệu ra) và phân tích mối quan hệ giữa hai yếu tố đó. Sau đây là một số ví dụ về bài toán: Bài toán 1.1: Kiểm tra tính nguyên tố của một số nguyên dương cho trước. Input: Số nguyên dương N. 4
Output: Xác định N là số nguyên tố hoặc N không là số nguyên tố. Bài toán 1.2: Giải phương trình bậc hai ax2+bx+c=0 (a≠0). Input: Các số thực a, b, c (a≠0). Output: Các nghiệm x thỏa mãn phương trình đã cho hoặc thông báo không có nghiệm. Bài toán 1.3: Tìm ước số chung lớn nhất của hai số nguyên dương a, b. Input: Hai số nguyên dương a, b. Output: Ước số chung lớn nhất của a và b. Bài toán 1.4: Xác định vị trí của phần tử có giá trị bằng số nguyên x trong một dãy số nguyên a1, a2,..., an. Input: Số n; dãy số nguyên a1, a2, ..., an và số nguyên x. Output: Chỉ số i nếu x=ai và là 0 nếu x không có mặt trong dãy. Bài toán 1.5. Cho đồ thị vô hướng G=(V, E). Tìm đường đi ngắn nhất từ đỉnh u tới đỉnh v của đồ thị G. Input: Đồ thị vô hướng G=(V, E) và hai đỉnh u,v. Output: Xác định đường đi có độ dài ngắn nhất d=(u=v1,v2,...,vn=v) (với đỉnh vi thuộc V, cung (vi, vi+1) thuộc E). Bài toán 1.6. Sắp xếp một dãy các số cho trước thành dãy không giảm. Input: Số n và dãy gồm n số . Output: Một hoán vị
thể là một thiết kế mới hoặc lựa chọn một thuật toán đã có. Thuật toán là để biểu diễn về cách giải một bài toán trên máy tính. Một bài toán có thể có nhiều cách giải nhưng một thuật toán chỉ giải một bài toán mà thôi. Đến hiện nay thì đã có nhiều định nghĩa về thuật toán và sau đây là một lựa chọn định nghĩa thuật toán: Định nghĩa: Thuật toán (Algorithm) để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định, sao cho sau khi thực hiện dãy thao tác ấy, từ dữ liệu vào có thể là một giá trị hoặc một tập giá trị (input) của bài toán ta nhận được một giá trị hoặc một tập giá trị còn gọi là dữ liệu ra (output) của bài toán đó. Để thuật toán được rõ ràng, chính xác, dễ hiểu, dễ đọc hơn người ta đưa ra các phương pháp biểu diễn thuật toán. Gồm có ba phương pháp biểu diễn thuật toán như sau: Ngôn ngữ tự nhiên (Natural languages): Dùng ngôn ngữ tự nhiên để liệt kê từng bước của thuật toán. Phương pháp này không có các quy tắc chung do đó người viết và người đọc dễ dàng thực hiện được mà không cần phải nắm được những quy tắc. Nhưng viết thuật toán theo cách này thường dài dòng, không thể hiện được rõ cấu trúc thuật toán và đôi lúc có thể gây khó hiểu hoặc hiểu nhầm đối với người đọc. Sơ đồ khối (Flowcharts): là công cụ trực quan để thể hiện thuật toán. Sơ đồ khối biểu diễn được sự phân cấp của thuật toán cũng như trình tự thực hiện thuật toán. Đặc biệt phù hợp với những thuật toán phức tạp, khó theo dõi quá trình xử lý. Tuy nhiên, phương pháp biểu diễn này có nhược điểm là cồng kềnh, cần không gian biểu diễn lớn hơn các phương pháp khác. Trong sơ đồ khối thường sử dụng một số khối và cung để biểu diễn thuật toán như sau: 6
Hình oval: Thể hiện thao tác nhập, xuất dữ liệu; Hình thoi: Thể hiện thao tác so sánh, chỉ có hai nhánh logic là đúng hoặc sai; Hình chữ nhật: Thể hiện các phép gán, các thao tác tính toán; Cung có hướng: Thể hiện trình tự thực hiện các thao tác, thao tác này nối tiếp thao tác kia theo hướng mũi tên. Nút nối: Để nối các phần khác nhau của sơ đồ khối lại với nhau. Thường biểu diễn bằng hình tròn, bên trong có kí hiệu để biết là nút nối nào. Nút nối trang: Với các sơ đồ khối lớn cần biểu diễn trên nhiều trang thì biểu diễn thêm bằng nút nối trang. Giả mã (Pseudocode): Sử dụng cú pháp của một ngôn ngữ lập trình nào đó kết hợp với ngôn ngữ tự nhiên để thể hiện thuật toán. Với giả mã người lập trình tận dụng được các định nghĩa và cấu trúc của ngôn ngữ lập trình. Đây cũng là phương pháp chính được chọn lựa để biểu diễn các thuật toán trong luận văn này. Sau đây là ví dụ về thuật toán và ba cách để biểu diễn thuật toán tương ứng của bài toán 1 đã nêu ở mục 1.1.1 Phân tích bài toán: Theo định nghĩa số nguyên tố thì số nguyên dương N là số nguyên tố nếu N chỉ có đúng 2 ước số là 1 và chính nó. Nên ta có với N là số nguyên dương thì: Nếu N=1 thì N không là số nguyên tố; Nếu 1
Nếu N 4 thì N là số nguyên tố nếu N không có ước số từ 2 đến phần nguyên căn bậc 2 của N, kí hiệu: � � � N �. Do đó ta có thuật toán như sau: Thuật toán biểu diễn bằng ngôn ngữ tự nhiên: Bước 1. Nhập số nguyên dương N; Bước 2. Nếu N=1 thì thông báo N không nguyên tố rồi kết thúc; Bước 3. Nếu N [ N ] thì thông báo N là nguyên tố rồi kết thúc; Bước 6. Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc; Bước 7. i = i+1 rồi quay lại bước 5. Thuật toán biểu diễn bằng sơ đồ khối: 8
Nhập N nguyên dương Đúng N = 1 ? Sai N � �? Thông báo N N Đúng là số nguyên tố � � Sai và kết thúc. Sai i = i + 1 N chia hết cho i ? Đúng Thông báo N không là số nguyên tố rồi kết thúc. Thuật toán biểu diễn bằng giả mã: Ngto(N):int //Hàm kiểm tra số N có phải nguyên tố hay không if (N=1) return 0; else 9
if (N
Tính đúng đắn (Generalliness): Sau khi thuật toán kết thúc ta phải nhận được output cần tìm. Tính đúng là tính chất hiển nhiên khi giải một bài toán muốn đạt được nhất nhưng cũng là tính chất khó đạt tới nhất. Vì không phải lúc nào cũng tìm được lời giải đúng cho bài toán đã đặt ra. 1.1.3. Cấu trúc dữ liệu (Data Structure) Cấu trúc dữ liệu là một cách lưu trữ dữ liệu trong máy tính sao cho việc khai thác chúng được hiệu quả hơn. Trong thiết kế chương trình việc lựa chọn cấu trúc dữ liệu rất quan trọng. Vì mỗi loại cấu trúc dữ liệu phù hợp với một số loại ứng dụng khác nhau. Một cấu trúc dữ liệu được thiết kế cho phép thực hiện nhiều phép toán, tiết kiệm tài nguyên, ít thời gian xử lý và sử dụng không gian bộ nhớ càng ít thì càng tốt. Các cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép toán trên cấu trúc dữ liệu đó được cung cấp bởi một ngôn ngữ lập trình cụ thể. Sự liên hệ giữa cấu trúc dữ liệu và thuật toán rất chặt chẽ, thuật toán cần được thao tác trên các cấu trúc dữ liệu nào đó và các cấu trúc dữ liệu sẽ được xử lý bởi thuật toán nào đó. Và vì không có một cấu trúc duy nhất nào có thể tốt cho mọi mục đích hay phù hợp với mọi thuật toán do đó điều quan trọng khi nghiên cứu cấu trúc dữ liệu là cần phải biết sức mạnh cũng như giới hạn của cấu trúc dữ liệu đó để sử dụng cho phù hợp, hiệu quả. 1.1.4. Chương trình (Program) Chương trình = Thuật toán + Cấu trúc dữ liệu. Chương trình là sự thể hiện bằng một ngôn ngữ lập trình cụ thể một thuật toán đã cho được thể hiện trên một cấu trúc dữ liệu xác định. Việc lựa chọn cấu trúc dữ liệu phù hợp với thuật toán hoặc ngược lại lựa chọn thuật toán phù hợp với cấu trúc dữ liệu cụ thể còn phụ thuộc vào mục đích của chương trình, kỹ năng người lập trình và khả năng của ngôn ngữ lập trình cụ thể. 11
1.2. Một số phương pháp thiết kế thuật toán Ngày nay có nhiều phương pháp thiết kế thuật toán đã được nghiên cứu và sử dụng trong công nghệ phần mềm. Có những bài toán có thể giải được bằng thuật toán nhưng cũng những bài toán chưa có thuật toán hoặc chỉ có thuật toán cho lời giải tương đối chấp nhận được. Trong luận văn này nghiên cứu về các phương pháp thiết kế thuật toán và ứng dụng cho các bài toán có thuật toán để giải. 1.2.1. Kỹ thuật đệ quy Đệ quy là một khái niệm cơ bản trong toán học và tin học. Ta nói một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng cùng dạng với chính nó bằng quy nạp. Ý tưởng của kỹ thuật đệ quy đó là chia bài toán cần giải quyết thành nhiều bài toán nhỏ hơn, việc chia này thực hiện cho đến khi bài toán con có lời giải và lời giải này thường là tường minh và tương đối đơn giản. Ví dụ: Kí hiệu |S| là số các phần tử của tập hữu hạn S. Nếu S= thì |S|=0 Ngược lại S≠ thì tất có một phần tử x S khi đó |S|=|S\{x}|+1. Khái niệm giải thuật đệ quy: Một bài toán T được thực hiện bằng giải thuật của một bài toán T’ có dạng giống như T thì giải thuật đó gọi là giải thuật đệ quy. Bài toán T’ tuy có dạng giống bài toán T nhưng T’ theo một nghĩa nào đó phải là bài toán nhỏ hơn T. Bài toán T’ phải dễ giải hơn bài toán T và việc giải bài toán T’ không cần dùng đến T. Do đó phương pháp chung sử dụng kỹ thuật đệ quy để giải một bài toán là ta chia bài toán đó thành các bài toán con đơn giản hơn cùng loại. 12
Phương pháp này còn được gọi là kỹ thu ật lập trình chia để trị. Chính nó là chìa khóa để thiết kế nhiều giải thuật quan trọng, là cơ sở của phương pháp quy hoạch động. Sau đây là một số ví dụ về bài toán mang bản chất đệ quy: Ví dụ 1: Bài toán tính n giai thừa. Cho n là một số tự nhiên (n 0). Hãy tính giai thừa của n. Biết rằng 0! =1 và n!=(n1)!n. Phân tích: Theo giả thiết, ta có : n! = (n1)!n. Như vậy : Để tính n! ta cần phải tính (n1)! Để tính (n1)! ta phải tính (n2)! ................................................... Cứ như vậy, cho tới khi gặp trường hợp 0!. Ví dụ 2: Dãy Fibonacci Dãy Fibonacci là dãy vô hạn các số tự nhiên. Số Fibonacci thứ n, ký hiệu F(n), được định nghĩa như sau: F(n) = 1, nếu n=1 hoặc n=2; F(n) = F(n1) + F(n2), nếu n 3. Yêu cầu: Tính số fibonacci thứ n với n nguyên dương cho trước. Phân tích: Với n 3 : Đế tính F(n) ta phải tính F(n1) và F(n2). Để tính F(n1) ta lại phải tính F(n2) và F(n3), và để tính F(n2) ta phải tính F(n3) và F(n4). 13