Xem mẫu

  1. L p trình ơn th Main Program(Also a module) Chương 3 Data Hàm (Function) Module1 Module2 + + Data Data1 Data Data2 Procedure1 Procedure2 Procedure3 M i module có d li u riêng c l p v i module khác L p trình ơn th (tt) L p trình ơn th (tt) “Chia tr ”: phân rã bài toán thành các bài Bài toán ban u toán con cho n khi “bài toán con” nh n ư c “ nh ”. M i “bài toán con” ư c gi i quy t b ng m t phân tích thi t k module, c l p v i các module khác. module1 module2 ... modulek Trong C m i module chính là 1 hàm. Phân tích: top down. Thi t k : bottom up. module11 module12 ... Ưu i m c a phương pháp l p trình ơn th ?
  2. Cú pháp c a hàm Cú pháp c a hàm (tt) Ví d 1: void chao() { f_name(parameters) printf(“\nxin chao”); { } /* các khai báo c c b */ Ví d 2: /* các câu l nh */ int tong(int n) [return ;] /* có th có ho c không*/ { } int i,t=0; for(i=1;iy)x=x%y; kq1=tong(12); kq2=tong(kq1); else y=y%x; kq3=ucln(kq1,15); return (x+y); }
  3. Các bư c th c hi n l i g i hàm Các bư c th c hi n l i g i hàm (tt) Gi s int a, b, kq; là các bi n toàn c c và a=6; b=8; Stack Segment Xét l i g i hàm: kq = ucln(a,b); (*) x y Khi ó các bư c sau ây ư c th c hi n: B1: Lưu a ch c a câu l nh k ti p sau l i g i 6 8 hàm (*) làm a ch quay v sau khi k t thúc Data Segment hàm. a b kq B2: C p phát vùng nh cho các tham s và các (bư c 2) bi n c c b . Các bư c th c hi n l i g i hàm (tt) Các bư c th c hi n l i g i hàm (tt) B3: Sao chép giá tr c a tham s th c B4: Th c hi n các câu l nh trong thân cho tham s hình th c hàm. 6 8 0 2 x y x y 6 8 6 8 a b kq a b kq
  4. Các bư c th c hi n l i g i hàm (tt) Các bư c th c hi n l i g i hàm (tt) B5: Tr l i k t qu b i l nh return. B6: Gi i phóng các vùng nh ã c p phát B2, l y a ch ã 0 2 lưu B1 th c hi n x y ti p chương trình. 6 8 2 6 8 2 a b kq a b kq Con tr (pointer) và cơ ch truy n Cơ ch truy n tham tr a ch Giá tr c a tham s th c ư c sao chép nh nghĩa: con tr là bi n dùng ch a cho tham s hình th c. a ch c a bi n khác. Tham s th c luôn luôn ư c b o toàn. Khai báo: *; Như ví d trên giá tr c a a và b sau Ví d : int *p; khi th c hi n (*) v n không thay i (trong khi x và y ã thay i). Khai báo con tr ki u nguyên int
  5. Cách s d ng con tr Cách s d ng con tr (tt) Dùng tên con tr , gi ng như m t bi n bình thư ng. Dùng d ng khai báo *, cho k t qu là d li u mà con tr ang “tr ” t i. 13 x=*p Có th dùng các phép toán i v i con tr (ph n sau) Ví d : int x=13, *p; p=&x; //p tr t i x. &x p printf(“\n%d duoc luu tai dia chi %p”,x,p); printf(“\np dang tro toi du lieu la %d”,*p); Truy n a ch Truy n a ch Trong nh ng trư ng h p c n làm cho Ví d : tham s th c b thay i thì phương void hoan_vi(int *x, int *y) pháp truy n tham tr không áp ng { ư c. V y c n có m t phương pháp int t=*x; khác, ó là: *x=*y; *y=t; Tham s hình th c nh n a ch c a } tham s th c (nên tham s hình th c Gi s int a,b là các bi n toàn c c và a=5; b=7; ph i là m t con tr ). Xét l i g i hàm: hoan_vi(&a,&b); khi ó:
  6. Truy n a ch (tt) Hàm quy i tư ng quy: là i tư ng ư c xây d ng thông qua chính nó. ( i tư ng có &a &b 6 th là: bài toán, hàm, ki u d li u...) x y t x y t Ví d : xét bài toán P(n) = 1+2+...+n. Bài toán này có l i gi i ( quy như sau): 6 8 8 6  p ( 0) = 0 a b a b   p(n) = p(n − 1) + n (n > 0) Hàm quy (tt) Hàm quy (tt) Hàm quy là hàm mà trong thân c a Ví d 2: tính F(n) bi t nó ch a l i g i n chính nó.  f (1) = f (2) = 1  Ví d 1: hàm tính p(n) Ph n neo  f (n) = f (n − 1) + f (n − 2) v i n>2 int p(int n) int F(int n) { { if(n==0)return 0; if(n==1||n==2) return 1; Ph n quy else return p(n-1)+n; else return F(n-1)+F(n-2); } }
  7. Phân tích hàm quy H i áp Xét l i g i hàm t=F(4); t=F(4) S hàm ư c g i + chính là s nút trên F(3) F(2) cây. || F(2) 1 Do ó v i kích thư c F(1) + tham s l n hàm || || 1 1 quy tiêu t n nhi u th i gian và b nh .