Tin học đại cương - bài 11: đệ quy tập tin

Chia sẻ: Lê Trinh | Ngày: | Loại File: PPT | Số trang:27

Thêm vào BST

Báo xấu

79
lượt xem 4
download

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

Trong bất cứ hàm đệ qui nào cũng phải có điều kiện dừng, điều kiện này sẽ kết thúc quá trình đệ qui bằng một đoạn mã chương trình được viết theo lối thông thường. Tập tin là một loại dữ liệu có thể ghi lên đĩa để dùng nhiều lần. Có 2 loại tập tin: Tập tin văn bản (text file, ASCII file): *.PAS, *.C, … (các tập tin mã nguồn chương trình). Mỗi tập tin văn bản gồm nhiều dòng. Mã ngăn cách dòng (chuyển dòng khác) là mã 10 ($OA), được tách ra thành mã 13 ($OD) và mã 10...

Chủ đề:

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

Lưu

Nội dung Text: Tin học đại cương - bài 11: đệ quy tập tin

www.uit.edu.vn TIN HỌC ĐẠI CƯƠNG BÀI 11 ĐỆ QUY TẬP TIN 1
NỘI DUNG 11 ĐỆ QUY Tin học đại cương 2
NỘI DUNG BÀI ĐỆ QUY  Khái niệm  Phân loại các hàm đệ qui:  Đệ qui tuyến tính  Đệ qui nhị phân  Đệ qui hỗ tương  Đệ qui phi tuyến Tin học đại cương 3
ĐIỀU KIỆN DỪNG  Trong bất cứ hàm đệ qui nào cũng phải có điều kiện dừng, điều kiện này sẽ kết thúc quá trình đệ qui bằng một đoạn mã chương trình được viết theo lối thông thường. Ví dụ: if (N==1) return 1; Tin học đại cương 4
SO SÁNH ĐỆ QUY VÀ LẶP Đệ qui Lặp Sử dụng cấu trúc lựa chọn Sử dụng cấu trúc lặp Sử dụng liên tục các lời gọi hàm Sử dụng vòng lặp tường minh Kết thúc khi đến trường hợp cơ sở Kết thúc khi điều kiện để tiếp tục vòng lặp sai Làm cho các lời gọi hàm đơn giản dần cho Thay đổi biến đếm trong vòng đến khi tới trường hợp cơ sở lặp cho đến khi nó làm cho điều kiện lặp sai Không thoát ra được khi các bước đệ qui Lặp sẽ không thoát ra được không làm cho bài toán đơn giản hơn và khi điều kiện lặp không bao cuối cùng hội tụ về trường hợp cơ sở giờ sai Đệ qui tồi hơn, nó liên tục đưa ra các lời gọi Phương pháp lặp được hàm làm tốn thời gian xử lý và không gian chuộng hơn nhớ. Mỗi lần gọi hàm, lại cần thêm một bản sao của hàm, tốn thêm bộ nhớ (lưu các biến của hàm, địa chỉ trở về của hàm ...). Tin học đại cương Tuy nhiên, có nhiều bài toán có thể giải bằng đệ qui lại tốt hơn (các bài toán cổ điển: tháp Hà Nội, mã đi tuần, 8 hậu, sắp xếp QuickSort…) 5
PHÂN LOẠI CÁC DẠNG ĐỆ QUY  Đệ qui tuyến tính  Đệ qui nhị phân  Đệ qui hỗ tương  Đệ qui phi tuyến Tin học đại cương 6
ĐỆ QUY TUYẾN TÍNH  Một hàm được gọi là đệ qui tuyến tính khi nó có dạng: < tên hàm> { if < điều kiện dừng > { /*Trả về giá trị hay kết thúc công việc...*/ } else { /*Làm một số công việc...*/ /*Gọi đệ qui đến hàm */ Tin học đại cương } } 7
VÍ DỤ VỀ ĐỆ QUY TUYẾN TÍNH  Viết hàm đệ qui tính xn, n nguyên dương.  Điều kiện dừng: nếu n=0 thì x0=1.  Tổng quát: xn=xn-1*x. float xn(float x, int n) { if (n==0) return 1; else return xn(x,n-1)*x; Tin học đại cương } 8
ĐỆ QUY NHỊ PHÂN  Một hàm được gọi là đệ qui nhị phân khi nó có dạng: < tênhàm> { if < điều kiện dừng > /*Trả về gtrị hay kthúc công việc...*/ else { /*Làm một số công việc ...*/ /*Gọi đqui đến để giải quyết vấn đề nhỏ hơn */ /*Gọi đqui đến để Tin học đại cương giải quyết vấn đề còn lại */ } } 9
VÍ DỤ VỀ ĐỆ QUY NHỊ PHÂN  Viết hàm đệ qui tính số hạng thứ n của dãy fibo. F0=F1=1 Fn=Fn-1+Fn-2  Điều kiện dừng: nếu n=0 hay n=1 thì Fn=1. long fibo(int n) { if ((n==0)||(n==1)) return 1; else Tin học đại cương return (fibo(n-1)+fibo(n-2)); } 10
ĐỆ QUY PHI TUYẾN  Một hàm được gọi là đệ qui phi tuyến khi nó có dạng: { if (điềukiệndừngđúng) return ; else { for… ; return ; Tin học đại cương } } 11
VÍ DỤ VỀ ĐỆ QUY PHI TUYẾN  Tính: x(0)=1 với n=0; x(n)=n2x(0)+(n-1)2x(1)+…+12x(n-1) với n>0;  Xây dựng: int x(int n) { if (n==0) return 1; else { int t=0; for (int i=0; i
ĐỆ QUY HỖ TƯƠNG  Hai hàm được gọi là đệ qui hỗ tương khi chúng có dạng: () { ... Gọi hàm ... } () { ... Tin học đại cương Gọi hàm ... } 13
VÍ DỤ VỀ ĐỆ QUY HỖ TƯƠNG  Xét hai dãy {Xn}, {Yn} được định nghĩa nh ư sau:  Xo=Yo=1  Xn = Xn-1 + Yn-1  Yn = n2Xn-1+ Yn-1  Viết hai hàm đệ qui tính số hạng thứ N của hai dãy trên Tin học đại cương 14
VÍ DỤ VỀ ĐỆ QUY HỖ TƯƠNG /* Prototype */ unsigned long TinhY(int n); unsigned long TinhX(int n); /* Implementation */ unsigned long TinhY(int n) { if (n==0) return 1; return TinhX(n-1) + TinhY(n-1); } unsigned long TinhY(int n) { Tin học đại cương if (n==0) return 1; return n*n*TinhX(n-1) + TinhY(n-1); } 15
NỘI DUNG 12 TẬP TIN Tin học đại cương 16
NỘI DUNG BÀI TẬP TIN  Khái niệm  Các thao tác trên Tập Tin  Các hàm Nhập Xuất  Các hàm di chuyển Con Trỏ tập tin  Các hàm quản lý Thư Mục Tin học đại cương 17
KHÁI NIỆM TẬP TIN  Tập tin là một loại dữ liệu có thể ghi lên đĩa để dùng nhiều lần.  Có 2 loại tập tin:  Tập tin văn bản (text file, ASCII file): *.PAS, *.C, … (các tập tin mã nguồn chương trình). Mỗi tập tin văn bản gồm nhiều dòng. Mã ngăn cách dòng (chuyển dòng khác) là mã 10 ($OA), được tách ra thành mã 13 ($OD) và mã 10 ($OA). Mã kết thúc tập tin là mã 26 ($O1A). Các ký tự trên mỗi dòng đều phải có mã ASCII từ khoảng trắng (#32 hay $O20) trở lên, nếu nhỏ hơn $O20 thì phải là các ký tự điều khiển hợp lệ.  Tập tin nhị phân (binary file): *.COM, *.EXE, *.DOC, *.XLS, *BMP, *PCX, *.GIF,… Tin học đại cương  Dữ liệu ghi lên tập tin không bị thay đổi và khi ta đóng tập tin thì mã kết thúc tập tin sẽ được ghi lên đĩa là -1. 18
CÁC THAO TÁC TRÊN FILE  Việc sử dụng file được thực hiện qua 3 bước cơ bản:  Mở file (fopen)  Đọc hay ghi thông tin lên file (fread, fscanf, fwrite, fprintf)  Đóng file (fclose)  Có các hàm làm việc với tập tin thông qua con trỏ tập tin FILE *pf; Con trỏ này được xác định khi ta mở tập tin.  Mỗi biến file đại diện trong RAM luôn có một con trỏ file. Lúc đầu, con trỏ file trỏ vào phần tử đầu tiên, sau mỗi lần đọc hay ghi dữ liệu vào biến file con trỏ tự động trỏ tới mẫu tin kế tiếp.  Chỉ thao tác được trên file khi file đang được mở. Tin học đại cương  Sau khi thao tác xong, phải đóng file. 19
CÁC CHẾ ĐỘ LÀM VIỆC TRÊN FILE r Mở tập tin để đọc w Mở tập tin để ghi a Mở để ghi thêm thông tin vào đó. Vị trí đầu tiên để truy xuất tập tin là cuối tập tin vừa mở. r+ Mở một tập tin ở cả hai chế độ ghi đọc. Vị trí đầu tiên để truy xuất tập tin là đầu tập tin vừa mở. w+ Mở một tập tin ở cả hai chế độ ghi đọc. a+ Tập tin được mở để ghi và đọc. Vị trí đầu tiên để truy xuất tập tin là cuối tập tin vừa mở. Tin học đại cương t Mở tập tập tin kiểu văn bản. b Mở tập tập tin kiểu nhị phân (binary data) 20