Bai 4 Bai toan va thuat toan

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: 1N). 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 !