Slide 1: BAØI TOAÙN VAØ THUAÄT TOAÙN BAØI TOAÙN VAØ THUAÄT TOAÙN BAØI TOAÙN VAØ THUAÄT TOAÙN Baøi 4
Slide 2: 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) 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.
Slide 3: 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
Slide 4: 1. Kh¸i niÖm bµi to¸n Lµ viÖc nµo ®ã ta muèn m¸y thùc hiÖn ®Ó tõ th«ng tin ®a vµo (INPUT) t×m ®îc th«ng tin ra (OUTPUT). 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. Bµi 4. Bµi to¸n vµ thuËt To¸n
Slide 5: 2. Kh¸i niÖm thuËt to¸n Tõ INPUT lµm thÕ nµo ®Ó t×m ra OUTPUT ? C¸c em cÇn t×m ra c¸ch gi¶i cña bµi to¸n.
Slide 6: 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.
Slide 7: ThuËt to¸n ®Ó gi¶i mét bµi 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 sau khi thùc hiÖn d·y thao t¸c Êy, tõ Input cña bµi to¸n, ta nhËn ®îc Output cÇn t×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.
Slide 8: B7: KÕt thóc. B1: B¾t ®Çu; B2: NhËp a, b, c; B3: TÝnh = b2 – 4ac; B4: NÕu < 0 => PT v« nghiÖm => B7; B5: NÕu = 0 => PT cã nghiÖm kÐp x = -b/2a => B7; B6: NÕu > 0 => PT cã hai nghiÖm x1, x2 = (-b )/2a => B7; ThuËt to¸n gi¶i ph¬ng tr×nh bËc hai (a 0). C¸ch 1: LiÖt kª c¸c bíc
Slide 9: 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. B§ ® S C¸ch 2: VÏ s¬ ®å khèi
Slide 10: ® s S¬ ®å thuËt to¸n gi¶i ph¬ng tr×nh bËc hai 2 B1 B2 B3 B4 B5 B6 s ® B7
Slide 11: a,b,c= 1 3 5 D = 3*3 - 4*5 = - 11 -11 < 0 PT v« nghiÖm KT BD S PT cã 2 nghiÖm x1, x2 = (-b )/2a § S D = b*b - 4*a*c nhËp vµo a,b,c < 0 M« pháng thuËt to¸n gi¶i ph¬ng tr×nh bËc hai Bé TEST 1:
Slide 12: a,b,c= 1 2 1 D = 2*2 - 4*1*1 = 0 PT v« nghiÖm PT cã nghiÖm x=-b/2a KT BD S PT cã 2 nghiÖm x1, x2 = (-b )/2a § S D = b*b - 4*a*c nhËp vµo a,b,c < 0 M« pháng thuËt to¸n gi¶i ph¬ng tr×nh bËc hai Bé TEST 2: § = 0 PT cã nghiÖm kÐp x=-1
Slide 13: a,b,c= 1 -5 6 D = 25 - 24 = 1 PT v« nghiÖm PT cã nghiÖm x=-b/2a KT BD S PT cã 2 nghiÖm x1, x2 = (-b )/2a § S D = b*b - 4*a*c nhËp vµo a,b,c < 0 M« pháng thuËt to¸n gi¶i ph¬ng tr×nh bËc hai Bé TEST 3: § = 0 PT cã nghiÖm x1 = 3
x2 = 2
Slide 14: + Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác + Tính chính xác: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để thực hiện tiếp theo. + Tính đúng đắn: Sau khi thuật toán kết thúc ta phải nhận được output. Tính chất:
Slide 15: ThuËt to¸n t×m max 3 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 .
Slide 16: Qu¶ nµy lín nhÊt Qu¶ nµy míi lín nhÊt å! Qu¶ nµy lín h¬n T×m ra qu¶ lín nhÊt råi! Cïng t×m thuËt to¸n
Slide 17: ThuËt to¸n t×m sè lín nhÊt trong mét d·y sè nguyªn X¸c ®Þnh bµi to¸n:INPUT: Sè nguyªn d¬ng N vµ d·y N sè nguyªn a1, a2, …, aN (ai víi i: 1N). OUTPUT: Sè lín nhÊt (Max) cña d·y sè.
Slide 18: ý 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.
Slide 19: C¸ch 1: LiÖt kª c¸c bíc B1: NhËp N vµ d·y a1,…, aN; B2: Max a1; i 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 ai > Max th× Max ai; Bíc 4.2: i i+1 råi quay l¹i B3.
Slide 20: § S § S B1: NhËp N vµ d·y a1,…,aN; B2: Max a1; i 2; B3: NÕu i > N th× ®a ra gi¸ trÞ Max råi kÕt thóc; B4 : 4.1: NÕu ai > Max th× Max ai; 4.2: i i + 1 råi quay l¹i B3. C¸ch 2: S¬ ®å khèi
Slide 21: § S § S NhËp N vµ d·y a1,…,aN Max a1 ; i 2 I > N ? ai> Max ? Max ai i i+1 §a ra Max råi kÕt thóc Max i A 7 7 5 5 5 5 4 3 2 6 7 4 1 5 N=5 ; A [ 5 1 4 7 6 ] Max 5 ; i 2 2 > 5 ? 1> 5 ? i 2+1 3 > 5 ? 4> 5 ? i 3+1 4 > 5 ? 7 > 5 ? Max 7 4 i 4+1 5 > 5 ? 7 > 7 ? i 5+1 6 > 5 ? Sè lín nhÊt cña d·y lµ 7 M« pháng
thuËt to¸n Víi i = 2 Víi i = 3 Víi i = 4 Víi i = 5
Slide 22: § S § S NhËp N vµ d·y a1,…,aN Max a1 ; i 2 I > N ? ai> Max ? Max ai i i+1 §a ra Max råi kÕt thóc Max i A 7 7 5 5 5 5 4 3 2 6 7 4 1 5 N=5 ; A [ 5 1 4 7 6 ] Max 5 ; i 2 2 > 5 ? 1> 5 ? i 2+1 3 > 5 ? 4> 5 ? i 3+1 4 > 5 ? 7 > 5 ? Max 7 4 i 4+1 5 > 5 ? 7 > 7 ? i 5+1 6 > 5 ? Sè lín nhÊt cña d·y lµ 7
Slide 23: Cảm ơn các em đã theo dõi !