HỌC VIỆN KTQS KHOA CÔNG NGHỆ THÔNG TIN
Chương 4. Giải thuật xử lý thông tin và ngôn ngữ lập trình
Ơ Ả Ậ ầ ọ H c ph n: L P TRÌNH C B N
ệ
ả
Tài li u tham kh o
ồ ỹ
ồ ắ
ươ
ươ
Giáo trình tin h c c s , H S Đàm, Đào Ki n Qu c, ố ạ ọ ư ạ ng 7,
ế ọ ơ ở ng. Đ i h c S ph m, 2004 – Ch
H Đ c Ph 9.
2
Giải thuật xử lý thông tin và ngôn ngữ lập trình
Ộ
N I DUNG
ệ
ả
ậ
Khái ni m bài toán và gi
i thu t
ư
ủ
ặ
ầ
ả
Đ c tr ng (yêu c u) c a gi
ậ i thu t
ươ
ễ
ạ
ả
Các ph
ng pháp di n đ t gi
ậ i thu t
ơ ượ ề
ả
S l
c v đánh giá gi
ậ i thu t
ữ ậ
ứ
ủ
Ngôn ng l p trình và các m c khác nhau c a ngôn ng ữ
ậ l p trình
ự
ệ
ươ
ữ ậ
Quá trình th c hi n ch
ng trình trên ngôn ng b c cao
3
Giải thuật xử lý thông tin và ngôn ngữ lập trình
Input
Yêu cầu
Output
Ệ
KHÁI NI M BÀI TOÁN
Cho số tự nhiên n “có” hay “không”
n có phải số nguyên tố hay không
Cho hồ sơ điểm sinh viên Danh sách sv thoả mãn
Tìm tất cả các sinh viên có điểm trung bình trên 8
Độ bền
Tính sức bền
Cho một bài toán nghĩa là cho input, và yêu cầu để tìm (tính) ra output
4
Giải thuật xử lý thông tin và ngôn ngữ lập trình
Thiết kế hình học, tải trọng
Ậ
Ệ
KHÁI NI M THU T TOÁN
Thu t toán (algorithm) là m t quá trình g m m t dãy h u h n các
ữ ạ ậ ộ ồ ộ
ể ự ệ ượ ắ ế ộ ự ị thao tác có th th c hi n đ c s p x p theo m t trình t xác đ nh
ể ả ộ dùng đ gi i m t bài toán
Ví d : thu t toán Euclid tìm
ụ ậ ướ ố ấ ủ ớ c s chung l n nh t c a hai s t ố ự
ủ ả ấ ị ỉ nhiên. Thay vì ph i tính toán theo đ nh nghĩa ch làm rõ c u trúc c a
ủ ướ ố ớ ố ấ ậ ỏ USCLN (tích c a các c s chung v i s mũ nh nh t) thu t toán
USCLN(a,b) = USCLN (b,a))
Nếu a> b, USCLN(a,b) = USCLN (a-b,b)
USCLN(a,a)= a
5
Giải thuật xử lý thông tin và ngôn ngữ lập trình
ự ấ Euclid d a trên các tính ch t sau:
Ậ
Ố Ự Ủ THU T TOÁN EUCLID TIM USCLN C A HAI S T NHIÊN
1.
ố Bài toán: Cho hai s m, n tìm d = USCLN(m,n)
ề ướ ướ ể ế ự ế ệ B c 1: Ki m tra n u m= n thì v b c 5, n u không th c hi n
2.
ế ướ ti p b c 2
ề ướ ướ ế ế ướ ự ế ệ B c 2: N u m> n thì v b c 4 n u không th c hi n ti p b c
3.
3
4.
ộ ượ ướ ớ ề ướ ằ B c 3: m 5. ộ ượ ướ ề ướ ằ ớ
B c 4: b t m đi m t l ng b ng n và quay v b c 1 6 Giải thuật xử lý thông tin và ngôn ngữ lập trình ướ ủ ế ấ ị
B c 5: L y d chính là giá tr chung c a m và n. K t thúc Ụ ƯỚ Ủ Ậ VÍ D CÁC B C C A THU T TOÁN EUCLID 7 Giải thuật xử lý thông tin và ngôn ngữ lập trình Input Output Tính xác đ nh: Sau m i b
ị ỗ ướ ướ ế ị c, b c ti p theo hoàn toàn xác đ nh. Tính kh thi: các ch d n đ t ra đ u có th th c hi n đ
ặ ể ự ệ ượ ỉ ẫ ề ả c Tính d ng: quá trình tính toán luôn ph i d ng sau m t s h u h n ộ ố ữ ả ừ ừ ạ b c.ướ Tính ph d ng: m i thu t toán không ch dùng cho m t bài toán v i d
ớ ữ ổ ụ ậ ộ ỗ ỉ ệ ụ ể ộ ớ ụ ể ể ớ
li u c th mà có th áp d ng v i m t l p các bài toán cùng ki u. ạ ẳ ườ ớ ố ự ủ ậ Ch ng h n ng i ta nói t i thu t toán tìm USCLN c a hai s t nhiên 8 Giải thuật xử lý thông tin và ngôn ngữ lập trình ủ ậ ả ấ ỳ ứ
b t k ch không ph i thu t toán tìm USCLN c a 15 và 21. ữ ự Dùng ngôn ng t nhiên ơ ồ Dùng s đ kh i
ố ả Dùng mã gi (pseudocode) 9 Giải thuật xử lý thông tin và ngôn ngữ lập trình ƯƠ Ậ Ể CÁC PH Ễ
NG PHÁP BI U DI N THU T TOÁN ữ ự Dùng ngôn ng t nhiên ố ỏ ụ ỏ ườ ơ ỗ Ví d : Bài toán b c s i: có 30 viên s i. Hai ng i ch i, m i ố ừ ế ố ố ng ườ ế ượ
i đ n l t mình b c t ỏ
1 đ n 3 viên s i. Ai b c cu i ể ườ ế ắ ướ cùng là th ng. Làm th nào đ ng i đi tr ắ
c th ng. ướ ố 1. B c 1, b c 2 viên ế ố ỏ ố ườ ướ ừ ế ơ ộ 2. B c 2: n u s s i đã h t, d ng cu c ch i, tuyên b ng i ướ ề ướ ế ắ ộ ế (đi tr c) th ng cu c. N u không v b c ti p theo ướ ố ươ ố 3. B c 3: Đ i ph ng b c k viên 0 < k<4 ườ ướ ố ộ ượ ướ
4. B c 4: Ng i đi tr c b c m t l ng là 4 k sau đó quay ề ướ
v b c 2 10 Giải thuật xử lý thông tin và ngôn ngữ lập trình Ặ Ơ Ồ Ằ Ễ Ể Ố
Ư Ồ
BI U DI N B NG L U Đ HO C S Đ KH I Khối input Khối output
Khối input Khối thao tác Khởi đầu Kết thúc Khối điều kiện đối tượng:= biểu
thức Thứ tự xử lý 11 Giải thuật xử lý thông tin và ngôn ngữ lập trình Ư Ồ Ậ Ằ Ễ Ể BI U DI N B NG L U Đ THU T TOÁN EUCLID Bắt đầu m,n -
m>n ? +
d:= m m=n? d Kết thúc 12 Giải thuật xử lý thông tin và ngôn ngữ lập trình +
m:=m-n n:= n - m Ằ Ễ Ể Ả BI U DI N B NG GI MÃ Trong khi m (cid:0) n thì lặp lại khối sau: Điều chỉnh lại giá trị
của m và n Nếu m > n thì Bớt m đi một lượng là n Cho tới khi m = n thì tuyên bố USCLN
chính là giá trị chung của m và n read(m,n);
while m <> n do
if m>n
m=m-n
else
n= n-m;
write(m); 13 Giải thuật xử lý thông tin và ngôn ngữ lập trình Nếu ngược lại thì Bớt n đi một lượng là m Ỉ Ớ Ộ Ấ Ệ Ủ TÍNH NGHI M X P X V I Đ CHÍNH XÁC
ε = 0.000001 C A PH
ƯƠ NG TRÌNH f(x)= e x x3 = 0 ự ậ ử ụ
S d ng thu t toán chia đôi d a ấ ộ ế
vào tính ch t: n u m t hàm f liên ạ ụ
t c trên đo n [a,b] có f(a) và f(b) ươ ấ ị thì ph ng trình f(x) = 0 nh t đ nh ữ ừ ệ ậ ằ ộ th a nh n m t nghi m c n m gi a [a,b] ươ ệ Ph ư
ng trình có hai nghi m nh ệ ẽ ỏ
trong hình v . Ta vây nghi m nh ạ ơ
h n trong đo n [1,4] 14 Giải thuật xử lý thông tin và ngôn ngữ lập trình Ỉ Ớ Ộ Ấ Ệ Ủ TÍNH NGHI M X P X V I Đ CHÍNH XÁC
ε = 0.000001 C A PH
ƯƠ NG TRÌNH f(x)= e x x3 = 0 Ta có f(a)>0, f(b)<0. Thuật toán chia đôi tiến hành vây nghiệm, mỗi bước vây, giảm khoảng vây đi 2 lần. c 1. Tính f(c) với c= (a+b)/2. Không xảy ra f(c) = 0. Tiếp b bước 2 2. Nếu f(c)> 0 thay a bởi c, sau đó thực hiện bước 4 3. Nếu f(c) <0 thay b bởi c. Thực hiện bước tiếp theo 4. Nếu b-a > ε, quay về 1, nếu không làm tiếp 5. Dừng, lấy c làm nghiệm 15 Giải thuật xử lý thông tin và ngôn ngữ lập trình a TÍNH NGHIỆM XẤP XỈ VỚI ĐỘ CHÍNH XÁC
ε = 0.000001 CỦA PHƯƠNG TRÌNH f(x)= ex- x3 = 0 a:= 1; b:= 4; ε = 0.00001 c:= (a+b)/2 f(c) >0 ? + c a:= c + - 16 Giải thuật xử lý thông tin và ngôn ngữ lập trình b-a < ε Ằ Ể Ễ Ả BI U DI N B NG GI MÃ Cho ε = 0.000001, a=1 b=4
Lặp lại khối sau: Tính c:= (a+b)/2
Tính f(c)
Nếu f(c) > 0 thì thực hiện khối Thay a bởi c Thay b bởi c a=1; b= 4;
epsi= 0.000001;
do
c= (a+b)/2;
if (epx(c)-sin(c) > 0)
a=c
else
b= c
while (b-a < epsi)
printf(c); Nếu ngược lại thì thực hiện
khối 17 Giải thuật xử lý thông tin và ngôn ngữ lập trình Cho tới khi b-a < ε thì lấy c làm
nghiệm xấp xỉ ể ậ ỗ ớ V i m i bài toán có th có nhi u thu t toán khác nhau. Tuy nhiên
ề ả ủ ể ấ ệ hi u qu c a chúng có th r t khác nhau. ọ ườ ộ ứ ạ ề ờ ề Trong tin h c ng ế
i ta quan tâm nhi u đ n đ ph c t p v th i ả ề ầ ấ ờ ượ gian: gi i bài toán đó c n bao nhiêu th i gian, v n đ này đ c ơ ả ầ ượ ề ố ự ệ quy v s phép tính c b n c n đ c th c hi n ộ ứ ạ ự ố Đ ph c t p không gian: s tiêu t n không gian nh .
ớ ề ệ ề ượ ấ ấ ứ ề ơ V n đ hi u qu th i gian là v n đ đ
ả ờ c nghiên c u nhi u h n c . ả 18 Giải thuật xử lý thông tin và ngôn ngữ lập trình ế ộ ở ị ác nhau a1,a2...ai... an và
ứ
v trí th ộ ố .Hãy cho bi ế ậ m t s x
bao nhiêu. Thu t toán tìm ki m tu n t ố
t x có trong dãy s đó hay không và
ầ ự ư
nh sau: ướ B c 1. Cho i = 1 ế ể ớ ướ ự ế ệ ế i b c 5, n u không th c hi n ti p ướ
B c 2. N u ai = x thì chuy n t
ướ
b c 3 ướ ế ề ướ ế
c 4. N u sai ề ướ ể
B c 3. Tăng i lên 1 và ki m tra i > n. N u đúng v b
quay v b c 2 ướ ế ố ố B c 4. Tuyên b không có s x. K t thúc ố ứ ố ố ướ ế B c 5. Tuyên b s x chính là s th i. K t thúc ố ướ ầ ử ế ệ ả ả S b c tìm trung bình là n/2. N u có 1 tri u ph n t ấ
thì ph i m t kho ng 500.000 phép so sánh 19 Giải thuật xử lý thông tin và ngôn ngữ lập trình ế ắ ứ ự ế ố ể ầ ằ ậ N u s p x p dãy s theo th t tăng d n có th tìm b ng thu t toán tìm ướ ầ ố B c 1. Cho d := 1, c:=n ữ )
(d: đ u, c: cu i, g: gi a ướ B c 2. Tính g := [(d+c)/2] ướ ế ụ ệ ướ ự ế B c 3. So x v i a ể ớ ướ
i b c 7. N u khác thì ti p t c th c hi n b c 4 ế
ớ g. N u x=a g chuy n t ệ ướ ướ ự ế ế ế ố ố
B c 4. N u d=c thì tuyên b không có s x và k t thúc. N u không thì th c hi n b c 5 ế ti p theo ướ ế ằ ề ướ ệ ướ ự ế B c 5. N u x < a c 2. N u không thì th c hi n b c 6 g thì thay c b ng a g và quay v b ế ti p theo ướ ằ ề ướ B c 6. Thay d b ng a c 2 g và quay v b ố ứ ố ố ướ ế B c 7. Tuyên b s x chính là s th g. K t thúc ứ ỗ ầ ượ ạ ố ướ ế ầ ả ộ C m i l n không tìm đ c ta l i gi m đ dài vùng tìm ki m đi hai l n. S b c tìm trung bình ầ ử ế ệ ỉ ấ ầ ự ả ầ ấ ỏ ớ thì ch m t kho ng 20 l n tìm, r t nh so v i tìm tu n t là log2n. N u có 1 tri u ph n t 20 Giải thuật xử lý thông tin và ngôn ngữ lập trình ế ị ẹ ế ầ ki m nh phân, v i t ớ ư ưở
t ng thu h p d n vùng tìm ki m ữ ể ữ ậ Ngôn ng l p trình (programming language) là ngôn ng bi u ể ề ự ễ ể ệ ậ di n thu t toán dùng đ đi u khi n máy tính th c hi n các ị ệ
công vi c đã đ nh. ắ ế ượ ọ ữ ủ Các quy t c vi c g i là cú pháp (syntax) c a ngôn ng . ý t đ ể ả ọ ữ ữ nghĩa mà ngôn ng chuy n t i g i là ng nghĩa (semantic) ươ ả ượ ể ệ ng trình máy tính (program)ph i đ c th hi n trên ể ễ ữ ậ ộ ị M t ch
ộ
ộ ư ậ
m t ngôn ng xác đ nh. Nh v y m t thu t toán có th di n ề ươ ữ ạ ằ
đ t b ng nhi u ch ữ
ng trình khác nhau trên nh ng ngôn ng khác nhau. 21 Giải thuật xử lý thông tin và ngôn ngữ lập trình Ứ Ủ Ữ Ậ CÁC M C C A NGÔN NG L P TRÌNH Ngôn ng máy: ngôn ng th hi n tr c ti p trong h l nh c a máy. Nói
ữ ở ứ ữ ữ ể ệ ự ế ệ ệ ủ ượ ọ ữ chung ngôn ng máy là ngôn ng m c các bít, nên cũng đ c g i là ngôn ữ ị ng nh phân H p ng (assembly) là lo i ngôn ng v c b n là g n v i ngôn ng nh
ữ ị ữ ề ơ ả ữ ạ ầ ớ ợ ộ ệ ỗ ệ ữ ủ ươ ứ phân, m i l nh c a ngôn ng máy có m t l nh t ữ
ủ ợ
ng ng c a h p ng ữ ử ụ ư ợ ữ nh ng h p ng s d ng mã ch Ngôn ng b c cao – còn g i là ngôn ng thu t toán (Algorithmic language)
ộ ậ ữ ậ ữ ậ ọ ớ ệ ệ ữ ể ủ ễ ậ là ngôn ng bi u di n thu t toán đ c l p v i h l nh c a máy M i ngôn ng xác đ nh m t ki u di n đ t k ch b n đi u khi n máy tính
ễ ạ ị ữ ề ể ể ả ộ ỗ ị ộ ị ể ề ả ỗ ế ữ ậ ọ ộ M i m t k ch b n đi u khi n máy vi t trên m t ngôn ng l p trình g i là 22 Giải thuật xử lý thông tin và ngôn ngữ lập trình ươ ộ
m t ch ng trình (program) ữ ượ ế ằ ệ ệ ị Chính là ngôn ng đ c vi t b ng l nh máy trong h nh phân ặ ệ
ho c h 16 Ư ể ậ ụ ượ ủ ả u đi m, t n d ng đ c kh năng c a máy, t ố ư ượ
i u đ ờ
c th i gian ch yạ ượ ể ế ữ ỗ ụ ừ ạ ộ Nh c đi m: khó vi t, khó ch a l i, ph thu c vào t ng lo i máy. Nói chung chi phí cao. Nạp 1060 lên TG AX A1 60 10 Cộng AX với 1066 -> AX 03 66 10 Ghi từ AX về 2B00 Giải thuật xử lý thông tin và ngôn ngữ lập trình A3 00 2B 1001 0001 0110 0000 0001 0000
0000 0011 0110 0110 0001 0000
23
1010 0011 0000 0000 0010 1011 Mã máy nhị phân Mã hexa Ý nghĩa V c b n, m i l nh h p ng t
ễ ử ề ơ ả ỗ ệ ữ ươ ợ ự ớ ộ ệ ư ng t v i m t l nh máy – nh ng ễ ể ữ dùng mã ch nên d hi u, d s a. Ph i d ch ra ngôn ng máy (thay mã l nh và đ a ch )
ỉ ả ị ữ ệ ị Có các l nh macro, cho phép thay th hi u qu h n
ả ơ ế ệ ệ Ư ể ễ ử ỗ ơ ễ ậ ữ u đi m: d l p trình d s a l i h n ngôn ng máy Nh Mã máy trong hệ hexa ượ ứ ạ ụ ể ẫ ộ c đi m: v n còn ph c t p và ph thu c vào máy A1 64 10 03 66 10 A3 00 2B 24 Giải thuật xử lý thông tin và ngôn ngữ lập trình ể ạ ượ ể ươ ữ ợ ộ Đ máy có th ch y đ ả ị
c thì ph i d ch ch ng trình trên h p ng thành m t ươ ộ ợ ữ ề ầ ị ch ờ ộ
ng trình trên ngôn ng máy > nh m t ph n m m có tên là b h p d ch (assembler) ộ ợ ố ượ ẽ ầ ớ ị đ u tiên b h p d ch s ph i b trí không gian nh cho các đ i t
ả ố ng, sau đó thay ỉ ằ ế ệ ố ị th mã l nh và đ a ch b ng các mã s . ế ượ ự ệ ệ ớ ươ ươ ề ớ Thay th đ ệ
c th c hi n v i các l nh macro, là các l nh t ng đ ng v i nhi u ệ
l nh. ả ủ ướ ị ế ố ượ ầ ạ ạ K t qu c a b c d ch đ u tiên là t o ra các mô đun đ i t ng, là các đo n ươ ướ ạ ể ẵ ư ư ị ỉ ch ng trình d ấ
i d ng nh phân nh ng ch a có c u trúc hoàn ch nh đ s n sàng ạ ch y ngay. ườ ộ ướ ự ề ế ố ệ
ng th c hi n m t b ể ế ợ
c khác là liên k t, đ k t h p nhi u mô đun đ i ộ ươ ớ ạ ị ỉ ươ ng thành m t ch ng trình nh phân hoàn ch nh. Sau đó m i n p ch ng trình Th
ượ
t này vào thi hành 25 Giải thuật xử lý thông tin và ngôn ngữ lập trình Ngôn ng máy và h p ng ph thu c vào máy, l ữ ụ ữ ộ ợ ạ ộ i khó dùng, vì nó bu c ườ ậ ả ế ế ế ng i l p trình ph i vi t tinh t ứ ệ
đ n m c l nh máy. Ng ườ ữ ỉ ễ ả ố ậ i ta mu n các ngôn ng ch di n t thu t toán mà thôi, không liên ụ ể ệ ệ ủ ữ ế ặ ọ quan đ n các h l nh đ c thù c a máy tính c th . Các ngôn ng này g i ữ ậ ữ ậ ọ là ngôn ng b c cao (high level language) hay còn g i là ngôn ng thu t toán (algorithmic language) Ngôn ng thu t toán có hình th c gi ng v i ngôn ng t ữ ự ứ ữ ậ ố ớ ặ
nhiên ho c ngôn ặ ợ ễ ễ ạ ơ ữ ữ ề ớ ọ ng toán h c nên d di n đ t h n nhi u so v i ngôn ng máy ho c h p 26 Giải thuật xử lý thông tin và ngôn ngữ lập trình ngữ Ví dụ giải phương trình bậc 2 trên PASCAL FORTRAN
DELTA = B*B - 4* A*C
IF DELTA < 0 GOTO 10
X1= (- B + SQRT(DELTA))/(2*A)
X2 =(- B - SQRT(DELTA))/(2*A)
WRITE (3,20) X1, X2
20 FORMAT ('NGHIEM 1= ', F8.3, NGHIEM 2 = ', F8.3) DELTA := B*B - 4*A*C;
IF DELTA >= 0 THEN
BEGIN
X1 := (- B + SQRT(DELTA))/(2*A);
X2 := (- B - SQRT(DELTA))/(2*A);
WRITE (X1,X2);
END
ELSE WRITE(‘Vô nghiệm) GOTO 30
10 WRITE(3,40)
40 FORMAT('VO NGHIEM')
30 END 27 Giải thuật xử lý thông tin và ngôn ngữ lập trình ự ế ữ ị ả ị ể ằ ỉ Máy tính ch có th thi hành tr c ti p ngôn ng nh phân, do đó ph i d ch b ng ể ự ệ ượ ể ộ m t cách nào đó đ máy tính có th th c hi n đ c. ự ệ Có hai cách th c hi n: S d ng m t ch ử ụ ộ ươ ề ầ ỏ ở ọ ị ng trình mô ph ng (ph n m m này đã mã nh phân g i ươ ị ươ ọ là ch ng trình thông d ch interpreter). Ch ng trình này đ c và thi hành các ậ ươ ự ự ữ ậ
ệ
l nh trong ngôn ng b c cao. Do v y ch ị
ng trình thông d ch th c s đóng ế ộ ả ộ ị ươ ươ vai trò m t máy o. Trong ch đ thông d ch, không sinh ch ng trình t ng ứ ị ng trong mã nh phân ươ ậ ộ ươ ở ị
D ch ch ữ
ng trình trong ngôn ng thu t toán thành m t ch ng trình ngôn d chị 28 Giải thuật xử lý thông tin và ngôn ngữ lập trình ữ ữ ả ươ ng máy b o toàn ng nghĩa nh ờ ch ng trình biên (compiler) Ự Ệ ƯƠ Ữ Ậ TH C HI N CH NG TRÌNH TRÊN NGÔN NG B C CAO ạ ả ươ ờ ộ ộ ạ ả So n th o ch ng trình nh m t b so n th o nào đó ừ ự ồ ơ ủ ấ ả ố ượ ạ ươ Phân tích t v ng (lexical analys): t o ra h s c a t t c các đ i t ủ
ng c a ch ng ụ ụ ệ ố ớ trình ph c v cho vi c phân ph i không gian nh sau này ắ ế ệ Phân tích cú pháp (syntax analys):. Cú pháp (syntax): quy t c vi t các câu l nh ể ạ ẽ ế ậ ằ ả ả (statement) đ m b o rõ nghĩa, không nh p nh ng. N u không đúng s không th t o ượ ỗ ề ượ ệ ượ ị đ ấ ả
c mã T t c các l i cú pháp đ u đ c phát hi n đ c trong khi d ch. ố ư T o mã, t
ạ i u mã (code generation, optimalization) ố ượ ế ộ ươ ỉ Liên k t: (link) k t n i các mô đun đ i t
ế ố ng thành m t ch ng trình hoàn ch nh và duy nh t.ấ ự ệ ả ươ ạ ữ ệ ể ạ ể ạ ẫ ỗ Th c hi n, t i ch ng trình và n p d li u đ ch y. Khi ch y v n còn có th có l i ữ ữ ể ệ ạ ỗ ươ ỉ
ng nghĩa. L i ng nghĩa ch có th phát hi n khi ch y ch ng trình 29 Giải thuật xử lý thông tin và ngôn ngữ lập trình ươ Ch ữ ệ
D li u
ữ ệ
D li u ầ
ạ ề
Ph n m m
ả
so n th o ng trình
d chị ươ
ng
Ch
trình liên
k t ế ả Ch ng trình Ch ả
K t quế
K t quế
xử lý
xử lý ng trình
ượ ươ
ngu nồ Các mô đun
ố ượ
đ i t ng ươ
ạ
ch y đ c ỗ
L i cú
ỗ
L i cú
pháp
pháp ỗ
L i liên
ỗ
L i liên
k tế
k tế ỗ
L i thi
ỗ
L i thi
hành
hành 30 Giải thuật xử lý thông tin và ngôn ngữ lập trình Soạn thảo Dịch Liên kết Thực hiện ƯỜ Ầ Ề MÔI TR Ể
NG PHÁT TRI N PH N M M 1985: v i s xu t hi n b phát tri n Turbo Pascal đã hình thành m t khuynh ớ ự ấ ệ ể ộ ộ ướ ớ ề ệ ạ ườ ể h ng m i v vi c t o ra các môi tr ợ
ng phát tri n tích h p IDE (Intergated ế ạ ả ộ ị Development Environment) > toàn b các quá trình so n th o, d ch, liên k t , ố ườ ự ệ ộ ệ ặ thi hành và g l ỡ ỗ ượ
i đ c th c hi n trong cùng m t m i tr ng liên h ch t chẽ b ướ ế ủ ể ướ ệ ể ố ượ ể c phát tri n ti p c a IDE là vi c phát tri n h ng đ i t ng, phát tri n ậ ẫ ướ ớ ầ ầ theo m u, l p trình h ng t ế ộ
i thành ph n (liên k t đ ng các thành ph n có ệ ị ươ ả ơ ệ ở ẵ
s n trong mã nh phân) làm vi c sinh mã ch ng trình tr nên hi u qu h n ề ấ
r t nhi u. Các h CASE (Computer Aided Software Engineering) còn cho phép phát sinh ệ 31
mã trên n n thi Giải thuật xử lý thông tin và ngôn ngữ lập trình
c ti n theo m t khuynh h ề ế ế ộ ướ ế ộ ướ t k là m t b ng khác. Ngôn ng l p trình là ph
ữ ậ ươ ễ ả ệ ể ậ ng ti n di n t ể
thu t toán đ máy tính có th ự ế ế ặ ử ụ
s d ng tr c ti p ho c gián ti p. Theo m c tr u t ừ ượ ứ ứ ữ ữ ợ ng hoá có các m c là ngôn ng máy, h p ng và ngôn ữ ả ử ụ ố ớ ợ ữ ề ầ ậ ợ ớ ị ng thu t toán. Đ i v i h p ng ph i s d ng ph n m m h p d ch, v i ể ạ ữ ề ề ầ ậ ả ầ ị ngôn ng thu t toán ph i dùng ph n m m biên d ch đ t o ra ph n m m ể ạ ữ ữ ự ng ng trong ngôn ng máy – ngôn ng mà máy có th ch y tr c ươ ứ
t
ti p.ế Các b ướ ể ị ừ ộ ươ ồ ị c chính đ d ch t m t ch ng trình ngu n sang mã nh phân là ả ạ ừ ự ị ố ư ế so n th o, phân tích t v ng, phân tích cú pháp, d ch, t i u hoá, liên k t ườ ả ợ mã. Trong các môi tr ng tích h p các khâu trên và c khâu g l ỡ ỗ ượ
i đ c 32 Giải thuật xử lý thông tin và ngôn ngữ lập trình ộ ổ ợ ể
tích h p vào trong m t t ng th . ự ệ ữ ậ ứ ữ S khác bi t gi a các m c ngôn ng l p trình, nguyên ệ ắ
t c phân bi ứ ủ
t các m c c a NNLT. ả ủ ệ ậ Đánh giá hi u qu c a các thu t toán khác nhau cùng ả ế gi ộ
i quy t m t bài toán. ư ượ ủ ừ ể ươ ể Phân tích u, nh c đi m c a t ng ph ng pháp bi u ả ậ ễ
di n gi i thu t? 33 Giải thuật xử lý thông tin và ngôn ngữ lập trình 1. ậ ụ
Thu t toán là gì? Cho ví d . 2. ậ ị Xác đ nh input và output cho các thu t toán sau đây: a. Rút gọn một phân số. b. Kiểm tra xem ba số cho trước a, b và c có thể là độ dài ba cạnh của một tam giác hay không? 3. ủ ủ ấ ấ ị ậ
Trình bày tính ch t xác đ nh c a thu t toán và nêu rõ nghĩa c a tính ch t
này 4. ế ạ ế t c nh a và góc B. Hãy vi t ể ậ ạ ạ Cho tam giác ABC có góc vuông A và cho bi
thu t toán đ tính góc C, c nh b và c nh c. 5. ể ả ể ậ ộ ố
i bài toán sau: "Có m t s qu táo. Dùng
ặ
ể ấ ả ả ị ả
Hãy phát bi u thu t toán đ gi
cân hai đĩa (không có qu cân) đ xác đ nh qu táo n ng nh t" 6. ỉ ươ ộ ố ủ ộ
Ch dùng phép c ng, tính bình ph ng c a m t s 34 Giải thuật xử lý thông tin và ngôn ngữ lập trình ữ ữ ậ ớ ợ 7. So sánh ngôn ng thu t toán v i ngôn ng máy và h p ngữ ộ ố ữ ậ ể ạ ế 8. K tên m t s ngôn ng l p trình mà b n bi t ướ ự ộ ươ ế
9. N u các b ệ
c th c hi n m t ch ng trình trên ngôn ữ ậ ng thu t gi ả
i ỗ 10. Phân bi ệ ỗ
t l i cú pháp và l ữ
i ng nghĩa ườ 11. Trình bày môi tr ợ
ể
ng phát tri n tích h p 35 Giải thuật xử lý thông tin và ngôn ngữ lập trình Máy tính điện tử và xử lý thông tinm n
m
15 21
m>n
15 6
m>n
9 6
m
3 6
m=n
3 3
USCLN(15,21) = 3
Ư
Ủ
Ặ
Ậ
CÁC Đ C TR NG C A THU T TOÁN
Ậ
Ố Ỏ
THU T TOÁN B C S I
+
-
-
-
b:= c
Ả Ủ
Ậ
Ệ
HI U QU C A THU T TOÁN
Ụ Ệ
Ả
Ế
ố
VÍ D HI U QU TÌM KI M
Ví d bụ ài toán tìm ki m: cho m t dãy n s kh
ế
Ả Ủ
Ậ
Ệ
HI U QU C A THU T TOÁN
Ữ Ậ
NGÔN NG L P TRÌNH
Ữ
NGÔN NG MÁY
Ợ
Ữ
H P NG (ASSEMBLY)
Hợp ngữ
MOV AX CHIEU_DAI
ADD AX CHIEU_RONG
MOV NUA_CHU_VI AX
Ợ
Ị
Ữ
D CH H P NG (ASSEMBLY)
Ữ Ậ
NGÔN NG B C CAO
Ữ Ậ
Ụ Ề
VÍ D V NGÔN NG B C CAO
Ữ Ậ
Ị
D CH NGÔN NG B C CAO
Ữ
Ị
D CH SANG NGÔN NG MÁY
ắ ộ
Tóm t
t n i dung
Ậ
Ả
TH O LU N
Ỏ
Ậ
CÂU H I VÀ BÀI T P
Ỏ
Ậ
CÂU H I VÀ BÀI T P
Ỏ
H I VÀ ĐÁP
