Bài giảng Tin học đại cương - Chương 3: Tổng quan Phương pháp giải bài toán trên máy tính

18 trang ngocly 2950

Download

Bạn đang xem tài liệu "Bài giảng Tin học đại cương - Chương 3: Tổng quan Phương pháp giải bài toán trên máy tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_tin_hoc_dai_cuong_chuong_3_tong_quan_phuong_phap_g.pdf

Nội dung text: Bài giảng Tin học đại cương - Chương 3: Tổng quan Phương pháp giải bài toán trên máy tính

Dùng cho nhóm ngành: Công trình + C ơ khí TIN HỌC ĐẠI CƯƠNG Ch ươ ng 3: Tổng quan Ph ươ ng pháp gi ải bài toán trên máy tính bangtqh@utc2.edu.vn Nội dung 1. Khái ni ệm v ề v ấn đề và bài toán 2. Các b ướ c gi ải quy ết bài toán b ằng máy tính 3. Thu ật toán và thu ật gi ải 4. Bi ểu di ễn thu ật toán và thu ật gi ải 5. Một s ố thu ật toán th ườ ng g ặp bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 2
2.1. Khái ni ệm bài toán và thu ật toán Bài toán – Trong ph ạm vi tin h ọc, bài toán đượ c hi ểu là m ột công vi ệc nào đó mà ta mu ốn máy tính th ực hi ện. – 2 y ếu t ố quan tr ọng c ủa bài toán: • Input: d ữ li ệu đư a vào • Output: k ết qu ả c ần tìm c ủa bài toán. – Vd: Vi ết m ột dòng ch ữ ra màn hình. Bài toán gi ải ph ươ ng trình b ậc 2; Bài toán qu ản lý điểm v.v Thu ật 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 khi th ực hi ện dãy thao tác đó thì t ừ Input c ủa bài toán ta s ẽ có Output c ần tìm bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 3 2.2. Các bước gi ải bài toán Bướ c 1 - Xác đị nh bài toán – Xác đị nh rõ Input và Output c ủa bài toán. –Cần xác đị nh input, output một cách cẩn th ận vì nó sẽ ảnh hưở ng tới vi ệc lựa ch ọn thu ật toán gi ải quy ết. Trong tin học, đôi khi vi ệc xác đị nh input/output còn ph ụ thu ộc vào ngôn ng ữ lập trình sử dụng. Bướ c 2 - Thi ết kế thu ật toán – Là bướ c quan tr ọng nh ất để gi ải bài toán –Một bài toán có th ể có nhi ều thu ật toán để gi ải quy ết –Cần quan tâm tới tính hi ệu qu ả của thu ật toán (v ề bộ nh ớ, về th ời gian th ực hi ện v.v) bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 4
2.2. Các bước gi ải bài toán (tt) Bướ c 3 – Vi ết ch ươ ng trình –Lựa ch ọn ngôn ng ữ l ập trình phù h ợp v ới nhu c ầu và kh ả n ăng c ủa b ản thân –Cần t ận d ụng các ti ện ích mà các IDE ( Integrated Deverlopment Environment ) Bướ c 4 – Hi ệu ch ỉnh, làm tinh ch ươ ng trình –Cần đư a nhi ều b ộ s ố li ệu khác nhau vào ki ểm th ử – Đôi khi c ần có kinh nghi ệm và đầ u óc phán đoán l ỗi. Bướ c 5 – Vi ết tài li ệu – Là h ướ ng d ẫn s ử d ụng, k ết qu ả th ử nghi ệm, ho ặc mô tả chi ti ết thu ật toán bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 5 2.3. Thuật toán – Thuật gi ải Đị nh ngh ĩa: – Thu ật toán (algorithm) 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 khi th ực hi ện dãy thao tác đó thì t ừ Input c ủa bài toán ta s ẽ có Output c ần tìm. Các đặ c tr ưng c ủa thu ật toán – Tính h ữu h ạn – Tính xác đị nh – Tính đúng đắ n – Tính chi ti ết: thao tác trong thu ật toán ph ải ch ặt ch ẽ, đủ chi ti ết để 1 đố i tượ ng có th ể th ực hi ện đượ c thu ật toán. – Tính ph ổ d ụng bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 6
Từ gi ải thuật đế n chương trình Gi ải thu ật ch ỉ là “ph ươ ng pháp”. Sử d ụng gi ải thu ật nh ư th ế nào để gi ải quy ết bài toán –Cần ph ải có máy tính. –Lập trình: Mô t ả (cài đặ t) gi ải thu ật lên máy tính. Bi ểu di ễn đố i t ượ ng x ử lý b ởi d ữ li ệu (data) trong ch ươ ng trình (có nhi ều ki ểu d ữ li ệu v ới c ấu trúc khác nhau). Thu ật gi ải + c ấu trúc d ữ li ệu = ch ươ ng trình DATA STRUCTURES +ALGORITHMS = PROGRAM bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 7 Có ph ải mọi bài toán đề u có thu ật gi ải ? Có nh ững bài toán không có gi ải thu ật tổng quát để gi ải quy ết. Có nh ững bài toán ch ưa có gi ải thu ật hữu hi ệu để gi ải quy ết. Có nh ững bài toán ch ưa có gi ải thu ật tìm lời gi ải. bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 8
2.4. Bi ểu di ễn thuật toán Li ệt kê t ừng b ướ c Sử d ụng s ơ đồ kh ối Sử d ụng gi ả ngôn ng ữ l ập trình bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 9 Phương pháp li ệt kê t ừng bước Các thao tác của gi ải thu ật đượ c li ệt kê từng bướ c. Tại mỗi bướ c, sử dụng ngôn ng ữ tự nhiên để di ễn tả công vi ệc ph ải làm. Bướ c đứ ng tr ướ c (có số th ứ tự nh ỏ hơn) đượ c th ực hi ện tr ướ c. Ưu nh ượ c điểm –Dễ hi ểu, dễ làm – Ph ụ thu ộc vào “cách hành văn” của ng ườ i di ễn đạ t –Với nh ững gi ải thu ật ph ức tạp, cách di ễn đạ t này tr ở nên rườ m rà – bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 10
Ví dụ Gi ải thu ật “Tìm v ị trí xu ất hi ện đầ u tiên c ủa m ột s ố nguyên trong dãy s ố nguyên đã cho”: –Bướ c 1 : Nh ập dãy s ố nguyên a 1, a 2, ., a N –Bướ c 2 : Nh ập s ố nguyên s –Bướ c 3 : Gán v ị trí p ban đầ u = 0 và v ị trí i đang xét = 1 p = 0, i=1 –Bướ c 4 : So sánh a i với s •Nếu a i =s thì ghi nh ận v ị trí p = i Sang Bướ c 5 •Nếu a i ≠ s và i < N thì gán i=i+1 và l ặp l ại bướ c 4 , ng ượ c l ại sang Bướ c 5 –Bướ c 5 : N ếu p ≠ 0 thì đư a ra v ị trí c ần tìm là p, ng ượ c l ại thông báo không tìm th ấy giá tr ị s trong dãy s ố đã cho. –Bướ c 6 : K ết thúc. bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 11 Bi ểu di ễn thu ật toán b ằng s ơ đồ kh ối Sử d ụng các hình kh ối để minh ho ạ cho các l ệnh hay thao tác. Sử d ụng m ũi tên để di ễn đạ t th ứ t ự th ực hi ện. Đây là cách di ễn đạ t khoa h ọc, có tính nh ất quán cao . Các hình kh ối c ơ b ản – Kh ối b ắt đầ u. – Kh ối k ết thúc. – Kh ối thao tác c ụ th ể. – Kh ối ki ểm tra điều ki ện. – Kh ối vào/ra d ữ li ệu. – Kh ối g ọi ch ươ ng trình con. Các ký pháp. bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 12
Các hình khối c ơ bản Gọi ch ươ ng trình con A ( ít Kh ối b ắt đầ u và k ết thúc dùng ) Begin A End Kh ối th ực thi công vi ệc A Kh ối ki ểm tra điều ki ện – Tu ỳ thu ộc điều ki ện ( Đúng A hay Sai) mà r ẽ nhánh thích hợp Kh ối input/output Đúng Điểm n ối Điều ki ện Sai bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 13 Sơ đồ một s ố c ấu trúc c ơ bản Cấu trúc r ẽ nhánh Cấu trúc l ặp True True If then while do False False Xö lý nÕu §iÒu KiÖn §óng ®óng If then Sai repeat until else Xö lý nÕu sai True False bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 14
Tính chu vi và di ện tích HCN Ph ươ ng pháp li ệt kê Sơ đồ kh ối – B1. Nh ập hai c ạnh a,b – B2. Tính chu vi Begin • C = 2*(a+b) – B3. Tính di ện tích §äc c¹nh a,b • S = a*b – B4. In chu vi C C := 2*(a+b) – B5. In di ện tích S S := a*b –Kết thúc In ra C,S End bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 15 Tính chu vi, di ện tích tam giác Ph ươ ng pháp li ệt kê Sơ đồ thu ật toán – B1. Nh ập c ạnh a,b,c – B2. Ki ểm tra xem a,b,c có ph ải ba cạnh tam giác không •Nếu (a+b>c) và (b+c>a) và (a+c>b) thì sang b ướ c 3 •Nếu không thì thông báo “không t ạo thành tam giác” và kết thúc – B3. Tính chu vi C = (a+b+c) – B4. Tính n ửa chu vi p = C/2 – B5. Tính di ện tích tam giác theo p (* p− a (*) p− b (*) p− c) công th ức Hê-rông • S = p (* p−a (*) p−b (*) p−c) – B6. In k ết qu ả C,S bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 16
Bi ểu di ễn thu ật toán b ằng gi ả ngôn ng ữ Gi ả ngôn ng ữ –Dựa trên ngôn ng ữ l ập trình b ậc cao. –Gần v ới ngôn ng ữ t ự nhiên c ủa con ng ườ i. – Ví d ụ: • Ngôn ng ữ gi ả Pascal (tựa Pascal ) có các ký pháp khá gi ống với ngôn ng ữ l ập trình Pascal, đượ c rút g ọn sao cho d ễ di ễn đạ t. Gi ả ngôn ng ữ đượ c đư a ra v ới m ục đích di ễn đạ t các gi ải thu ật sao cho g ần v ới ngôn ng ữ l ập trình và ngôn ng ữ t ự nhiên. Sử d ụng gi ả ngôn ng ữ khi ến vi ệc chuy ển t ừ gi ải thu ật sang ch ươ ng trình d ễ dàng h ơn. bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 17 Gi ải thu ật tính t ổng N s ố t ự nhiên đầ u tiên Nh ập N i:=0 S:=0 REPEAT S:=S+i i:=i+1 UNTIL (i>N) In S bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 18
Thi ết k ế thuật toán Các b ướ c gi ải bài toán trên máy tính: – Xác đị nh bài toán – Thi ết k ế gi ải thu ật – Vi ết ch ươ ng trình – Hi ệu ch ỉnh, làm tinh – Vi ết tài li ệu Thi ết k ế gi ải thu ật là t ừ yêu c ầu c ủa m ột bài toán, di ễn đạ t một gi ải thu ật gi ải quy ết bài toán đó. – Mô-đun hoá vi ệc gi ải quy ết bài toán. – Tinh ch ỉnh t ừng b ướ c. Phân tích gi ải thu ật – Xem xét các tiêu chu ẩn c ủa gi ải thu ật có đượ c tho ả mãn không, n ếu có thì đế n m ức độ nào. bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 19 Thi ết k ế t ừ trên xuống Các bài toán l ớn đòi h ỏi gi ải thu ật có quy mô l ớn. Mô-đun hoá BÀI TOÁN – Bài toán = nhi ều mô-đun – Mô-đun l ớn = nhi ều mô-đun con. A B C – Vi ệc gi ải quy ết m ột mô-đun ở m ức th ấp nh ất là “ đủ đơ n gi ản” A1 A2 C1 C2 Chia để tr ị. A2.1 A2.2 A2.3 Thi ết kế từ trên xu ống (top- down design ): Bài toán đượ c xem xét từ tổng quát đế n chi ti ết. bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 20
Bài toán gi ải ph ương trình b ậc 2 GI ẢI PH ƯƠ NG TRÌNH B ẬC II NH ẬP H Ệ S Ố XỬ LÝ HI ỂN TH Ị K ẾT QU Ả TR ƯỜ NG H ỢP SUY BI ẾN TR ƯỜ NG H ỢP KHÔNG SUY BI ẾN TÍNH DELTA TÍNH NGHI ỆM THEO DELTA bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 21 Ph ương pháp tinh ch ỉnh t ừng b ước Ph ươ ng pháp tinh ch ỉnh t ừng b ướ c ( stepwise refinement ) – Ban đầ u, s ử d ụng ngôn ng ữ t ự nhiên để di ễn t ả nh ững công vi ệc chính c ủa gi ải thu ật. – Các b ướ c sau, các công vi ệc đượ c chi ti ết hoá d ần dần, ngôn ng ữ t ự nhiên đượ c thay th ế d ần d ần bằng gi ả ngôn ng ữ. – Cu ối cùng, gi ả ngôn ng ữ đượ c chuy ển sang ngôn ng ữ l ập trình Đặ c điểm – Th ể hi ện rõ ý t ưở ng thi ết k ế t ừ trên xu ống –Gắn li ền vi ệc thi ết k ế gi ải thu ật v ới vi ệc l ập trình bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 22
Bài toán s ắp x ếp dãy s ố (t ăng d ần) Phác th ảo “thô” v ới nh ững “ý t ưở ng c ơ b ản” – “T ừ dãy các s ố ch ưa đượ c s ắp x ếp, tìm s ố nh ỏ nh ất và đư a lên đầ u” –Lặp l ại quy trình trên t ới khi dãy ch ưa đượ c s ắp x ếp tr ở thành r ỗng. Ban đầ u, dãy ch ưa s ắp x ếp là dãy đã cho, dãy đã s ắp x ếp là rỗng. Lưu tr ữ dãy b ằng “m ảng” (danh sách các s ố), đư a s ố nh ỏ nh ất (a j) lên đầ u danh sách là đổ i ch ỗ nó v ới s ố đầ u tiên. Đổ i ch ỗ –Số trung gian := a j – aj := s ố đầ u tiên –Số đầ u tiên : = s ố trung gian , cu ối cùng ta đượ c ch ươ ng trình v ới ngôn ng ữ c ụ th ể bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 23 Phân tích thuật toán Tính đúng đắ n – Ch ạy th ử nghi ệm, đố i chi ếu k ết qu ả phát hi ện đượ c tính sai. – Dùng công c ụ toán h ọc để ch ứng minh tính đúng đắ n. Tính đơ n gi ản – Gi ải thu ật có d ễ hi ểu, d ễ l ập trình không? Tính hi ệu qu ả – Đơ n gi ản ch ưa ch ắc đã hi ệu qu ả. – Đố i v ới nhi ều bài toán, tính hi ệu qu ả là quan tr ọng, các gi ải thu ật đơ n gi ản l ại gây t ốn tài nguyên, ch ạy ch ậm. – Th ời gian tính toán Độ ph ức t ạp tính toán – Nh ững gi ải thu ật hi ệu qu ả ph ải có độ ph ức t ạp (th ời gian) tính toán ch ấp nh ận đượ c. Tính h ữu h ạn d ừng – Ch ứng minh, suy lu ận – Ch ạy th ử bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 24
Độ phức t ạp c ủa thuật toán Độ ph ức t ạp th ời gian: – Là th ời gian máy tính s ử d ụng để gi ải bài toán theo gi ải thu ật đang xét. (v ới b ộ input có kích th ướ c xác đị nh) – Có th ể bi ểu di ễn thông qua s ố l ượ ng các phép tính đượ c dùng bởi thu ật toán. Độ ph ức t ạp không gian – Là dung l ượ ng b ộ nh ớ c ần thi ết mà máy tính s ẽ s ử d ụng để gi ải bài toán theo gi ải thu ật đang xét (v ới b ộ input có kích th ướ c xác đị nh) Ví d ụ: – Bài toán tìm s ố l ớn nh ất trong dãy s ố a 1, a 2, ,a N. –Nếu coi phép so sánh 2 s ố c ủa thu ật toán c ần 1 đơ n v ị th ời gian Độ ph ức t ạp th ời gian c ủa thu ật toán s ẽ là n-1 (n ếu bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 25 Độ phức t ạp c ủa thuật toán (tt) Bài toán tính giá tr ị đa th ức: n n-1 P(x) = a nx + a n-1x + + a 1x + a 0 Khi x = x 0 Thu ật toán 1 Thu ật toán 2 S = a ; 0 S = a 0; For i = 1 To n For i = 1 To n i S = S + a i*x 0 S = S*x 0 + a n-i Số phép tính(* và + ) là: n(n+3)/2 Số phép tính(* và + ) là: 2n bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 26
Độ phức t ạp c ủa thuật toán (tt) Hàm th ể hi ện độ ph ức t ạp c ủa thu ật toán – Để so sánh độ ph ức tạp của các thu ật toán ng ườ i ta coi độ ph ức tạp của mỗi thu ật toán nh ư là cấp của hàm bi ểu hi ện th ời gian th ực hi ện thu ật toán đó. Đị nh ngh ĩa Big-O – hàm f(n) có cấp th ấp hơn ho ặc bằng hàm g(n) nếu tồn tại hằng C > 0 và một số tự nhiên n0 sao cho |f(n)| ≤ C|g(n)| với mọi n ≥ n0 Ta vi ết f(n) = O(g(n)) hay còn nói hàm f(n) th ỏa mãn quan hệ Big-O với g(n) – vd : f(n) = n(n+3)/2 và g(n) = n 2 khi đó f(n) = O(g(n)) = O(n 2) vì f(n) ≤ 3 g(n) v ới n ≥3 bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 27 Độ phức t ạp c ủa thuật toán (tt) Đị nh ngh ĩa – nếu một thu ật toán có độ ph ức tạp là f(n) trong đó f(n) = O(g(n)) thì ta nói thu ật toán đó cũng đồ ng th ời có độ ph ức tạp là “O lớn g(n) ” – nếu bài toán có 2 thu ật toán với độ ph ức tạp lần lượ t là O(g 1(n)) và O(g 2(n)) mà bậc của g1(n) th ấp hơn bậc của g2(n) thì ta nói thu ật toán 1 hi ệu qu ả hơn thu ật toán 2 –Một cách t ổng quát: k k-1 k nếu f(n) = a kn + a k-1n + +a 1n+a 0 thì f(n) = O(n ) (f 1 + f 2)(n) = O(max(|g 1(n)|,|g 2(n)|), (f 1f2)(n)) = O(g 1(n)g 2(n)) bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 28
Độ phức t ạp c ủa thuật toán (tt) Các thu ật ng ữ th ườ ng dùng bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 29 Độ phức t ạp c ủa thuật toán (tt) Độ ph ức t ạp thu ật toán và Th ời gian th ực hi ện bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 30
2.5. Một s ố thu ật toán th ường g ặp Bài toán tìm ki ếm – Thu ật toán tìm ki ếm tuy ến tính – Thu ật toán tìm ki ếm nh ị phân Bài toán tìm s ố USCLN c ủa 2 s ố – Thu ật toán l ặp, ki ểm tra các giá tr ị t ừ 1,2, ,min(a, b) – Thu ật toán phân tích các s ố nguyên đã cho thành các th ừa s ố nguyên t ố. – Thu ật toán euclide Bài toán s ắp x ếp dãy t ăng/gi ảm d ần – Thu ật toán n ổi b ọt (bubble sort) – Thu ật toán ch ọn tr ực ti ếp (selection sort) – Thu ật toán chèn tr ực ti ếp (insertion sort) – Thu ật toán s ắp vun đố ng (heap sort) bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 31 2.5. Một s ố thu ật toán th ường g ặp Thu ật toán đệ quy – Đị nh ngh ĩa: M ột thu ật toán đượ c g ọi là đệ quy n ếu nó gi ải bài toán b ằng cách rút g ọn liên ti ếp bài toán ban đầ u t ới bài toán đồ ng d ạng v ới d ữ li ệu đầ u vào nh ỏ h ơn. – Ví d ụ: • Bài toán tính n! • Bài toán tìm s ố th ứ n c ủa dãy s ố Fibonaci • Bài toán tìm USCLN c ủa 2 s ố a, b • Bài toán tìm ki ếm nh ị phân • Bài toán tháp Hà N ội bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 32
Bài t ập Vẽ sơ đồ bi ểu di ễn thu ật toán tìm trung bình cộng của dãy số a1, a2, , an Vẽ sơ đồ bi ểu di ễn thu ật toán tìm TBC các số ch ẵn và chia hết cho 5 trong dãy số a1, a2, , an Vẽ sơ đồ bi ểu di ễn thu ật toán đế m xem trong dãy số a1, a2, , an có bao nhiêu cặp có ch ỉ số liên ti ếp (vd: a2, a3) th ỏa điều ki ện tích chúng chia hết tổng của chúng. Vẽ sơ đồ kh ối bi ểu di ễn thu ật toán ki ểm tra xem 1 số nguyên N có là số nguyên tố hay không? bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 33 Bài t ập (tt) 1. Hãy v ẽ s ơ đồ thu ật toán tìm và in ra các s ố là s ố nguyên t ố trong dãy s ố a 1, a2, ,a N 2. Hãy v ẽ s ơ đồ th ể hi ện thu ật toán tính giá tr ị c ủa bi ểu th ức x + x 2 + x 3 + + x N 3. Hãy v ẽ s ơ đồ thu ật toán tìm trong s ố các ph ần t ử c ủa dãy a 1, a 2, ,a N có bao nhiêu c ặp (a i, a j) v ới i ≠j th ỏa điều ki ện a i+a j = x 4. Hãy v ẽ s ơ đồ th ể hi ện thu ật toán đổ i m ột s ố nguyên d ươ ng N sang h ệ đế m c ơ số 2 (h ệ nh ị phân). 5. Hãy v ẽ s ơ đồ th ể hi ện thu ật toán gi ải ph ươ ng trình b ậc 2 ax 2+ bx + c = 0 6. Hãy v ẽ s ơ đồ th ể hi ện toán tìm tích c ủa 2 ma tr ận A mxn và B nxp 7. Hãy v ẽ s ơ đồ th ể hi ện thu ật toán tìm độ dài c ủa đườ ng g ấp khúc đi qua N điểm trên m ặt ph ẳng M 1(x 1, y 1), M 2(x 2, y 2), ,M n(x n, y n). 8. Vẽ s ơ đồ th ể hi ện thu ật toán s ắp x ếp l ại dãy s ố a 1, a 2, ,an theo th ứ t ự gi ảm dần. 9. Vẽ s ơ đồ th ể hi ện thu ật toán tìm các ph ần t ử trong dãy a 1, a 2, ,an th ỏa điều ki ện a i = a i-1 + ai-2 + + a 2+ a 1 10. Vẽ s ơ đồ th ể hi ện thu ật toán tìm trung bình c ộng c ủa các ph ần t ử là s ố chính ph ươ ng trong dãy a 1, a 2, ,a N bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 34
bangtqh@utc2.edu.vn Tin h ọc đạ i c ươ ng - Ch ươ ng 3 35