Công ty Cổ phần Mạng giáo dục Bạch Kim - 27 Huỳnh Thúc Kháng, Đống Đa, Hà Nội
Trang bìa
Trang bìa:
BÀI TOÁN
Ví dụ 1::
VÝ dô 1: Qu¶n lÝ ®iÓm trong mét k× thi b»ng m¸y tÝnh. Yªu cÇu : H·y x¸c ®Þnh th«ng tin ®­a vµo (Input) vµ th«ng tin cÇn lÊy ra (Output) Đáp án::
VÝ dô 1: Qu¶n lÝ ®iÓm trong mét k× thi b»ng m¸y tÝnh. Input: SBD, Hä vµ tªn, V¨n, To¸n, LÝ, Anh.  Output: Tæng ®iÓm, KÕt qu¶ thi cña häc sinh. Ví dụ 2::
VÝ dô 2: Gi¶i ph­¬ng tr×nh bËc nhÊt ax b = 0. Yªu cÇu : H·y x¸c ®Þnh th«ng tin ®­a vµo (Input) vµ th«ng tin cÇn lÊy ra (Output) Input: C¸c hÖ sè a, b.  Output: NghiÖm cña ph­¬ng tr×nh. Víi a = 1, b = -5  Ph­¬ng tr×nh cã nghiÖm x = 5 KHÁI NIỆM
Bài toán:
1. Kh¸i niÖm bµi to¸n VÝ dô 3: T×m ­íc sè chung lín nhÊt cña hai sè nguyªn d­¬ng. INPUT: Hai sè nguyªn d­¬ng M vµ N. OUTPUT: ­íc sè chung lín nhÊt cña M vµ N. VÝ dô 4: Bµi to¸n xÕp lo¹i häc tËp cña mét líp. INPUT: B¶ng ®iÓm cña häc sinh trong líp. OUTPUT: B¶ng xÕp lo¹i häc lùc cña häc sinh. Thuật toán:
2. Kh¸i niÖm thuËt to¸n Ví dụ:
XÐt vÝ dô 2: Gi¶i ph­¬ng tr×nh bËc nhÊt ax b = 0. B1: X¸c ®Þnh hÖ sè a, b; B2: NÕu a=0 vµ b=0 => Ph­¬ng tr×nh v« sè nghiÖm =>B5; B3: NÕu a=0 vµ b≠0 => Ph­¬ng tr×nh v« nghiÖm =>B5; B4: NÕu a≠0 => Ph­¬ng tr×nh cã nghiÖm x=-b/a =>B5; B5: KÕt thóc. Khái niệm:
Cã hai c¸ch thÓ hiÖn mét thuËt to¸n:  C¸ch 1: LiÖt kª c¸c b­íc.  C¸ch 2: VÏ s¬ ®å khèi. BÀI TOÁN
Ví dụ :
3. Một số ví dụ về thuật toán Cách 1: Liệt kê các bước B1: Bắt đầu; B2: Nhập a, b, c; B3: Tính latex(Delta = b^2 - 4ac) B4: Nếu latex(Delta)< 0 => PT vô nghiệm => B7 B5: Nếu latex(Delta)= 0 => PT có nghiệm kép x = -b/2a => B7; B6: Nếu latex(Delta)> 0 => PT có hai nghiệm latex(x_1, x_2 =(-b - sqrt(Delta))/(2a)) => B7; B7: Kết thúc. Sơ đồ khối:
Quy ­íc c¸c khèi trong s¬ ®å thuËt to¸n B¾t ®Çu thuËt to¸n. Dïng ®Ó nhËp vµ xuÊt d÷ liÖu. Dïng ®Ó g¸n gi¸ trÞ vµ tÝnh to¸n. XÐt ®iÒu kiÖn rÏ nh¸nh theo mét trong hai ®iÒu kiÖn ®óng, sai. KÕt thóc thuËt to¸n. Đ S C¸ch 2: VÏ s¬ ®å khèi Các bước giải:
S¬ ®å thuËt to¸n gi¶i ph­¬ng tr×nh bËc hai 2 ® s ® s Bài test 1:
PT v« nghiÖm KT Bé TEST 1: S PT có 2 nghiệm latex(x_1, x_2 = (-b - sqrt(Delta))/(2a)) § S M« pháng thuËt to¸n gi¶i ph­¬ng tr×nh bËc hai D = b*b - 4*a*c nhập vào a,b,c latex(Delta < 0) BD Bài test 2:
PT v« nghiÖm KT Bé TEST 2: S PT có 2 nghiệm latex(x_1, x_2 = (-b - sqrt(Delta))/(2a)) § S M« pháng thuËt to¸n gi¶i ph­¬ng tr×nh bËc hai D = b*b - 4*a*c nhập vào a,b,c latex(Delta < 0) BD Bài test 3:
PT v« nghiÖm KT Bé TEST 3: S PT có 2 nghiệm latex(x_1, x_2 = (-b - sqrt(Delta))/(2a)) § S M« pháng thuËt to¸n gi¶i ph­¬ng tr×nh bËc hai D = b*b - 4*a*c nhập vào a,b,c latex(Delta < 0) BD TÌM MAX
Đặt vấn đề:
ThuËt to¸n t×m max Ng­êi ta ®Æt 5 qu¶ bãng cã kÝch th­íc kh¸c nhau trong hép ®· ®­îc ®Ëy n¾p nh­ h×nh bªn. ChØ dïng tay h·y t×m ra qu¶ bãng cã kÝch th­íc lín nhÊt . Tìm thuật toán:
Cïng t×m thuËt to¸n Ví dụ:
Xác định bài toán: INPUT: Số nguyên dương N và dãy N số nguyên latex(a_1, a_2, , , a_N (a_i , i: 1 rarr N)) OUTPUT: Số lớn nhất (Max) của dãy số. Cách giải:
Ý tưởng: - Đặt giá trị Max = a1. - Lần lượt cho i chạy từ 2 đến N, so sánh giá trị ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai. Cách 1:
C¸ch 1: LiÖt kª c¸c b­íc B1: NhËp N vµ d·y latex(a_1,..., a_N); B2: latex(Max larr a1; i larr 2); B3: NÕu i > N th× ®­a ra gi¸ trÞ Max råi kÕt thóc; B4: B­íc 4.1: NÕu latex(a_i > Max) th× Max latex(larr a_i); B­íc 4.2: i latex(larr) i 1 råi quay l¹i B3. Cách 2:
§ S § S C¸ch 2: S¬ ®å khèi Mô phỏng:
KIỂM TRA SNT
Ví dụ::
X¸c ®Þnh bµi to¸n: INPUT: N lµ mét sè nguyªn d­¬ng. OUTPUT: Tr¶ lêi c©u hái N cã lµ sè nguyªn tè kh«ng? Phân tích:
ý t­ëng: XÐt c¸c tr­êng hîp - NÕu N = 1 th× N kh«ng lµ sè nguyªn tè. - NÕu 1< N <4 th× N lµ sè nguyªn tè. Mô phỏng:
M« pháng thuËt to¸n kiÓm tra tÝnh nguyªn tè 45 kh«ng lµ sè nguyªn tè. 29 lµ sè nguyªn tè. Liệt kê bước:
C¸ch 1: LiÖt kª c¸c b­íc B1: NhËp sè nguyªn d­¬ng N; B2: NÕu N = 1 th«ng b¸o N kh«ng nguyªn tè, kÕt thóc; B3: NÕu N < 4 th«ng b¸o N lµ nguyªn tè råi kÕt thóc; B4: latex(i larr 2); B5: NÕu i > [latex(sqrt(N))] th× th«ng b¸o N lµ nguyªn tè, kÕt thóc; B6: 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; B7: i latex(larr) i 1 råi quay l¹i B5. Sơ đồ khối:
SẮP XẾP
Ví dụ:
ThuËt to¸n s¾p xÕp H·y t×m c¸ch s¾p xÕp häc sinh ®øng chµo cê (h×nh a) theo thø tù thÊp tr­íc cao sau (h×nh b). H×nh a H×nh b Xác định yêu cầu:
X¸c ®Þnh bµi to¸n: INPUT: D·y A gåm N sè nguyªn latex(a_1, a_2,..., a_N). OUTPUT: D·y A ®­îc s¾p xÕp thµnh d·y kh«ng gi¶m. Ý tưởng:
ý t­ëng: Víi mçi cÆp sè h¹ng ®øng liÒn kÒ trong d·y, nÕu sè tr­íc lín h¬n sè sau ta ®æi vÞ trÝ chóng cho nhau. ViÖc ®ã ®­îc lÆp l¹i cho ®Õn khi kh«ng cã sù ®æi chç nµo x¶y ra n÷a. Thuật toán:
 Víi N = 6 vµ d·y A gåm 6 sè h¹ng nh­ sau :  L­ît thø nhÊt:  L­ît thø hai:  L­ît thø ba:  L­ît thø t­: M« pháng thuËt to¸n s¾p xÕp b»ng tr¸o ®æi Cách 1:
