Đề tài Phát triển tư duy thuật giải cho học sinh thông qua dạy học các cấu trúc điều khiển và các kiểu dữ liệu có cấu trúc Tin học lớp 11 THPT

c sinh suy nghÜ, vËn dông c¸c thao t¸c cña t­ duy thuËt gi¶i tøc lµ c¸c qu¸ tr×nh ph©n t¸ch ho¹t ®éng (kh¶ n¨ng K2). Cã tõng b­íc luyÖn tËp, häc sinh míi quen víi lèi suy nghÜ cÇn thiÕt. NÕu kh«ng, ta chØ kªu gäi chung chung c¸c em suy nghÜ mµ hä ch¼ng biÕt b¾t ®Çu suy nghÜ tõ ®©u vµ suy nghÜ nh­ thÕ nµo. Ph©n t¸ch lµ dïng trÝ ãc chia c¸i toµn thÓ ra tõng phÇn, hoÆc t¸ch b¹ch tõng thao t¸c, tõng khÝa c¹nh riªng biÖt. Trong gi¶ng d¹y Tin häc, kh©u ph©n t¸ch ho¹t ®éng lµ rÊt cÇn thiÕt. Thao t¸c nµy ®Æt biÖt quan träng ®èi víi viÖc gi¶i c¸c bµi tËp Tin häc. V× th«ng th­êng häc sinh chØ quen sö dông m¸y mãc c«ng thøc mµ kh«ng chÞu t­ duy, suy nghÜ, kh«ng cã thãi quen ph©n t¸ch ho¹t ®éng, do ®ã kh«ng ph¸t triÓn ®­îc t­ duy cña m×nh. H¬n n÷a, ph©n t¸ch ho¹t ®éng vµ thùc hiÖn c¸c ho¹t ®éng thµnh phÇn lµ mét yÕu tè rÊt cÇn thiÕt ®èi víi mét ng­êi lËp tr×nh, ph¸t triÓn ®­îc kh¶ n¨ng nµy cho häc sinh kh«ng chØ cã ý nghÜa gióp häc sinh gi¶i quyÕt nh÷ng bµi to¸n ®¬n gi¶n s¬ cÊp trong ch­¬ng tr×nh THPT mµ nã cßn lµ hµnh trang gióp häc sinh tiÕn xa h¬n trong lÜnh vùc lËp tr×nh. Tõ bµi to¸n cÇn gi¶i quyÕt, häc sinh ph¶i x¸c ®Þnh ®­îc thuËt gi¶i, gi¸o viªn cã thÓ chia bµi to¸n lín thµnh c¸c bµi to¸n nhá hoÆc “níi láng”, “®Æc biÖt” mét vµi ®iÒu kiÖn nh»m ®­a bµi to¸n ®ã vÒ c¸c bµi to¸n mµ häc sinh ®· biÕt thuËt gi¶i (quy l¹ vÒ quen). Ch¼ng h¹n nh­ x©y dùng thuËt gi¶i tÝnh diÖn tÝch tø gi¸c låi khi biÕt täa ®é c¸c ®Ønh cña tø gi¸c (bµi to¸n T). Thao t¸c ph©n t¸ch: chia bµi to¸n T thµnh c¸c bµi to¸n nhá h¬n T1, T2: T1: TÝnh ®é dµi ®o¹n th¼ng khi biÕt täa ®é 2 ®Ønh. T2: TÝnh diÖn tÝch tø gi¸c khi biÕt täa ®é 4 ®Ønh. Bµi to¸n T2 l¹i ®­îc chia thµnh 2 bµi to¸n nhá h¬n: T21: TÝnh diÖn tÝch tam gi¸c khi biÕt täa ®é 3 ®Ønh. T22: TÝnh diÖn tÝch tø gi¸c khi biÕt täa ®é 4 ®Ønh. Nh­ vËy, bµi to¸n T ®· ®­îc chia thµnh c¸c bµi to¸n nhá h¬n, ®©y lµ nh÷ng bµi to¸n häc sinh ®· biÕt thuËt gi¶i nªn cã thÓ vËn dông ®Ó gi¶i quyÕt ®­îc bµi to¸n ®Æt ra. Trong qu¸ tr×nh ph©n t¸ch ho¹t ®éng, môc ®Ých lín nhÊt lµ gi¸o viªn ph¶i kh¬i dËy vai trß tÝch cùc, chñ ®éng cña häc sinh. Gi¸o viªn kh«ng chØ h­íng cho häc sinh ph¸t hiÖn vµ nªu ra vÊn ®Ò mµ trong mét chõng mùc nµo ®ã cßn khuyÕn khÝch häc sinh tham gia gi¶i quyÕt vÊn ®Ò. Ph©n t¸ch ®­îc mét ho¹t ®éng thµnh nh÷ng ho¹t ®éng thµnh phÇn lµ biÕt ®­îc c¸ch tiÕn hµnh ho¹t ®éng toµn bé, nhê ®ã cã thÓ võa quan t©m rÌn luyÖn cho häc sinh ho¹t ®éng toµn bé võa chó ý cho hä luyÖn tËp t¸ch riªng nh÷ng ho¹t ®éng thµnh phÇn khã hoÆc quan träng khi cÇn thiÕt. VÝ dô 1: Khi d¹y cho häc sinh vÒ c©u lÖnh lÆp víi ®iÒu kiÖn cho tr­íc FOR…DO, ta cho häc sinh ph©n t¸ch ra thµnh nh÷ng ho¹t ®éng: H§1: Ho¹t ®éng kiÓm tra ®iÒu kiÖn H§2: Ho¹t ®éng thùc hiÖn c©u lÖnh sau Do khi ®iÒu kiÖn ®óng H§3: Ho¹t ®éng quay l¹i kiÓm tra ®iÒu kiÖn H§4: Ho¹t ®éng ra khái vßng lÆp khi ®iÒu kiÖn sai. VÝ dô 2: D¹y c©u lÖnh FOR d¹ng tiÕn: FOR := TO DO Dùa vµo sù ph©n t¸ch ë vÝ dô 1, gi¸o viªn yªu cÇu häc sinh ph©n t¸ch ho¹t ®éng cña c©u lÖnh nµy thµnh nh÷ng ho¹t ®éng thµnh phÇn nh­ sau: §Çu tiªn m¸y kiÓm tra ®iÒu kiÖn biÓu thøc 1 kh«ng lín h¬n biÓu thøc 2. NÕu ®iÒu kiÖn nµy ®óng th× m¸y ghi nhí gi¸ trÞ cña biÓu thøc 2. TiÕp ®ã m¸y thùc hiÖn liªn tiÕp c¸c ho¹t ®éng sau ®©y: 1. G¸n gi¸ trÞ cña biÓu thøc 1 cho biÕn ®iÒu khiÓn 2. Thùc hiÖn c©u lÖnh sau DO 3. BiÕn ®iÒu khiÓn chu tr×nh nhËn gi¸ trÞ tiÕp theo gi¸ trÞ hiÖn t¹i (tøc lµ gi¸ trÞ cña nã sau khi thùc hiÖn c©u lÖnh sau DO). 4. Quay l¹i kiÓm tra ®iÒu kiÖn ra khái vßng lÆp (®iÒu kiÖn lµ biÕn ®iÒu khiÓn = gi¸ trÞ tiÕp theo cña gi¸ trÞ cuèi, nÕu ®iÒu kiÖn nµy sai m¸y quay trë l¹i thùc hiÖn c¸c ho¹t ®éng tõ 2 -> 4). 5. Qu¸ tr×nh lÆp chØ kÕt thóc khi m¸y quay l¹i kiÓm tra ®iÒu kiÖn ra khái vßng lÆp mµ ®iÒu kiÖn nµy ®óng. Gi¸o viªn cã thÓ cho häc sinh thùc hiÖn ho¹t ®éng nhËn d¹ng ®Ó ®o¸n tr­íc ch­¬ng tr×nh sau ®©y in lªn mµn h×nh nh÷ng sè nh­ thÕ nµo? Program Chuong_trinh; Uses Crt; Var a: array [1..5,1..6] of Integer; i, j : Byte; Begin For i:=1 to 5 do For j:= 1 to 6 do a[i,j] := i*j; For i:=1 to 5 do Begin For j:= 1 to 6 do write( a[i,j] : 5); Writeln; End; Readln; End. NÕu häc sinh gÆp khã kh¨n khi x©y dùng thuËt gi¶i ®Ó gi¶i mét bµi to¸n nµo ®ã, gi¸o viªn cã thÓ t¸ch riªng 1 ho¹t ®éng nµo ®ã ®Ó råi h­íng dÉn häc sinh thùc hiÖn mét ho¹t ®éng nhËn d¹ng vµ xÐt t­¬ng tù xem t×nh huèng nµo tr­íc ®©y ®· gÆp gÇn gièng hoÆc t­¬ng thÝch víi ho¹t ®éng nµy? Vµ cho häc sinh tËp luyÖn nh÷ng ho¹t ®éng ¨n khíp víi ho¹t ®éng nµy. 3. T­êng minh hãa thuËt gi¶i Trong qu¸ tr×nh nµy, tr­íc tiªn tõ c¸c bµo to¸n cô thÓ gi¸o viªn x¸c ®Þnh hai thµnh phÇn: §Çu vµo (Input) vµ ®Çu ra (Output), sau ®ã ph¸t biÓu thµnh bµi to¸n tæng qu¸t trong ®ã nh÷ng tham biÕn ®Çu vµo, ®Çu ra cã thÓ xem lµ c¸c tham biÕn h×nh thøc vµ khi cã c¸c tham biÕn ®ã víi c¸c gi¸ trÞ x¸c ®Þnh, ta sÏ nhËn l¹i ®­îc c¸c bµi to¸n mµ häc sinh ®· gi¶i quyÕt ®­îc. VÝ dô: Cho d·y gåm N sè nguyªn (1<N 50) A1, A2,…,AN trong ®ã cã Ýt nhÊt hai sè 0. H·y lËp tr×nh: - NhËp tõ bµn phÝm sè nguyªn N vµ d·y A1, A2,…, AN. -TÝnh tæng c¸c sè Ai n»m gi÷a sè 0 ®Çu tiªn vµ sè 0 cuèi cïng råi ®­a kÕt qu¶ ra mµn h×nh. NÕu hai sè 0 n»m c¹nh nhau th× kÕt qu¶ ®­a ra sÏ lµ 0. §èi víi bµi to¸n nµy, ta sÏ x¸c ®Þnh ®­îc: + Th«ng tin vµo (Input): Sè nguyªn N (1<N 50). D·y sè nguyªn A1, A2,…, AN. + Th«ng tin ra (Output): Tæng S cña c¸c sè Ai trong d·y víi ®iÒu kiÖn: - C¸c sè Ai nµy n»m gi÷a sè 0 ®Çu tiªn vµ sè 0 cuèi cïng cña d·y. - NÕu hai sè 0 nµy n»m c¹nh nhau th× tæng S=0. X¸c ®Þnh ®­îc th«ng tin vµo vµ th«ng tin ra cã nghÜa lµ häc sinh ®· x¸c ®Þnh ®­îc nh÷ng d÷ kiÖn mµ m×nh cã vµ c«ng viÖc m×nh cÇn lµm. Tõ ®ã cã thÓ ®­a ra thuËt gi¶i ®Ó gi¶i quyÕt bµi to¸n nh­ sau: B1: §Çu tiªn ta sÏ t×m sè 0 ®Çu tiªn tõ tr¸i sang ph¶i, ®¸nh dÊu vÞ trÝ t×m ®­îc. B2: Sau ®ã, t×m sè 0 thø hai lµ sè 0 ®Çu tiªn tõ ph¶i sang tr¸i, ®¸nh dÊu vÞ trÝ võa t×m ®­îc. B3: So s¸nh 2 vÞ trÝ ®¸nh dÊu: NÕu b»ng nhau th× th«ng b¸o S=0 ng­îc l¹i th× tÝnh tæng c¸c gi¸ trÞ Ai trong kho¶ng ®¸nh dÊu. B4: Th«ng b¸o kÕt qu¶. C«ng viÖc quan träng cña lËp tr×nh lµ x©y dùng thuËt gi¶i, ®Ó tõ ®ã m· hãa thµnh ch­¬ng tr×nh theo mét ng«n ng÷ lËp tr×nh cô thÓ nµo ®ã, ®Ó qu¸n triÖt ph­¬ng diÖn nµy, ®øng tr­íc mét t×nh huèng c«ng viÖc hay mét bµi to¸n ta yªu cÇu häc sinh x©y dùng thuËt gi¶i, cã nghÜa lµ x©y dùng d·y c¸c t¸c ®éng ®Ó cho m¸y tÝnh cã thÓ thùc hiÖn trong mét kho¶ng thêi gian h÷u h¹n, ®Ó ®¹t ®Õn mét kÕt qu¶ x¸c ®Þnh gäi lµ ®iÒu kiÖn ra, xuÊt ph¸t tõ mét t×nh huèng cho tr­íc gäi lµ ®iÒu kiÖn vµo, nÕu cã thÓ ®­îc th× cho häc sinh viÕt nhiÒu thuËt gi¶i cïng gi¶i quyÕt mét bµi to¸n, sau ®ã chän xem trong sè c¸c thuËt gi¶i nµo tèt h¬n vÒ mét yªu cÇu nµo ®ã. ë líp 10 häc sinh ®· ®­îc häc c¸c b­íc ®Ó gi¶i mét bµi to¸n trªn m¸y tÝnh bao gåm: B­íc 1: X¸c ®Þnh bµi to¸n (Input, Output) B­íc 2: Lùa chän hoÆc thiÕt kÕ thuËt to¸n. B­íc 3: ViÕt ch­¬ng tr×nh B­íc 4: HiÖu chØnh B­íc 5: ViÕt tµi liÖu. Dùa vµo ®ã häc sinh sÏ tõng b­íc gi¶i quyÕt ®­îc bµi to¸n ®Æt ra, tuy nhiªn trong c¸c b­íc ®ã th× “lùa chän hoÆc thiÕt kÕ thuËt to¸n” lµ b­íc quan träng nhÊt, yªu cÇu häc sinh ph¶i t­ duy, suy nghÜ ®Ó x©y dùng thuËt gi¶i cho bµi to¸n. Mçi thuËt gi¶i chØ gi¶i quyÕt mét bµi to¸n nµo ®ã, nh­ng cã thÓ cã nhiÒu thuËt gi¶i kh¸c nhau cïng gi¶i mét bµi to¸n. CÇn thiÕt kÕ hoÆc lùa chän mét thuËt gi¶i phï hîp ®· cã ®Ó gi¶i bµi to¸n cho tr­íc. Sau khi lùa chän hoÆc thiÕt kÕ thuËt gi¶i, häc sinh ph¶i biÓu diÔn (thÓ hiÖn) thuËt gi¶i, cã nhiÒu ph­¬ng ph¸p ®Ó diÔn t¶ thuËt gi¶i: + BiÓu diÔn b»ng s¬ ®å khèi: Tr­íc khi viÕt ch­¬ng tr×nh cÇn ph©n tÝch mét c¸ch cÆn kÏ c¸c t×nh huèng cã thÓ x¶y ra trong qu¸ tr×nh tÝnh to¸n. §Ó m« t¶ qu¸ tr×nh tÝnh to¸n mét c¸ch cã hÖ thèng vµ râ rµng ng­êi ta th­êng thÓ hiÖn thuËt gi¶i b»ng l­u ®å, ®ã lµ sù biÓu diÔn b»ng ®å thÞ cña toµn bé qu¸ tr×nh tÝnh to¸n. ViÖc vÏ l­u ®å kh«ng nh÷ng gióp cho qu¸ tr×nh so¹n th¶o ch­¬ng tr×nh dÔ dµng mµ cßn gióp cho häc sinh ph¸t hiÖn ®­îc nh÷ng sai sãt trong ch­¬ng tr×nh. Trong c¸c bµi to¸n ®¬n gi¶n cã thÓ bá qua giai ®o¹n nµy, nh­ng trong c¸c bµi to¸n tÝnh to¸n nhÊt thiÕt ph¶i lËp l­u ®å tÝnh to¸n. VÝ dô: T×m ­íc chung lín nhÊt (UCLN) cña hai sè nguyªn d­¬ng M vµ N. NhËp M vµ N M = N ? M > N ? N ß N - M M ß M - N §­a ra M; KÕt thóc Sai Sai §óng §óng + BiÓu diÔn b»ng ng«n ng÷ pháng tr×nh: ViÖc m« t¶ thuËt gi¶i b»ng s¬ ®å khèi ®«i khi rÊt cång kÒnh vµ cã thÓ cã nh÷ng bµi to¸n kh«ng thÓ biÓu diÔn ®­îc b»ng s¬ ®å khèi. Do ®ã, ng­êi ta dïng ng«n ng÷ tù nhiªn ®Ó m« t¶ thuËt gi¶i. ThuËt gi¶i ®­îc m« t¶ b»ng ng«n ng÷ tù nhiªn sÏ dÔ hiÓu h¬n gän h¬n vµ cã thÓ chuyÓn sang mét ng«n ng÷ lËp tr×nh cô thÓ dÔ dµng h¬n. Khung thuËt gi¶i b»ng ng«n ng÷ pháng tr×nh ®­îc x©y dùng nh­ sau: THUATGIAI Ten_thuat_giai; HANG Khai bao hang; BIEN Khai bao cac bien; THUTUC Ten_thu_tuc (ds cac tham so hinh thuc); BATDAU ; KETTHUC; HAM Ten_ham (ds cac tham so hinh thuc) : Kieu ham; BATDAU ; KETTHUC; BATDAU {bat dau cua thuat giai} ; KETTHUC. {Ket thuc thuat giai} + Ngoµi ra cßn cã nhiÒu c¸ch kh¸c ®Ó biÓu diÔn thuËt gi¶i, tuy nhiªn ë ch­¬ng tr×nh Tin häc 10 c¸c em ®­îc häc hai ph­¬ng ph¸p biÓu diÔn thuËt gi¶i b»ng s¬ ®å khèi vµ liÖt kª c¸c b­íc. LiÖt kª c¸c b­íc nghÜa lµ häc sinh sÏ x¸c ®Þnh tõng b­íc ®Ó gi¶i quyÕt bµi to¸n. VÝ dô: T×m ­íc chung lín nhÊt (UCLN) cña hai sè nguyªn d­¬ng M vµ N. DiÔn t¶ thuËt gi¶i b»ng c¸ch liÖt kª: B­íc 1: NhËp M vµ N; B­íc 2: NÕu M = N th× lÊy gi¸ trÞ chung nµy lµm UCLN råi chuyÓn ®Õn b­íc 5; B­íc 3: NÕu M > N th× M ß M – N råi quay l¹i b­íc 2; B­íc 4: N ß N – M råi quay l¹i b­íc 2; B­íc 5: §­a ra kÕt qu¶ UCLN råi kÕt thóc. 4. Kh¸i qu¸t ho¸ ho¹t ®éng ViÖc d¹y häc lËp tr×nh cho häc sinh kh«ng chØ dõng l¹i ë viÖc häc sinh n¾m ®­îc c¸c kiÕn thøc vÒ lËp tr×nh vµ cã thÓ lËp ®­îc ch­¬ng tr×nh ®Ó gi¶i quyÕt c¸c bµi to¸n ®Æt ra mµ cßn ph¶i h­íng cho häc sinh ®Õn c¸c thao t¸c nh­: * Tõ mét bµi to¸n cô thÓ cÇn x¸c ®Þnh thuËt gi¶i, häc sinh ph¶i x¸c ®Þnh ®­îc nh÷ng bµi to¸n cïng lo¹i, kh¸i qu¸t ho¸ thµnh bµi to¸n tæng qu¸t vµ x©y dùng thuËt gi¶i cho bµi to¸n ®ã. * Khi ®· cã thuËt gi¶i ®Ó gi¶i quyÕt bµi to¸n tæng qu¸t nµo ®ã, häc sinh cÇn ph¶i chuyÓn ®­êng lèi chung ®ã vµo c¸c bµi to¸n cô thÓ. C«ng viÖc nµy tuy ®¬n gi¶n nh­ng nÕu kh«ng luyÖn tËp th× häc sinh còng kh«ng thÓ tr¸nh khái sù lóng tóng tr­íc mét bµi to¸n cÇn gi¶i quyÕt v×: Khi gÆp mét bµi to¸n häc sinh sÏ kh«ng x¸c ®Þnh ®­îc bµi to¸n nµy thuéc lo¹i bµi to¸n tæng qu¸t nµo vµ ®­êng lèi, ph­¬ng ph¸p gi¶i quyÕt bµi to¸n tæng qu¸t ®ã ra sao? §èi víi thao t¸c thø nhÊt, ®Ó lµm ®­îc ®iÒu nµy tr­íc hÕt ®ßi hái tr×nh ®é hiÓu biÕt c¸c d¹ng bµi to¸n ®Ó ®ñ kh¶ n¨ng h×nh thµnh ®­îc c¸c bµi to¸n tæng qu¸t vµ ph­¬ng ph¸p gi¶i chóng. §Ó luyÖn tËp kh¶ n¨ng kh¸i qu¸t ho¸ ho¹t ®éng, häc sinh cÇn ph¶i ph©n tÝch trong c¸c bµi to¸n ®· cho c¸c ®Æc ®iÓm c¬ b¶n, chung cho mäi bµi to¸n vµ c¸c ®Æc ®iÓm phô, riªng cho tõng bµi to¸n. VÝ dô 1: Tõ bµi to¸n s¾p xÕp ba sè nguyªn a, b, c theo thø tù t¨ng dÇn. Gi¸o viªn nªn ®Þnh h­íng cho häc sinh kh¸i qu¸t hãa lªn thµnh bµi to¸n s¾p xÕp m¶ng mét chiÒu gåm N sè nguyªn A1, A2,…, AN. Víi bµi to¸n s¾p xÕp ba sè nguyªn a, b, c theo thø tù t¨ng dÇn häc sinh cã thÓ ®­a ra thuËt gi¶i nh­ sau: THUATGIAI Sap_xep; BIEN a, b, c : Nguyªn; BATDAU Vµo a, b, c; NÕu b < a th× tr¸o ®æi gi¸ trÞ gi÷a hai biÕn a vµ b; NÕu c < b th× tr¸o ®æi gi¸ trÞ gi÷a hai biÕn c vµ b; NÕu b < a th× tr¸o ®æi gi¸ trÞ gi÷a hai biÕn a vµ b; In 3 sè a, b, c; KETTHUC. Tõ ®ã häc sinh cã thÓ kh¸i qu¸t, ph¸t triÓn x©y dùng thuËt gi¶i bµi tãan s¾p xÕp m¶ng mét chiÒu t¨ng dÇn nh­ sau: B­íc 1: NhËp N, c¸c sè h¹ng A1, A2,…, AN; B­íc 2: M ß N; B­íc 3: NÕu M < 2 th× ®­a ra d·y A ®· ®­îc s¾p xÕp råi kÕt thóc; B­íc 4: M ß M – 1, i ß 0; B­íc 5: i ß i + 1; B­íc 6: NÕu i > M th× quay l¹i b­íc 3; B­íc 7: NÕu Ai > Ai + 1 th× tr¸o ®æi Ai víi Ai + 1 cho nhau; B­íc 8: Quay l¹i b­íc 5. Bµi to¸n s¾p xÕp lµ bµi to¸n ®iÓn h×nh trong c¸c bµi to¸n liªn quan ®Õn m¶ng mét chiÒu, cã nhiÒu thuËt gi¶i ®Ó gi¶i quyÕt bµi to¸n nµy. Do ®ã, khi d¹y häc cho häc sinh kiÕn thøc vÒ m¶ng mét chiÒu, gi¸o viªn nªn cã nh÷ng ®Þnh h­íng ®Ó häc sinh cã thÓ x©y dùng ®­îc c¸c thuËt gi¶i kh¸c nhau cïng gi¶i quyÕt mét bµi to¸n. 5. Chän thuËt gi¶i tèi ­u ë líp 10 häc sinh ®· ®­îc lµm quen víi kh¸i niÖm thuËt gi¶i tèi ­u, ®ã lµ thuËt gi¶i ®¸p øng ®­îc c¸c tiªu chÝ sau: Dung l­îng bé nhí chiÕm Ýt. Sè c¸c phÐp tÝnh cÇn thùc hiÖn Ýt. Thêi gian cÇn thiÕt ®Ó ch¹y ng¾n. DÔ hiÓu ®èi víi con ng­êi. DÔ cµi ®Æt trªn m¸y. ViÖc rÌn luyÖn, ph¸t triÓn t­ duy thuËt gi¶i cho ®èi t­îng häc sinh ®¹i trµ th× viÖc thùc hiÖn lùa chän thuËt gi¶i tèi ­u th­êng gÆp nhiÒu khã kh¨n mµ lý do chñ yÕu cã thÓ kÓ ®Õn lµ: - Häc sinh kh«ng ®­îc häc mét c¸ch t­êng minh vÒ kh¸i niÖm “§é phøc t¹p cña mét thuËt gi¶i”. - ViÖc ®¸nh gi¸ ®é phøc t¹p cña mét thuËt gi¶i vèn lµ mét bµi to¸n khã… Tuy nhiªn, gi¸o viªn cã thÓ tõng b­íc h×nh thµnh, rÌn luyÖn cho häc sinh kh¶ n¨ng ®¸nh gi¸ ®é phøc t¹p cña thuËt gi¶i ë møc ®é ®¬n gi¶n vµ dùa vµo c¸c tiªu chÝ ë trªn d­íi c¸c gãc ®é sau: + §é phøc t¹p vÒ thêi gian tÝnh to¸n cña thuËt gi¶i (sè phÐp tÝnh m¸y tÝnh ph¶i thùc hiÖn). + §é phøc t¹p cña dung l­îng nhí dïng cho thuËt gi¶i. + §é phøc t¹p khi cµi ®Æt thuËt gi¶i trªn m¸y. Cã thÓ lÊy vÝ dô nh­ sau: Bµi to¸n s¾p xÕp Cho d·y A gåm N sè nguyªn a1, a2, …, aN. CÇn s¾p xÕp c¸c sè h¹ng ®Ó d·y A trë thµnh d·y kh«ng gi¶m (tøc lµ sè h¹ng ®øng tr­íc kh«ng lín h¬n sè h¹ng ®øng sau). §èi víi bµi to¸n nµy, cã nhiÒu thuËt gi¶i ®Ó gi¶i quyÕt. Tuy nhiªn ë ®©y xin giíi thiÖu hai thuËt gi¶i ®iÓn h×nh nh­ sau: ThuËt gi¶i s¾p xÕp b»ng tr¸o ®æi (Exchange Sort) ý 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 chç chóng cho nhau. ViÖc ®ã ®­îc lÆp l¹i, cho ®Õn khi kh«ng cã sù ®æi chç nµo n÷a. ThuËt gi¶i: BiÓu diÔn b»ng c¸ch liÖt kª B­íc 1: NhËp N, c¸c sè h¹ng a1, a2, …, aN; B­íc 2: M ß N; B­íc 3: NÕu M < 2 th× ®­a ra d·y A ®· ®­îc s¾p xÕp råi kÕt thóc; B­íc 4: M ß M – 1, i ß 0; B­íc 5: i ß i + 1; B­íc 6: NÕu i > M th× quay l¹i b­íc 3; B­íc 7: NÕu ai > ai + 1 th× tr¸o ®æi ai vµ ai + 1 cho nhau; B­íc 8: Quay l¹i b­íc 5; ThuËt gi¶i s¾p xÕp nhanh (QuickSort) ý t­ëng: Ta dïng ph­¬ng ph¸p ph©n vïng ®Ó xö lý. Néi dung chÝnh lµ chän phÇn tö X ë gi÷a cña d·y lµm chuÈn ®Ó so s¸nh, tõ ®ã ph©n ho¹ch d·y nµy thµnh 3 d·y con liªn tiÕp nh­ sau: + D·y con thø nhÊt gåm c¸c phÇn tö nhá h¬n X + D·y con thø hai gåm c¸c phÇn tö b»ng X + D·y con thø ba gåm c¸c phÇn tö lín h¬n X Sau ®ã l¹i ¸p dông thuËt gi¶i ph©n ho¹ch nµy cho d·y con thø nhÊt vµ d·y con thø 3, nÕu c¸c d·y con nµy cã nhiÒu h¬n mét phÇn tö (®Ö quy). Cô thÓ lµ xÐt mét ®o¹n cña d·y tõ thµnh phÇn thø L ®Õn thµnh phÇn thø R ta thùc hiÖn c¸c b­íc nh­ sau: + LÊy gi¸ trÞ cña thµnh phÇn thø (L + R) div 2 g¸n vµo biÕn X + Cho i ban ®Çu lµ L + Cho j ban ®Çu lµ R + LÆp l¹i: * Chõng nµo cßn A[i] < X th× t¨ng i. * Chõng nµo cßn A[j] > X th× gi¶m j * NÕu i < = j th×: - Ho¸n vÞ A[i] cho A[j] - T¨ng i - Gi¶m j Cho ®Õn khi i > j + S¾p xÕp ®o¹n tõ A[L] ®Õn A[j] + S¾p xÕp ®o¹n tõ A[i] ®Õn A[R] Tõ ý t­ëng vÒ thuËt gi¶i nh­ trªn häc sinh sÏ x©y dùng ®­îc ch­¬ng tr×nh. So s¸nh gi÷a hai thuËt gi¶i trªn häc sinh sÏ chän ra ®­îc thuËt gi¶i nµo tèi ­u h¬n. Do ®ã, ®Ó chän thuËt gi¶i tèi ­u, trong bµi gi¶ng gi¸o viªn nªn cã nh÷ng t×nh huèng t¹o cho häc sinh c¸c mèi liªn hÖ xu«i, ng­îc vµ c¸c biÖn ph¸p nh»m ph¸t huy tÝnh n¨ng ®éng, sù s¸ng t¹o, sù say mª t×m tßi vµ høng thó häc tËp lËp tr×nh cña häc sinh. Trong qu¸ tr×nh gi¶ng d¹y gi¸o viªn kh«ng chØ ®¬n thuÇn lµ ®­a ra c¸c bµi to¸n khã, mµ gi¸o viªn ph¶i chó träng ®Õn viÖc gióp häc sinh t×m tßi, so s¸nh ®Ó ®­a ra thuËt gi¶i tèi ­u, phï hîp víi néi dung cña bµi to¸n. 2.4 X©y dùng hÖ thèng c¸c bµi tËp theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh * D¹ng 1: Bµi tËp lý thuyÕt vÒ c¸c kh¸i niÖm, c©u lÖnh, cÊu tróc, c¸ch khai b¸o ®· ®­îc häc. Lµ nh÷ng bµi tËp chØ dùa vµo kiÕn thøc lý thuyÕt, lo¹i bµi tËp nµy cã thÓ ph©n hãa thµnh ba møc nh­ sau: - T¸i hiÖn kiÕn thøc lý thuyÕt. - T¸i hiÖn kiÕn thøc vµ gi¶i thÝch. - VËn dông s¸ng t¹o vµ suy luËn linh häat kiÕn thøc ë ®iÒu kiÖn míi. VÝ dô: XÐt c¸c cÊu tróc ®iÒu khiÓn, thiÕt kÕ bµi tËp theo kiÓu ph©n hãa: + Møc ®é 1: Nªu ho¹t ®éng cña c¸c c©u lÖnh ®iÒu khiÓn ®· häc. Bµi tËp 1: Nªu ho¹t ®éng cña c©u lÖnh lÆp víi sè lÇn ch­a biÕt tr­íc While – do. + Møc ®é 2: T×m chç sai trong c¸c c©u lÖnh vµ gi¶i thÝch. + Møc ®é 3: Dùa vµo s¬ ®å khèi h·y t×m ra c©u lÖnh ®iÒu khiÓn t­¬ng øng. * D¹ng 2: X©y dùng thuËt gi¶i, m· hãa ch­¬ng tr×nh Lµ nh÷ng bµi tËp lËp tr×nh yªu cÇu häc sinh ph¶i n¾m v÷ng kiÕn thøc trong tõng phÇn, kiÕn thøc cña c¶ ch­¬ng ®· häc. Lo¹i bµi tËp nµy còng cã thÓ ph©n thµnh 3 møc: Møc ®é 1: Dù ®o¸n kÕt qu¶ cña c¸c ch­¬ng tr×nh ®· cã s½n Bµi tËp 2: XÐt ch­¬ng tr×nh: Program VD; Var a: array [1..100] of Integer; i, n, t : Integer; Begin Write(‘ N = ’); Readln(N); For i : = 1 to n do readln(a[i]); For i : = 1 to n div 2 do Begin t : = a[i]; a[i] := a[n – i + 1]; a[n – i + 1] : = t; end; for i : = 1 to n do write( a[i] : 5); Readln; End. §iÒu kh¼ng ®Þnh nµo sau ®©y lµ ®óng? Ch­¬ng tr×nh trªn ®¶o ng­îc vÞ trÝ cña c¸c phÇn tö trong m¶ng a (theo kÝch th­íc thùc tÕ ®­îc nhËp); Ch­¬ng tr×nh trªn ghi mét nöa sè phÇn tö ë cuèi lªn c¸c vÞ trÝ ®Çu tiªn; Ch­¬ng tr×nh trªn s¾p xÕp c¸c phÇn tö cña a theo thø tù gi¶m dÇn; C¶ a, b vµ c ®Òu sai. Bµi tËp 3: Ch­¬ng tr×nh d­íi ®©y thùc hiÖn c«ng viÖc g×? Program CT; Var x1, y1, x2, y2, x3, y3, u, v : Integer; Begin Write( ‘ Nhap toa do diem A :’); readln (x1, y1); Write( ‘ Nhap toa do diem B :’); readln (x2, y2); Write( ‘ Nhap toa do diem C :’); readln (x3, y3); If (x1 – x3)*(x1 – x3) + (y1 – y3)*(y1 – y3) > (x2 – x3)*(x2 – x3) + (y2 – y3) * (y2 – y3) then Begin u : = x2; v : = y2; end else begin u : = x1; v : = y1; end; writeln( ‘ X = ’, u, ‘ Y = ’, v); End. Møc ®é 2: M· hãa bµi to¸n víi c¸c thuËt gi¶i ®· cã. Bµi tËp 4: Cho thuËt gi¶i bµi to¸n kiÓm tra tÝnh nguyªn tè cña mét sè nguyªn d­¬ng N nh­ sau: B­íc 1: NhËp sè nguyªn d­¬ng N; B­íc 2: NÕu N = 1 th× th«ng b¸o N kh«ng nguyªn tè råi kÕt thóc; B­íc 3: NÕu N < 4 th× th«ng b¸o N lµ nguyªn tè råi kÕt thóc; B­íc 4: i ß 2; B­íc 5: NÕu i > [](*) th× th«ng b¸o N lµ nguyªn tè råi kÕt thóc; B­íc 6: 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; B­íc 7: i ß i +1 råi quay l¹i b­íc 5; (*) BiÕn i nhËn gi¸ trÞ nguyªn thay ®æi trong ph¹m vi tõ 2 ®Õn [] + 1 vµ dïng ®Ó kiÓm tra N cã chia hÕt cho i hay kh«ng. Tõ thuËt gi¶i ®· cho ë trªn, h·y viÕt ch­¬ng tr×nh Pascal hoµn chØnh ®Ó gi¶i bµi to¸n. Møc ®é 3: Tù x©y dùng ch­¬ng tr×nh. ë møc ®é nµy, gi¸o viªn sÏ ®­a ra c¸c bµi to¸n vµ mét sè gîi ý råi tõ ®ã häc sinh sÏ tù x©y dùng ch­¬ng tr×nh. * D¹ng 3: Bµi tËp tæng hîp vµ mét sè bµi to¸n cã øng dông thùc tÕ. 2. 5 Mét sè gi¸o ¸n thùc nghiÖm d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh. Gi¸o ¸n sè 1: PhiÕu häc tËp C©u 1: Lo¹i biÓu thøc g× nhÊt thiÕt ph¶i cã mÆt trong c©u lÖnh r· nh¸nh? C©u 2: Cã thÓ dïng cÊu tróc rÏ nh¸nh d¹ng thiÕu ®Ó m« t¶ cÊu tróc rÏ nh¸nh d¹ng ®ñ ®­îc kh«ng? Cho vÝ dô minh ho¹. C©u 3: H·y x©y dùng thuËt gi¶i tÝnh tæng vµ ®­a kÕt qu¶ ra mµn h×nh S = 1+ 2+ 3 + …+ N, biÕt N ®­îc nhËp vµo tõ bµn phÝm. C©u 4: H·y x©y dùng thuËt gi¶i tÝnh tæng S, biÕt S = 1+ 2 + 3 + …+ N dõng khi S > 100. Gi¸o ¸n: §10. CÊu tróc lÆp A. Môc tiªu 1. KiÕn thøc - HiÓu nhu cÇu cña cÊu tróc lÆp trong biÓu diÔn thuËt to¸n. - HiÓu cÊu tróc lÆp víi sè lÇn lÆp cho biÕt tr­íc vµ cÊu tróc lÆp kiÓm tra ®iÒu kiÖn tr­íc. - B­íc ®Çu h×nh thµnh kü n¨ng lËp tr×nh cã cÊu tróc lÆp. 2. Kü n¨ng - BiÕt vËn dông ®óng ®¾n tõng lo¹i cÊu tróc lÆp vµo t×nh huèng cô thÓ - M« t¶ ®­îc thuËt to¸n cña mét sè bµi to¸n ®¬n gi¶n cã sö dông lÖnh lÆp. - BiÕt diÔn ®¹t ®óng c¸c c©u lÖnh, so¹n ®­îc ch­¬ng tr×nh gi¶i c¸c bµi to¸n ®¬n gi¶n ¸p dông c¸c cÊu tróc ®iÒu khiÓn. 3. Th¸i ®é - X¸c ®Þnh th¸i ®é nghiªm tóc trong häc tËp khi tiÕp xóc víi nhiÒu quy ®Þnh nghiªm ngÆt trong lËp tr×nh. - TiÕp tôc rÌn luyÖn nh÷ng phÈm chÊt cÇn thiÕt cña ng­êi lËp tr×nh, nhÊt lµ t­ duy thuËt gi¶i. - Ham muèn gi¶i c¸c bµi tËp b»ng lËp tr×nh. B. Ph­¬ng Ph¸p - D¹y häc b»ng ph­¬ng ph¸p nªu t×nh huèng “cã vÊn ®Ò”. - Sö dông c¸c phiÕu häc tËp vµ c¸c c©u hái gîi më. C. ChuÈn bÞ 1. ChuÈn bÞ cña gi¸o viªn: C¸c phiÕu häc tËp, gi¸o ¸n, c¸c dông cô trùc quan, ch­¬ng tr×nh ®Ó minh ho¹. 2. ChuÈn bÞ cña häc sinh: S¸ch gi¸o khoa, vë ghi, c¸c thuËt to¸n gi¸o viªn yªu cÇu bµi tËp vÒ nhµ. D. Ho¹t ®éng D¹y – häc I. æn ®Þnh II. KiÓm tra bµi cò: GV: gäi 2 häc sinh lªn tr×nh bµy c¸c c©u tr¶ lêi cho phiÕu häc tËp mµ gi¸o viªn ®· ph¸t ë tiÕt tr­íc. L­u ý tíi hai bµi tËp ®­a ra trong phiÕu: + H·y x©y dùng thuËt gi¶i tÝnh tæng vµ ®­a kÕt qu¶ ra mµn h×nh S = 1+ 2+ 3 + …+ N, biÕt N ®­îc nhËp vµo tõ bµn phÝm. + H·y x©y dùng thuËt gi¶i tÝnh tæng S, biÕt S = 1+ 2 + 3 + …+ N dõng khi S > 100. III. TiÕn tr×nh d¹y – häc bµi míi: §Æt vÊn ®Ò: GV chiÕu Slide cho ch­¬ng tr×nh sau: Yªu cÇu häc sinh nhËn xÐt kÕt qu¶ thùc hiÖn ch­¬ng tr×nh? GV: Trong nh÷ng c©u lÖnh mµ chóng ta ®· ®­îc häc cã lÖnh nµo thÓ hiÖn mét c«ng viÖc nµo ®ã ®­îc thùc hiÖn nhiÒu lÖnh kh«ng? Muèn thùc hiÖn c«ng viÖc nµo ®ã nhiÒu lÇn ta ph¶i lµm thÕ nµo? HS: Tr¶ lêi. GV DÉn d¾t: §Ó tr¸nh ph¶i viÕt ®i viÕt l¹i nhiÒu lÇn mét c©u lÖnh nµo ®ã, Turbo Pascal cho phÐp ng­êi lËp tr×nh sö dông c©u lÖnh lÆp. Ta ®i t×m hiÓu bµi míi. 2. TriÓn khai bµi: Ho¹t ®éng 1: T×m hiÓu vÒ lÆp. Néi dung Ho¹t ®éng cña GV vµ HS 1. LÆp a. Bµi to¸n 1: TÝnh tæng vµ ®­a kÕt qu¶ ra mµn h×nh S = 1 + 2+ 3+ …+ N, biÕt N ®­îc nhËp vµo tõ bµn phÝm. * Thuật toán tong1a: Bước 1: Nhập N Bước 2: S ← 0; i ←1; Bước 3: Nếu i >N chuyển đến B6 Bước 4: S ← S+i; Bước 5: i ← i +1; quay lại Bước 2 Bước 6: Đưa ra S ; Kết thúc * ThuËt to¸n tong1b: B­íc 1: NhËp N B­íc 2: S ß 0; i ß N; B­íc 3: NÕu i < 1 chuyÓn ®Õn B­íc 6 B­íc 4: S ß S + i; B­íc 5: i ß i – 1; quay l¹i B­íc 2 B­íc 6: §­a ra S; KÕt thóc b. Bµi to¸n 2: TÝnh tæng S, biÕt S = 1 + 2 + 3 + …+ N dõng khi S > 100 * ThuËt to¸n tæng _2: B­íc 1: S ß 0; N ß 0; B­íc 2: NÕu S > 100 chuyÓn ®Õn B5 B­íc 3: N ß N +1; B­íc 4: S ß S + N; quay l¹i B2 B­íc 5: §­a ra S; KÕt thóc KÕt luËn: Trong lËp tr×nh, còng cã nh÷ng thao t¸c, nh÷ng c©u lÖnh lÆp ®i lÆp l¹i nhiÒu lÇn t¹o thµnh cÊu tróc lÆp. * Cã hai lo¹i cÊu tróc lÆp: - LÆp víi sè lÇn biÕt tr­íc; - LÆp víi sè lÇn ch­a biÕt tr­íc. C¸c bµi to¸n 1 vµ bµi to¸n 2 ®· ®­îc häc sinh chuÈn bÞ tr­íc th«ng qua phiÕu häc tËp nªn gi¸o viªn chØ cÇn kiÓm tra thuËt gi¶i mµ häc sinh ®­a ra. GV: ChiÕu Slide 2 ®Ò bµi. GV: Gäi hai häc sinh cña hai nhãm trong líp lªn b¶ng d¸n thuËt to¸n cña nhãm m×nh ®· chuÈn bÞ. HS: Quan s¸t theo dâi thuËt to¸n trªn b¶ng vµ so s¸nh víi thuËt to¸n cña m×nh. GV: Gäi häc sinh d­íi líp nhËn xÐt thuËt to¸n cña b¹n. HS: NhËn xÐt bµi cña b¹n. GV: Tæng hîp ý kiÕn, nhËn xÐt vµ söa l¹i thuËt to¸n cña hai bµi to¸n trªn cho ®óng. GV: ThuËt hiÖn 2 thuËt to¸n trªn b»ng Slide m« pháng trªn Power Point vµ yªu cÇu häc sinh nhËn xÐt ®iÓm gièng nhau vµ kh¸c nhau gi÷a hai thuËt to¸n. HS: Suy nghÜ vµ nªu sù gièng nhau vµ kh¸c nhau gi÷a hai thuËt to¸n: + Gièng nhau: C«ng viÖc tÝnh tæng lÆp ®i lÆp l¹i nhiÒu lÇn. + Kh¸c nhau: - ThuËt to¸n 1 dõng tÝnh tæng khi i > N, lÆp víi sè lÇn biÕt tr­íc (N lÇn). - ThuËt to¸n 2 dõng tÝnh tæng khi S > 100; lÆp víi sè lÇn ch­a biÕt tr­íc (S > 100). GV: ChiÕu Slide HS: Ghi chÐp bµi. Ho¹t ®éng 2: T×m hiÓu lÆp víi sè lÇn biÕt tr­íc vµ c©u lÖnh FOR – DO Néi dung Ho¹t ®éng cña GV vµ HS 2. LÆp víi sè lÇn biÕt tr­íc vµ c©u lÖnh For - do. * D¹ng lÆp tiÕn: For : = to do ; * D¹ng lÆp lïi: For : = downto do ; Trong ®ã: - BiÕn ®Õm lµ biÕn ®¬n, th­êng cã kiÓu sè nguyªn. - Gi¸ trÞ ®Çu vµ gi¸ trÞ cuèi lµ c¸c biÓu thøc cïng kiÓu víi biÕn ®Õm vµ gi¸ trÞ ®Çu ph¶i nhá h¬n hoÆc b»ng gi¸ trÞ cuèi. C¸ch thùc hiÖn For – do: - ë d¹ng lÆp tiÕn, c©u lÖnh sau do ®­îc thùc hiÖn tuÇn tù, víi biÕn ®Õm lÇn l­ît nhËn c¸c gi¸ trÞ liªn tiÕp t¨ng tõ gi¸ trÞ ®Çu ®Õn gi¸ trÞ cuèi. - ë d¹ng lÆp lïi, c©u lÖnh sau do ®­îc thùc hiÖn tuÇn tù, víi c¸c biÕn ®Õm lÇn l­ît nhËn c¸c gi¸ trÞ liªn tiÕp gi¶m tõ gi¸ trÞ ®Çu ®Õn gi¸ trÞ cuèi. Chó ý: - Gi¸ trÞ ®Çu vµ gi¸ trÞ cuèi cã thÓ lµ nh÷ng biÓu thøc. - Trong vßng lÆp kh«ng nªn cã c©u lÖnh lµm thay ®æi gi¸ trÞ biÕn ®iÒu khiÓn. Ch­¬ng tr×nh thuËt to¸n 1: Program Tong1; Var S, i , N : Byte; Begin Write( ‘ Nhap N = ’); Readln(N); S : = 0; For i := 1 to N do S : = S +i; Writeln(‘ Tong la S = ’, S); Readln; End. GV: Cho häc sinh nhËn xÐt kÕt qu¶ sau khi thùc hiÖn thuËt to¸n tong1a ®· ®­a ra ë trªn víi gi¸ trÞ N cô thÓ N = 7 ch¼ng h¹n. HS: TÝnh to¸n vµ ®­a ra kÕt qu¶. GV: Nãi chung mét sè thuËt to¸n cã nh÷ng thao t¸c thùc hiÖn lÆp ®i lÆp l¹i mét sè lÇn liªn tiÕp. => LÆp víi sè lÇn biÕt tr­íc. GV: ChiÕu Slide 5 vµ 6. GV: Thùc hiÖn 1 lÖnh ®óng có ph¸p trªn Pascal vµ yªu cÇu häc sinh nhËn xÐt. For i := 1 to 10 do Writeln(i); For i := 10 downto 1 do Writeln(i); HS: Quan s¸t c©u lÖnh thùc hiÖn vµ nhËn xÐt 2 c©u lÖnh trªn. GV: Gi¶i thÝch có ph¸p vµ ý nghÜa cña hai c©u lÖnh trªn. ChiÕu Slide 7. GV: - Muèn in gi¸ trÞ tõ 1 ®Õn 100 th× ta ph¶i lµm thÕ nµo? - Sö dông hai có ph¸p h·y viÕt l¹i ®o¹n in c¸c sè. - ThÊy kh¸c khi in gi¸ trÞ ®ã nh­ thÕ nµo? HS: For i := 1 to 100 do Writeln(i: 4); For i:=100 downto 1 do Writeln(i: 4); GV: Ch¹y ®o¹n lÖnh trªn trong ch­¬ng tr×nh Pascal vµ yªu cÇu häc sinh nhËn xÐt. For i := 1 to 10 do Begin Write(i); i : = i +1; end; X:=5; Y := 15; For x := x+1 to y do Begin Write (x : 4); x := 2; end; HS: suy nghÜ tr¶ lêi. GV: TËp hîp ý kiÕn vµ gi¶i thÝch cho häc sinh. - Trong vßng lÆp kh«ng nªn cã c©u lÖnh g¸n gi¸ trÞ lµm thay ®æi biÕn ®iÒu khiÓn. Trong Turbo Pascal th× cho phÐp nh­ng trong Free Pascal th× sÏ th«ng b¸o lçi biªn dÞch. - C¸c gi¸ trÞ ®Çu vµ gi¸ trÞ cuèi cã thÓ lµ nh÷ng biÓu thøc. Gi¸ trÞ ®­îc tÝnh tr­íc khi vµo vßng lÆp vµ lµm nhiÖm vô gi¸ trÞ ®Çu vµ gi¸ trÞ cuèi. Do ®ã, trong vßng lÆp nÕu cã biÕn nµo n»m trong hai biÓu thøc nµy bÞ thay ®æi th× gi¸ trÞ ®Çu vµ gi¸ trÞ cuèi vÉn kh«ng thay ®æi. GV: ch¹y ch­¬ng tr×nh trªn Pascal. HS: Chó ý quan s¸t kÕt qu¶ khi ch¹y ch­¬ng tr×nh. GV: Më ch­¬ng tr×nh Violet ®Ó cho häc sinh lµm mét sè c©u hái tr¾c nghiÖm cñng cè. IV. Cñng cè C©u 1: KÕt qu¶ cña S sau khi thùc hiÖn ®o¹n lÖnh sau: S :=0; For i := 1 to 3 do S := S + i; a. 0 b. 1 c. 3 d. 6 C©u 2: §o¹n lÖnh sau cho kÕt qu¶ S b»ng bao nhiªu: S : = 0; For i : = 3 downto 1 to S : = S +1; a. 0 b. 1 c. 3 d. 6 C©u 3: H·y chän ®óng / sai cho c¸c ph¸t biÓu sau ®©y: Gi¸ trÞ ®Çu, gi¸ rÞ cuèi lµ c¸c biÓu thøc cïng kiÓu. X lµ biÕn kiÓu thùc; Ta cã c©u lÖnh lÆp For X : = 1 to 100 do S : = s + x; S, i lµ kiÓu nguyªn; C©u lÖnh For i : = 1 to 1 do S := S + 1; C©u lÖnh S : = S + 1; sÏ ®­îc lÆp hai lÇn. d. Sau DO muèn thùc hiÖn nhiÒu lÖnh ph¶i sö dông c©u lÖnh ghÐp. V. DÆn dß, h­íng dÉn häc sinh häc tËp ë nhµ - Xem l¹i c¸ch viÕt mét ch­¬ng tr×nh Turbo Pascal ®¬n gi¶n. 1. Lµm bµi tËp 3, 5a, 6 trong SGK (trang 51). 2. P = 1 – 2 +3 – 4 + …+ (-1)n+1 n 3. P = 1*2*3*4*…*n - ChuÈn bÞ bµi míi: Bµi 10. CÊu tróc lÆp (tiÕp). Gi¸o ¸n sè 2: PhiÕu häc tËp C©u hái 1: Chóng ta sö dông cÊu tróc lÆp trong tr­êng hîp nµo? Cã nh÷ng kiÓu d÷ liÖu chuÈn nµo mµ em ®· ®­îc häc? C©u hái 2: Sö dông c¸c cÊu tróc ®iÒu khiÓn vµ c¸c kiÓu d÷ liÖu ®· ®­îc häc lËp ch­¬ng tr×nh: NhËp vµo nhiÖt ®é (trung b×nh) cña mçi ngµy trong tuÇn. TÝnh vµ in ra mµn h×nh nhiÖt ®é trung b×nh cña tuÇn vµ sè l­îng ngµy trong tuÇn cã nhiÖt ®é cao h¬n nhiÖt ®é trung b×nh cña tuÇn. Gi¸o ¸n: §11. KiÓu m¶ng A. môc tiªu 1. KiÕn thøc - KiÓu m¶ng lµ mét kiÓu d÷ liÖu cã cÊu tróc, rÊt cÇn thiÕt vµ h÷u Ých trong nhiÒu ch­¬ng tr×nh. - M¶ng mét chiÒu lµ mét d·y h÷u h¹n c¸c phÇn tö cïng kiÓu. - Cã thÓ truy xuÊt (hay thao t¸c) trªn mçi phÇn tö cña m¶ng, trong viÖc lµm ®ã mçi phÇn tö cña m¶ng ®­îc x¸c ®Þnh bëi tªn c¶u m¶ng vµ chØ sè t­¬ng øng cña phÇn tö nµy. - C¸c ng«n ng÷ lËp tr×nh th«ng dông cho phÐp ng­êi lËp tr×nh x©y dùng kiÓu d÷ liÖu m¶ng mét chiÒu. 2. Kü n¨ng - NhËn biÕt ®­îc c¸c thµnh phÇn trong khai b¸o m¶ng mét chiÒu. - NhËn biÕt ®Þnh danh cña mét phÇn tö xuÊt hiÖn trong mét ch­¬ng tr×nh. - BiÕt c¸ch viÕt khai b¸o m¶ng ®¬n gi¶n víi chØ sè kiÓu miÒn con cña kiÓu nguyªn - Cµi ®Æt ®­îc thuËt to¸n cña mét sè bµi to¸n ®¬n gi¶n víi kiÓu d÷ liÖu m¶ng mét chiÒu. - Thùc hiÖn khai b¸o m¶ng, truy nhËp, tÝnh to¸n c¸c phÇn tö m¶ng. 3. Th¸i ®é - TiÕp tôc x©y dùng lßng ham thÝch lËp tr×nh, nh»m gi¶i quyÕt c¸c bµi to¸n b»ng m¸y tÝnh ®iÖn tö. - RÌn luyÖn h¬n n÷a cho häc sinh c¸c phÈm chÊt cña ng­êi lËp tr×nh, t¸c phong lµm viÖc khoa häc, cã s¸ng t¹o. B. ph­¬ng ph¸p: Nªu t×nh huèng cã vÊn ®Ò, ®­a ra c¸c bµi to¸n ®Æt vÊn ®Ò h­íng häc sinh vµo néi dung míi, c©u hái gîi më. C. ChuÈn bÞ 1. ChuÈn bÞ cña gi¸o viªn: C¸c phiÕu häc tËp, gi¸o ¸n, c¸c dông cô trùc quan, ch­¬ng tr×nh ®Ó minh ho¹. 2. ChuÈn bÞ cña häc sinh: S¸ch gi¸o khoa, vë ghi, c¸c thuËt to¸n gi¸o viªn yªu cÇu bµi tËp vÒ nhµ. D. Ho¹t ®éng D¹y – häc I. æn ®Þnh II. KiÓm tra bµi cò: GV: Gäi 2 häc sinh lªn tr×nh bµy c¸c c©u tr¶ lêi cho phiÕu häc tËp mµ gi¸o viªn ®· ph¸t ë tiÕt tr­íc sau ®ã: HS1: ViÕt ch­¬ng tr×nh vµo nhiÖt ®é trung b×nh cña mçi ngµy trong tuÇn. TÝnh vµ in ra mµn h×nh nhiÖt ®é trung b×nh cña tuÇn. HS2: ViÕt ®o¹n ch­¬ng tr×nh tÝnh sè l­îng ngµy trong tuÇn cã nhiÖt ®é cao h¬n nhiÖt ®é trung b×nh tÝnh ®­îc. III. Bµi míi 1. §Æt vÊn ®Ò: Víi bµi to¸n ®Æt ra ë c©u hái 2 trong phiÕu häc tËp, khi N kh«ng cßn lµ 7 ngµy cña mét tuÇn mµ cã thÓ lµ 30 ngµy hoÆc 365 ngµy th× khi ®ã ta ph¶i gi¶i quyÕt bµi to¸n ®ã nh­ thÕ nµo? 2. TriÓn khai bµi míi: Ho¹t ®éng 1: T×m hiÓu vÝ dô Néi dung Ho¹t ®éng cña GV vµ HS * VÝ dô: NhËp vµo nhiÖt ®é (trung b×nh) cña mçi ngµy trong tuÇn. TÝnh vµ in ra mµn h×nh nhiÖt ®é trung b×nh cña tuÇn vµ sè l­îng ngµy trong tuÇn cã nhiÖt ®é cao h¬n nhiÖt ®é trung b×nh cña tuÇn. Program Nhietdo_tuan; Var t1,t2,t3,t4,t5,t6,t7,tb: Real; Diem: integer; Begin Writeln(‘Nhap vao nhiet do cua 7 ngay:’); Readln(t1,t2,t3,t4,t5,t6,t7); tb:= (t1 + t2 + t3 + t4 + t5 + t6 + t7)/7; dem:=0; If t1>tb Then dem:=dem + 1; If t2>tb Then dem:=dem + 1; If t3>tb Then dem:=dem + 1; If t4>tb Then dem:=dem + 1; If t5>tb Then dem:=dem + 1; If t6>tb Then dem:=dem + 1; If t7>tb Then dem:=dem + 1; Writeln( ‘ Nhiet do trung binh cua tuan la: ’, tb:5:2); Writeln( ‘ So ngay co nhiet do cao hon trung binh la: ’, dem); Readln; End. - Do häc sinh ®· ®­îc chuÈn bÞ tr­íc ë nhµ vÒ vÝ dô nµy nªn gi¸o viªn chØ cÇn ®­a ra ch­¬ng tr×nh ®­îc viÕt b»ng c¸ch th«ng th­êng ®Ó häc sinh quan s¸t vµ so s¸nh. GV: Khi kh«ng cßn lµ 7 ngµy cña mét tuÇn mµ cã thÓ lµ 30 ngµy hoÆc 365 ngµy th× khi ®ã ta ph¶i khai b¸o bao nhiªu biÕn? HS: Ta sÏ ph¶i khai b¸o tíi 356 biÕn nhiÖt ®é vµ 1 biÕn ®Õm. GV: §Ó tÝnh ®­îc sè ngµy cã nhiÖt ®é cao h¬n nhiÖt ®é trung b×nh cña tuÇn ta ph¶i dïng bao nhiªu c©u lÖnh IF ®Ó so s¸nh? HS: Ta ph¶i dïng tíi 365 c©u lÖnh IF. GV: Ch­¬ng tr×nh nÕu viÕt nh­ vËy sÏ cã nh÷ng h¹n chÕ nµo? HS: Ch­¬ng tr×nh sÏ rÊt dµi dßng, khai b¸o qu¸ nhiÒu biÕn, khã hiÓu vµ ®«i khi cã thÓ kh«ng cho ra kÕt qu¶ ®óng. GV: §Ó kh¾c phôc ®­îc ®iÒu ®ã ng«n ng÷ lËp tr×nh cho phÐp ng­êi lËp tr×nh x©y dùng kiÓu d÷ liÖu míi b»ng c¸ch ghÐp chung 7 biÕn (hoÆc 365 biÕn) thµnh mét d·y vµ ®¹t cho nã chung mét tªn, ®¸nh cho mçi phÇn tö mét chØ sè. KiÓu d÷ liÖu nµy gäi lµ kiÓu m¶ng mét chiÒu. Ho¹t ®éng 2: T×m hiÓu kh¸i niÖm m¶ng mét chiÒu. Néi dung Ho¹t ®éng cña GV vµ HS a. Kh¸i niÖm * M¶ng mét chiÒu: lµ d·y h÷u h¹n c¸c phÇn tö cïng kiÓu. M¶ng ®­îc ®Æt tªn vµ mçi phÇn tö cña nã cã mét chØ sè. * Víi m¶ng mét chiÒu x¸c ®Þnh: - Tªn m¶ng mét chiÒu; - Sè l­îng phÇn tö; - KiÓu d÷ liÖu cña phÇn tö; - C¸c khai b¸o biÕn m¶ng; - C¸ch tham chiÕu ®Õn phÇn tö. GV: Qua vÝ dô trªn h·y tr×nh bµy kh¸i niÖm m¶ng mét chiÒu? HS: Tr×nh bµy kh¸i niÖm. GV: Dùa vµo kh¸i niÖm kiÓu m¶ng mét chiÒu em nµo cã thÓ cho biÕt khi khai b¸o m¶ng th× x¸c ®Þnh ®­îc nh÷ng g×? HS: Dùa vµo kh¸i niÖm ®Ó tr¶ lêi. Ho¹t ®éng 3: T×m hiÓu c¸ch khai b¸o m¶ng mét chiÒu Néi dung Ho¹t ®éng cña GV vµ HS b. Khai b¸o: - Trùc tiÕp: Var : array [kiÓu chØ sè] of ; - Gi¸n tiÕp: Type = array [kiÓu chØ sè] of ; Var : ; Trong ®ã: + KiÓu phÇn tö: lµ kiÓu cña c¸c phÇn tö t¹o nªn m¶ng; + KiÓu chØ sè: ng­êi ta th­êng dïng mét ®o¹n sè nguyªn liªn tôc cã d¹ng n1..n2 víi n1, n2 lµ c¸c h»ng hoÆc biÓu thøc nguyªn x¸c ®Þnh chØ sè ®Çu vµ chØ sè cuèi (n1<=n2). VÝ dô: VAR SV : ARRAY [1..10] OF REAL; M : ARRAY [‘a’.. ‘k’] of Integer; A, B : ARRAY [5..19] Word; GV: H·y nªu có ph¸p khai b¸o biÕn? HS: Tr¶ lêi. GV: Khai b¸o trªn Pascal nh­ sau: Var a: array[1..10] of integer; Begin End. DÞch ch­¬ng tr×nh trªn. HS: Chó ý quan s¸t GV: Gäi häc sinh nhËn xÐt khai b¸o ®ã. - DÞch cã b¸o lçi kh«ng? - BiÕn a nµy khai b¸o cã gièng c¸c biÕn kh¸c b×nh th­êng khai b¸o kh«ng? HS: Chó ý vµ tr¶ lêi c©u hái. GV: Cung cÊp có ph¸p khai b¸o trùc tiÕp vµ gi¶i thÝch. HS: Chó ý nghe gi¶ng vµ ghi bµi. GV: §Ó lËp tr×nh gi¶i bµi to¸n trªn ta cã thÓ khai b¸o nh­ sau: Var T: array [1..7] of real; HoÆc Type nhietdo = array [1..7] of Real; Var T : nhietdo; GV: Nªu hai c¸ch khai b¸o vµ gi¶i thÝch. HS: Chó ý ®Ó cã thÓ vËn dông khai b¸o cho c¸c bµi to¸n. GV: §­a ra mét sè khai b¸o ®Ó häc sinh chØ ra ®©u lµ khai b¸o hîp lÖ. Ho¹t ®éng 4: T×m hiÓu c¸ch tham chiÕu ®Õn 1phÇn tö cña m¶ng 1 chiÒu. Néi dung Ho¹t ®éng cña GV vµ HS c. Tham chiÕu ®Õn phÇn tö cña m¶ng [chØ sè] d. NhËp / xuÊt d÷ liÖu trªn m¶ng: - NhËp: Dïng thñ tôc Read / Readln /([ chØ sè] ); ®Ó nhËp d÷ liÖu cho m¶ng. §o¹n ch­¬ng tr×nh nhËp nhËp m¶ng mét chiÒu a gåm n phÇn tö ®­îc viÕt nh­ sau: Write(‘Nhap so ptu cua mang n= ’); Readln(n); For i : = 1 to n do Begin Write(‘Nhap phan tu thu’, i , ‘:’); Readln(a[i]); End; - XuÊt: Write/Writeln([chØ sè]); §o¹n ch­¬ng tr×nh in m¶ng mét chiÒu gåm n phÇn tö: For i : = 1 to n do Write( [i], ‘ ’); GV: §Ó tham chiÕu ®Õn 1 phÇn tö trong m¶ng ta dïng cÊu tróc có ph¸p sau: [chØ sè] HS: Chó ý l¾ng nghe vµ ghi bµi. GV: Cho vÝ dô sau: T 21 39 9 8 4 12 67 1 2 3 4 5 6 7 GV: H·y m« t¶ m¶ng trªn? ViÕt T[3] cã nghÜa lµ g×? T[5] = ? HS: M¶ng ®· cho cã tªn lµ T gåm 7 phÇn tö lµ c¸c sè nguyªn. NÕu viÕt T[3] cã nghÜa lµ ta ®ang tham chiÕu ®Õn phÇn tö thø 3 cña m¶ng T vµ T[5] = 4. GV: Gîi ý ®Ó häc sinh cã thÓ ®­a ra c¸ch nhËp gi¸ trÞ cho m¶ng vµ in m¶ng. VD: + NhËp phÇn tö thø 1 cña m¶ng: Read(T[1]); à NhiÒu phÇn tö? Readln(T[2], T[5], T[7]); + M¶ng T, nhËp vµo 7 phÇn tö : For i : = 1 to 7 do Begin Write(‘ Nhap nhiet do cua ngay thu’, i); Readln(A[i]); End; HS: §­a ra c¸ch nhËp cho tr­êng hîp tæng qu¸t (n phÇn tö). - Tr­êng hîp c¸c gi¸ trÞ cña m¶ng cã ®iÒu kiÖn th× cÇn ph¶i thùc hiÖn nh­ thÕ nµo? (VD c¸c phÇn tö cña m¶ng ph¶i lµ sè d­¬ng) For i : = 1 to 10 do Repeat Write(‘ Nhap nhiet do cua ngay thu’, i); Readln(A[i]); Until A[i] > 0; - Tr­êng hîp khèng chÕ sè l­îng phÇn tö cña m¶ng? à Sö dông Repeat. GV: Ta th­êng dïng thñ tôc g× ®Ó in gi¸ trÞ ra mµn h×nh? HS: Dïng thñ tôc Write / Writeln; GV: §Ó in ra phÇn tö ®Çu tiªn cña m¶ng T ta ph¶i viÕt nh­ thÕ nµo? HS: Ta viÕt : Write(T[1]); GV: Tr­êng hîp in ra cã chØ râ phÇn tö thø mÊy cña m¶ng: For i : = 1 to 10 do Write(‘A[‘, i, ‘]=’, A[i] : 3); IV. Cñng cè - Kh¸i niÖm kiÓu m¶ng? - Khai b¸o? - Tham chiÕu ®Õn 1 phÇn tö m¶ng 1 chiÒu? V. DÆn dß, h­íng dÉn häc sinh häc tËp ë nhµ. - Lµm bµi tËp vÒ nhµ. ViÕt ch­¬ng tr×nh cho m¸y thùc hiÖn nh÷ng c«ng viÖc sau: a. NhËp vµo m¶ng A [1..n] ( n> 9), c¸c phÇn tö lµ sè thùc lín h¬n – 2 vµ nhá h¬n 2. b. TÝnh trung b×nh céng cña c¸c phÇn tö d­¬ng cña m¶ng. c. So s¸nh sè phÇn tö d­¬ng víi sè phÇn tö ©m cña m¶ng. d. T×m phÇn tö nhá nhÊt vµ lín nhÊt cña m¶ng. ChØ ra vÞ trÝ vµ gi¸ trÞ cña chóng. e. TÝnh a[1] + a[2]2 + a[3]3 + …+ a[n]n. - Häc kü bµi ®Ó cã thÓ chän cÊu tróc trong khi viÕt ch­¬ng tr×nh. 2.6 KÕt luËn ch­¬ng II Trong ch­¬ng II kho¸ luËn ®· ®­a ra c¸c nguyªn t¾c d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i vµ dùa trªn hÖ thèng c¸c t¾c ®ã ®Ò ra 5 ®Þnh h­íng ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh th«ng qua d¹y häc c¸c cÊu tróc ®iÒu khiÓn vµ c¸c kiÓu d÷ liÖu cã cÊu tróc. Tõ môc ®Ých, yªu cÇu vÒ néi dung kiÕn thøc häc sinh cÇn n¾m v÷ng vÒ c¸c cÊu tróc ®iÒu khiÓn vµ c¸c kiÓu d÷ liÖu cã cÊu tróc Tin häc 11 THPT. T«i ®· vËn dông c¸c quan ®iÓm d¹y häc tÝch cùc, d¹y häc b»ng ho¹t ®éng,…, khai th¸c c¸c ph­¬ng tiÖn d¹y häc ®Ó x©y dùng quy tr×nh d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh.Víi hai quy tr×nh d¹y häc cô thÓ lµ: Quy tr×nh d¹y häc chiÕm lÜnh tri thøc lËp tr×nh vµ quy tr×nh d¹y häc rÌn luyÖn kü n¨ng lËp tr×nh. Trong ch­¬ng nµy, kho¸ luËn còng ®· giíi thiÖu mét sè gi¸o ¸n d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cã kÌm theo c¸c phiÕu häc tËp vµ ®· ®­îc thùc nghiÖm t¹i tr­êng THPT §«ng S¬n I - §«ng S¬n – Thanh Ho¸. Ch­¬ng III Thùc nghiÖm s­ ph¹m 3.1 Môc ®Ých vµ nhiÖm cô cña thùc nghiÖm s­ ph¹m Môc ®Ých thùc nghiÖm lµ kiÓm tra tÝnh thùc thi vµ tÝnh hiÖu qu¶ cña viÖc sö dông mét sè biÖn ph¸p ®· ®­îc ®­a ra trong ®Ò tµi. (§Æc biÖt lµ c¸c quy tr×nh d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i). 3.2 §èi t­îng thùc nghiÖm s­ ph¹m T«i chän líp 11A4 (48 häc sinh) lµm líp thùc nghiÖm (TN) vµ líp 11A6 (49 häc sinh) lµm líp ®èi chøng (§C) thuéc tr­êng THPT §«ng S¬n I – §«ng S¬n - Thanh Hãa. C¶ hai líp ®Òu häc Ban khoa häc tù nhiªn. §­îc sù ®ång ý cña tæ chuyªn m«n vµ cña gi¸o viªn gi¶ng d¹y, t«i ®· t×m hiÓu kÕt qu¶ häc tËp cña c¸c líp khèi 11 cña tr­êng vµ nhËn thÊy tr×nh ®é chung vÒ m«n Tin cña hai líp ®­îc chän ë trªn lµ t­¬ng ®­¬ng nhau rÊt thuËn lîi cho viÖc kiÓm tra ®¸nh gi¸ vµ ®èi chøng viÖc thùc thi c¸c biÖn ph¸p ®­a ra trong luËn v¨n. 3.3 Néi dung vµ kÕt qu¶ thùc nghiÖm s­ ph¹m 3.3.1 Néi dung thùc nghiÖm: TiÕn hµnh gi¶ng d¹y c¸c tiÕt lÝ thuyÕt cã sù ¸p dông quy tr×nh d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i ®· ®­a ra trong luËn v¨n. Sau ®ã tiÕn hµnh «n tËp, cñng cè l¹i kiÕn thøc cho häc sinh nh»m rÌn luyÖn t­ duy thuËt gi¶i, t­ duy logic trong lËp tr×nh cho häc sinh råi tiÕn hµnh kiÓm tra, ®¸nh gi¸ ë c¸c líp thùc nghiÖm vµ ®èi chøng víi cïng mét ®Ò kiÓm tra. Do h¹n chÕ vÒ thêi gian vµ ®Ó ®¶m b¶o ®óng ch­¬ng tr×nh d¹y häc theo ph©n phèi ch­¬ng tr×nh. T«i ®· tiÕn hµnh d¹y: - Bµi 10. CÊu tróc lÆp (TiÕt 1), bµi 11. KiÓu m¶ng, bµi 13. KiÓu b¶n ghi vµ mét sè tiÕt bµi tËp vµ thùc hµnh cho líp thùc nghiÖm 11A4 b»ng ph­¬ng ph¸p vµ quy tr×nh d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i. - Còng c¸c bµi nh­ trªn ®èi víi líp ®èi chøng 11A6 nh­ng b»ng ph­¬ng ph¸p d¹y häc th«ng th­êng vµ kh«ng ¸p dông quy tr×nh d¹y häc ®· ®­a ra trong luËn v¨n. - Sau khi d¹y häc cho häc sinh cña c¶ hai líp §C vµ TN c¸c bµi 10. CÊu tróc lÆp, bµi 11. KiÓu m¶ng vµ mét tiÕt bµi tËp t«i ®· tiÕn hµnh cho häc sinh lµm bµi kiÓm tra lÇn thø nhÊt. Bµi kiÓm tra thø hai ®­îc tiÕn hµnh vµo cuèi ®ît thùc nghiÖm s­ ph¹m, sau khi ®· d¹y cho häc sinh bµi 13. KiÓu b¶n ghi vµ mét sè tiÕt bµi tËp vµ thùc hµnh. 3.3.2 KÕt qu¶ thùc nghiÖm Qua c¸c lÇn kiÓm tra ®èi víi líp thùc nghiÖm vµ líp ®èi chøng t«i ®· chÊm bµi vµ xö lý kÕt qu¶ thu ®­îc theo c¸c ph­¬ng ph¸p thèng kª to¸n häc: B¶ng thèng kª sè ®iÓm. B¶ng tÇn suÊt sè % häc sinh (HS) ®¹t ®iÓm xi. B¶ng tÇn sè % HS ®¹t ®iÓm xi trë xuèng. VÏ ®­êng cong tÇn suÊt luü tÝch. TÝnh c¸c th«ng sè thèng kª theo c«ng thøc: §iÓm trung b×nh: = §é lÖnh chuÈn: S = Ph­¬ng sai: S2 = HÖ sè biÕn thiªn: V = .100% Trong ®ã: Xi lµ ®iÓm sè cña häc sinh; n lµ sè häc sinh tham gia lµm bµi kiÓm tra. B¶ng 1: B¶ng thèng kª ®iÓm sè LÇn §iÓm Líp 1 2 3 4 5 6 7 8 9 10 1 TN (11A4) 0 0 0 2 13 9 14 6 4 0 §C (11A6) 0 0 1 7 19 10 5 4 2 0 2 TN (11A4) 0 0 0 1 10 13 11 7 5 1 §C (11A6) 0 1 0 6 20 9 6 5 2 0 B¶ng 2: B¶ng tÇn suÊt sè % HS ®¹t ®iÓm xi LÇn §iÓm Líp 1 2 3 4 5 6 7 8 9 10 1 TN (11A4) 0 0 0 4.2 27.1 18.8 29.2 12.5 8.3 0 §C (11A6) 0 0 2 14.3 38.8 22.4 10.2 8.2 4.1 0 2 TN (11A4) 0 0 0 2.08 14.6 22.92 27.1 16.7 15 2.1 §C (11A6) 0 2.04 0 12.2 40.8 18.37 12.2 10.2 4.1 0 B¶ng 3: B¶ng tÇn sè % HS ®¹t ®iÓm xi trë xuèng LÇn §iÓm Líp 1 2 3 4 5 6 7 8 9 10 1 TN (11A4) 0.0 0.0 0.0 4.2 31.3 50.0 79.2 91.7 100 100 §C (11A6) 0.0 0.0 2.1 16.7 56.3 77.1 87.5 95.8 100 100 2 TN (11A4) 0.0 0.0 0.0 2.1 22.9 50.0 72.9 87.5 97.9 100 §C (11A6) 0.0 2.0 2.0 14.3 55.1 73.5 85.7 95.9 100 100 §å thÞ c¸c ®­êng cong tÇn suÊt luü tÝch (kiÓm tra lÇn 1) §å thÞ c¸c ®­êng cong tÇn suÊt luü tÝch (kiÓm tra lÇn 2) B¶ng 4: C¸c tham sè thèng kª (lÇn 1) Ph­¬ng ¸n Sè HS S2 S V% Z TN 48 6.43 2.04 1.34 32.72 2.57 §C 49 5.65 2.34 1.53 41.4 B¶ng 5: C¸c tham sè thèng kª (lÇn 2) Ph­¬ng ¸n Sè HS S2 S V% Z TN 48 6.67 1.9 1.38 28.48 3.35 §C 49 5.71 2.07 1.44 36.25 §é tin cËy: Z = 3.4 Ph©n tÝch, nhËn xÐt vµ rót ra kÕt luËn tõ thùc nghiÖm s­ ph¹m. LÇn 1: + §iÓm trung b×nh cña líp 11A4 cao h¬n so víi líp 11A6, nh­ng ch­a ®¸ng kÓ. + Tû lÖ häc sinh ®¹t ®iÓm 7 lµ cao nhÊt chiÕm 29,2% cña líp 11A4 so víi líp 11A6 cã tû lÖ häc sinh ®¹t ®iÓm 5 lµ cao nhÊt chiÕm 38,8%. + Líp 11A4 cã sè häc sinh ®¹t ®iÓm 9 lµ 8,3% trong khi ®ã líp 11A6 chØ cã 4,1%. + HÖ sè biÕn thiªn gi¸ trÞ ®iÓm sè cña líp thùc nghiÖm (32.72%) nhá h¬n so víi líp ®èi chøng (41.4%) chøng tá gi¸ trÞ ®iÓm sè cña líp TN tËp trung h¬n so víi líp §C. LÇn 2: + ë lÇn 1 th× ®iÓm trung b×nh cña líp 11A4 h¬n líp 11A6 nh­ng ch­a ®¸ng kÓ, qua lÇn kiÓm tra thø hai th× ®iÓm trung b×nh cña líp 11A4 ®· cao h¬n h¼n so víi líp 11A6. + Tû lÖ häc sinh ®¹t ®iÓm 9 ë líp 11A4 ®· v­ît h¬n h¼n líp 11A6 vµ cao h¬n so víi lÇn 1 (chiÕm 15%). + ë lÇn kiÓm tra thø nhÊt hÖ sè biÕn thiªn V cña líp TN lµ 32.72% nh­ng ®èi víi lÇn kiÓm tra thø 2 lµ 28.48% ®iÒu nµy chøng tá kÕt qu¶ häc tËp cña häc sinh ph©n t¸n quanh cµng Ýt. Qua ph©n tÝch c¸c kÕt qu¶ thùc nghiÖm ë trªn cho thÊy: - ChÊt l­îng n¾m v÷ng thuËt gi¶i ë líp 11A4 ®Òu h¬n vµ ch¾c h¬n so víi líp 11A6. ThÓ hiÖn ë kÕt qu¶ kiÓm tra cña líp 11A4 cao h¬n vµ ®ång ®Òu h¬n líp 11A6. - Kü n¨ng sö dông c¸c thao t¸c t­ duy nhÊt lµ t­ duy thuËt gi¶i ®­îc t¨ng c­êng vµ ph¸t triÓn h¬n. §iÒu nµy thÓ hiÖn ë chç, cïng mét ®Ò kiÓm tra vµ cïng mét thêi gian nh­ng kÕt qu¶ cña líp TN (11A4) cao h¬n líp §C (11A6). - §å thÞ tÇn suÊt luü tÝch cña hai líp qua hai lÇn kiÓm tra cho thÊy: ChÊt l­îng häc tËp cña líp TN thùc sù tèt h¬n so víi líp §C. ë líp TN cã nhiÒu ®iÓm cao h¬n líp §C (®å thÞ n»m phÝa d­íi dÞch ph¶i nhiÒu h¬n). Ta cÇn xÐt xem kÕt qu¶ ®¹t ®­îc nµy lµ do d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cã chÊt l­îng h¬n ph­¬ng ph¸p d¹y häc th«ng th­êng hay lµ do ngÉu nhiªn mµ cã. §Ó t×m hiÓu vÊn ®Ò nµy, t«i sö dông ph­¬ng ph¸p kiÓm ®Þnh thèng kª: Víi lÇn kiÓm tra thø nhÊt: + Gi¶ thuyÕt H0: = gi¶ thuyÕt thèng kª (Hai ph­¬ng ph¸p d¹y häc cho kÕt qu¶ ngÉu nhiªn). + Gi¶ thuyÕt H1: > ®èi gi¶ thuyÕt thèng kª (Ph­¬ng ph¸p d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cho kÕt qu¶ tèt h¬n ph­¬ng ph¸p d¹y häc th«ng th­êng). Chän møc ý nghÜa = 0.05, ®Ó kiÓm ®Þnh gi¶ thuyÕt H1 ta sö dông ®¹i l­îng ngÉu nhiªn sau: Z = Víi n1= 48; n2 = 49; , lµ gi¸ trÞ ®iÓm trung b×nh cña líp TN vµ líp §C thay sè vµo ta t×m ®­îc Z = 2.57 Víi = 0.05 Z(48)(0,05) = 1.68. So s¸nh Z vµ Zt ta thÊy Z > Zt, vËy gi¶ thuyÕt H0 bÞ b¸c bá. Do ®ã gi¶ thuyÕt H1 ®­îc chÊp nhËn, nh­ vËy > thùc chÊt kh«ng ph¶i do ngÉu nhiªn. Tøc lµ ph­¬ng ph¸p d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cã hiÖu qu¶ h¬n so víi ph­¬ng ph¸p d¹y häc th«ng th­êng. T­¬ng tù nh­ vËy víi lÇn kiÓm tra thø hai ta còng nhËn ®­îc kÕt qu¶ lµ Z = 3.35 > Zt = 1.68 cã nghÜa lµ ph­¬ng ph¸p d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cã hiÖu qu¶ thùc sù chø kh«ng ph¶i lµ do ngÉu nhiªn mµ cã. Tuy nhiªn, kÕt qu¶ ®ã cã ®­îc còng ph¶i kÓ ®Õn c¸c yÕu tè vÒ mÆt ®Þnh tÝnh nh­: tÝnh tÝch cùc, s¸ng t¹o, ham häc hái… cña HS trong giê häc. 3.5 KÕt luËn ch­¬ng III Ch­¬ng III lµ ch­¬ng thùc nghiÖm s­ ph¹m: Kho¸ luËn ®· nªu lªn ®­îc môc ®Ých, ®èi t­îng, néi dung thùc nghiÖm vµ ®· tiÕn hµnh thùc nghiÖm t¹i líp 11A4, lÊy líp 11A6 lµm líp ®èi chøng. Qu¸ tr×nh thùc nghiÖm s­ ph¹m cho thÊy: - ViÖc sö dông quy tr×nh d¹y häc theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh nh­ ®· tr×nh bµy ë ch­¬ng II lµ kh¶ thi. - C¸c gi¸o ¸n cho líp §C vµ TN hîp lý, cã hiÖu qu¶ thiÕt thùc ®èi víi viÖc n©ng cao n¨ng lùc nhËn thøc, t­ duy thuËt gi¶i cho häc sinh. - Do h¹n chÕ vÒ thêi gian vµ c¬ së vËt chÊt (phßng m¸y vi tÝnh cßn Ýt m¸y) nªn phÇn rÌn luyÖn kü n¨ng lËp tr×nh cho häc sinh ch­a nhiÒu. KÕt luËn Kho¸ luËn ®· gãp phÇn lµm s¸ng tá kh¸i niÖm, ®Æc ®iÓm cña t­ duy, t­ duy thuËt gi¶i, vai trß cña vÞªc ph¸t triÓn t­ duy thuËt gi¶i còng nh­ kh¸i niÖm, c¸c ®Æc tr­ng vµ c¸c ph­¬ng ph¸p biÓu diÔn thuËt to¸n, thuËt gi¶i. Kho¸ luËn ®· nghiªn cøu, tr×nh bµy c¸c nguyªn t¾c còng nh­ ®· x©y dùng c¸c ®Þnh h­íng, c¸c quy tr×nh d¹y häc theo h­íng “ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh th«ng qua d¹y häc c¸c cÊu tróc ®iÒu khiÓn vµ c¸c kiÓu d÷ liÖu cã cÊu tróc” trong ch­¬ng tr×nh Tin häc 11 – THPT. Ngoµi ra, kho¸ luËn còng ®· th©u tãm, ph©n tÝch nh÷ng kiÕn thøc chñ yÕu vÒ c¸c cÊu tróc ®iÒu khiÓn vµ c¸c kiÓu d÷ liÖu cã cÊu tróc ®Ó tõ ®ã tËp trung vµo x©y dùng c¸c hÖ thèng bµi tËp theo h­íng ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh. Qu¸ tr×nh thùc nghiÖm s­ ph¹m ®· gãp phÇn t¹o høng thó häc tËp, tÝnh tÝch cùc, tù lùc vµ rÌn luyÖn c¸c phÈm chÊt t­ duy cho häc sinh n©ng cao chÊt l­îng d¹y häc. Víi nh÷ng kÕt qu¶ ®ã, ®Ò tµi ®· ®¹t ®­îc môc ®Ých ®Ò ra vµ kh¼ng ®Þnh ®­îc gi¶ thuyÕt khoa häc ®­a ra ban ®Çu. Qua qu¸ tr×nh thùc hiÖn ®Ò tµi nghiªn cøu, t«i thÊy ®Ò tµi cßn mét sè nh­îc ®iÓm nh­ sau: - Do h¹n chÕ vÒ thêi gian vµ ®iÒu kiÖn gi¶ng d¹y nªn ®Ò tµi ch­a ®­îc triÓn khai trªn diÖn réng, víi nhiÒu líp ®èi t­îng. HiÖu qu¶ cña viÖc tæ chøc d¹y häc theo h­íng nµy cßn phô thuéc nhiÒu vµo n¨ng lùc s­ ph¹m, n¨ng lùc qu¶n lý häc tËp vµ ph­¬ng thøc tæ chøc cña gi¸o viªn. - HÖ thèng bµi tËp ®­îc x©y dùng theo h­íng ph¸t triÓn t­ duy thuËt gi¶i míi chØ triÓn khai ®­îc mét phÇn nhá do h¹n chÕ vÒ thêi l­îng c¸c tiÕt bµi tËp vµ thùc hµnh. Qu¸ tr×nh nghiªn cøu ®Ò tµi cßn gÆp mét sè khã kh¨n vÒ tµi liÖu tham kh¶o vµ do b¶n th©n ch­a cã nhiÒu kinh nghiÖm nªn khã tr¸nh khái mét sè sai sãt. T«i hy väng r»ng, ®Ò tµi sÏ gãp mét phÇn nhá bÐ vµo viÖc ®æi míi ph­¬ng ph¸p d¹y häc Tin häc ë tr­êng phæ th«ng. RÊt mong nhËn ®­îc sù quan t©m, ®ãng gãp ý kiÕn c¸c thÇy c« vµ c¸c b¹n ®Ó ®Ò tµi cña t«i ®­îc hoµn thiÖn h¬n. Phô lôc ®Ò kiÓm tra (sè 1) M«n: Tin häc Thêi gian: 45 phót C©u 1: H·y söa l¹i ch­¬ng tr×nh d­íi ®©y cho ®óng ®Ó thùc hiÖn kiÓm tra tÝnh nguyªn tè cña mét sè nguyªn nhËp vµo tõ bµn phÝm. Program BT; Var i, n : integer; kt: Boolean; Begin kt :=true; Write(‘ Nhap n =’); Readln(n); For i :=2 to n div 2 do If n mod i = 0 then kt := false; If kt then write(‘Khong phai la so nguyen to’); Else Write(‘la so nguyen to’); Readln; End. C©u 2: Cho c©u lÖnh: For i := 1 to n do writeln(i*(i+1) div 2); H·y thay thÕ c©u lÖnh trªn b»ng ®o¹n ch­¬ng tr×nh dïng While – do. C©u 3: H·y x©y dùng thuËt gi¶i thùc hiÖn tÝnh tæng cña c¸c phÇn tö n»m trªn ®­êng chÐo chÝnh vµ ®­êng chÐo phô cña mét ma trËn A kÝch th­íc n x n (víi n nhËp vµo tõ bµn phÝm). ®Ò kiÓm tra (sè 2) M«n: Tin häc Thêi gian: 45 phót C©u 1: C©u lÖnh nµo trong c¸c c©u lÖnh sau kh«ng dïng ®Ó g¸n gi¸ trÞ cho tr­êng cña b¶n ghi A? (víi b¶n ghi A cã 3 tr­êng lµ Hoten, lop, diem). A.ten :=’Nguyen Van A’; A.lop = ‘11T’; Readln(A.diem); S := A.diem; C©u 2: Cã thÓ thay thÕ m¶ng mét chiÒu n phÇn tö, mçi phÇn tö lµ mét b¶n ghi cã hai tr­êng b»ng m¶ng hai chiÒu cã n dßng vµ hai cét ®­îc kh«ng? T¹i sao? C©u 3: ViÕt ch­¬ng tr×nh t¹o mét m¶ng gåm n phÇn ti]; cal, ®o¹n ch­¬ng tr×nh sau thùc hiÖn viÖc nµo trong c¸c viÖc sau: víi b¶n ghi A cã 3 tr­êng lµ Hotenö. Mçi phÇn tö lµ mét b¶n ghi gåm c¸c tr­êng: hä tªn, ®iÓm to¸n, ®iÓm lý, ®iÓm tin, tæng ®iÓm. Trong ®ã: Tæng ®iÓm = ®iÓm to¸n + ®iÓm lý + ®iÓm tin. H·y t×m ng­êi cã tæng ®iÓm lín nhÊt, in ra néi dung cña m¶ng vµ ng­êi cã tæng ®iÓm lín nhÊt lªn mµn h×nh. Tµi liÖu tham kh¶o B¸o Tin häc vµ Nhµ tr­êng. §inh H¶i TruyÒn (1998), H×nh thµnh vµ ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh th«ng qua d¹y häc c¸c ph©n m«n To¸n, LuËn v¨n th¹c sü khoa häc gi¸o dôc. Tr­¬ng Träng CÇn (2003), Lý luËn d¹y häc Tin häc ë tr­êng Phæ th«ng, Tñ s¸ch tr­êng §¹i häc Vinh. Hå sÜ §µm, Hå CÈm Hµ, TrÇn §ç Hïng, NguyÔn §øc NghÜa, NguyÔn Thanh Tïng, Ng« ¸nh TuyÕt, S¸ch gi¸o khoa Tin häc 11, NXBGD. Hå sÜ §µm, Hå CÈm Hµ, TrÇn §ç Hïng, NguyÔn §øc NghÜa, NguyÔn Thanh Tïng, Ng« ¸nh TuyÕt, S¸ch gi¸o viªn Tin häc 11, NXBGD. Hå sÜ §µm, Hå CÈm Hµ, TrÇn §ç Hïng, NguyÔn §øc NghÜa, NguyÔn Thanh Tïng, Ng« ¸nh TuyÕt, S¸ch gi¸o khoa Tin häc 10, NXBGD. Hå sÜ §µm, NguyÔn Thanh Tïng, S¸ch Bµi tËp Tin häc 11, NXBGD. Hoµng Chóng (1978), Ph­¬ng ph¸p d¹y häc to¸n häc, NXBGD. Hoµng KiÕm (2001), Gi¶i mét bµi to¸n trªn m¸y tÝnh nh­ thÕ nµo (T1), NXBGD. Hoµng KiÕm, NguyÔn Phóc Tr­êng Sinh (30/4/1994), Algorithms (ThuËt to¸n), Nhµ xuÊt b¶n Khoa Häc vµ Kü ThuËt. NguyÔn B¸ Kim (1999), Häc tËp trong ho¹t ®éng vµ b»ng ho¹t ®éng, NXBGD. NguyÔn Quang UÈn, TrÇn H÷u LuyÕn, TrÇn Quèc Thµnh, T©m lÝ häc ®¹i c­¬ng, NXB §¹i häc Quèc gia. NguyÔn Xu©n Huy (1988), ThuËt to¸n, NXBTK. Phã §øc Hßa, Ng« Quang S¬n, øng dông C«ng nghÖ th«ng tin trong d¹y häc tÝch cùc, NXBGD. Qu¸ch TuÊn Ngäc (1993), Ng«n ng÷ lËp tr×nh Pascal, Tr­êng §¹i häc B¸ch Khoa Hµ Néi. V­¬ng D­¬ng Minh (1996), Ph¸t triÓn t­ duy thuËt gi¶i cña häc sinh trong khi d¹y häc c¸c hÖ thèng sè ë tr­êng phæ th«ng, luËn v¨n tèt nghiÖp th¹c sü. Chu H­¬ng Ly, Gãp phÇn ph¸t triÓn t­ duy thuËt gi¶i cho häc sinh th«ng qua d¹y häc c¸c néi dung ph­¬ng tr×nh, luËn v¨n tèt nghiÖp th¹c sü To¸n häc.