C¸ch 1: LiÖt kª c¸c b­íc B1: NhËp N, c¸c sè h¹ng latex(a_1, a_2,..., a_N); B2: M  N; B3: NÕu M < 2 th× ®­a ra d·y A ®· s¾p xÕp råi kÕt thóc; B4: M  M – 1; i  0; B5: i  i 1; B6: NÕu i > M th× quay l¹i B3; B7: NÕu ai > ai 1 th× tr¸o ®æi ai vµ ai 1 cho nhau; B8: Quay l¹i B5. Cách 2::
TÌM KIẾM
Bài toán:
ThuËt to¸n t×m kiÕm C1: T×m kiÕm tuÇn tù ( më tõng mò) C2: Do c¸c mò ®· s¾p xÕp lín dÇn, hai mò ®Çu nhá h¬n ng­êi cña B«ng nªn chØ t×m hai mò sau th«i! Phân tích:
X¸c ®Þnh bµi to¸n: INPUT: D·y A gåm N sè nguyªn latex(a_1, a_2,..., a_N) ®«i mét kh¸c nhau vµ sè nguyªn k. OUTPUT: ChØ sè i mµ ai = k hoÆc th«ng b¸o kh«ng cã sè h¹ng nµo cña A b»ng k. Thuật toán:
5 4 3 2 1 I 51 25 11 8 9 2 4 1 7 5 A M« pháng thuËt to¸n t×m kiÕm tuÇn tù  Víi k = 2 vµ d·y A gåm 10 sè h¹ng nh­ sau:  Víi k = 6 vµ d·y A gåm 10 sè h¹ng nh­ sau: Ý tưởng:
ý t­ëng: LÇn l­ît tõ sè h¹ng thø nhÊt, ta so s¸nh gi¸ trÞ sè h¹ng ®ang xÐt víi kho¸ (k) cho ®Õn khi cã sù trïng nhau, nÕu ®· xÐt tíi sè h¹ng cuèi cïng mµ kh«ng cã sù trïng nhau th× cã nghÜa lµ d·y A kh«ng cã sè h¹ng nµo cã gi¸ trÞ b»ng k. Cách 1:
C¸ch 1: LiÖt kª c¸c b­íc B­íc 1: NhËp N, c¸c sè h¹ng latex(a_1, a_2,..., a_N) vµ gi¸ trÞ kho¸ k; B­íc 2: latex(i larr 1); B­íc 3: NÕu ai = k th× th«ng b¸o chØ sè i, råi kÕt thóc; B­íc 4: latex(i larr i 1); B­íc 5: NÕu i > N th× th«ng b¸o d·y A kh«ng cã sè h¹ng nµo cã gi¸ trÞ b»ng k, råi kÕt thóc; B­íc 6: Quay l¹i B3. Cách 2:
Tìm kiếm nhị phân:
Ý tưởng: Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm bằng cách so sánh k với số hạng ở giữa dãy a giữa, khi đó chỉ xảy ra một trong ba trường hợp: - Nếu latex(a_(giữa) = k rArr) tìm được chỉ số, kết thúc; - Nếu latex(a_(giữa) > k rArr) do dãy A đã được sắp xếp tăng nên việc tìm kiếm thu hẹp chỉ xét từ latex(a_1 -> a_(giữa - 1)); - Nếu latex(a_(giữa) < k rArr) do dãy A đã được sắp xếp tăng nên việc tìm kiếm thu hẹp chỉ xét từ latex(a_(giữa 1) -> a_N). Quá trình trên được lặp đi lặp lại cho đến khi tìm được OUTPUT. Ví dụ::
M« pháng thuËt to¸n t×m kiÕm nhÞ ph©n 10 9 8 7 6 5 4 3 2 1 i 33 31 30 22 21 9 6 5 4 2 A  Víi k = 21 vµ d·y A gåm 10 sè h¹ng nh­ sau: L­ît thø nhÊt: latex(a_(gi÷a) lµ a_5 = 9; 9 < 21 ) => vïng t×m kiÕm thu hÑp trong ph¹m vi tõ latex(a_6 -> a_10); L­ît thø hai: agi÷a lµ a8 = 30; 30 > 21 => vïng t×m kiÕm thu hÑp trong ph¹m vi tõ latex(a_6 rArr a_7); => L­ît thø ba: Latex(a_(gi÷a) lµ a_6) = 21; 21= 21  VËy sè cÇn t×m lµ i = 6. 6 Các bước:
Liệt kê các bước Bước 1: Nhập N, các số hạng latex(a_1, a_2,..., a_N) và giá trị khoá k; Bước 2: Đầu latex(larr) 1, Cuối latex(larr) N; Bước 3: Giữa latex(larr) [(Đầu Cuối)/2]; Bước 4: Nếu latex(a_(Giữa)) = k thì thông báo chỉ số Giữa rồi kết thúc; Bước 5: Nếu latex(a_(Giữa)) > k thì đặt Cuối = Giữa - 1 rồi chuyển sang bước 7; Bước 6: Đầu latex(larr) Giữa 1; Bước 7: Nếu Đầu latex(<=) Cuối thì thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc; Bước 8: Quay lại bước 3. Tổng kết:
1. Kh¸i niÖm bµi to¸n Bµi to¸n vµ thuËt To¸n 2. Kh¸i niÖm thuËt to¸n Thuật toán tìm Max của một dãy số. Thuật toán giải phương trình bậc hai (latex(a!= 0)) Thuật toán kiểm tra tính nguyên tố của một số dương Thuật toán sắp xếp bằng tráo đổi Thuật toán tìm kiếm tuần tự và nhị phân