A gi¶i thuËt I / §Þnh nghÜa gi¶i thuËt



tải về 301.83 Kb.
trang1/3
Chuyển đổi dữ liệu05.08.2016
Kích301.83 Kb.
  1   2   3


Tµi liÖu Chuyªn Tin – THPT Ninh Giang

Ch­¬ng I Mét sè kh¸i niÖm më ®Çu


A - Gi¶i thuËt
I / §Þnh nghÜa gi¶i thuËt : Gi¶i thuËt lµ mét hÖ thèng chÆt chÏ vµ râ rµng c¸c qui t¾c nh»m x¸c ®Þnh mét d·y c¸c ®éng t¸c trªn nh÷ng ®èi t­îng, sao cho sau mét sè h÷u h¹n b­íc thùc hiÖn c¸c ®éng t¸c nµy ta thu ®­îc kÕt qu¶ mong muèn.
II / C¸c ®Æc tr­ng cña gi¶i thuËt :

- TÝnh kÕt thóc

- TÝnh râ rµng, chÆt chÏ

- TÝnh phæ dông

- TÝnh hiÖu qu¶
III / BiÓu diÔn gi¶i thuËt :
1 / Ph­¬ng ph¸p dïng ng«n ng÷ liÖt kª c¸c ®éng t¸c :

Trong ®ã cã c¸c ®éng t¸c c¬ b¶n :

+ B¾t ®Çu, th«ng b¸o yªu cÇu

+ LÖnh g¸n trÞ

+ LÖnh thùc hiÖn c¸c phÐp tÝnh sè häc, phÐp tÝnh l«gÝc

+ LÖnh kiÓm tra ®iÒu kiÖn (Thao t¸c so s¸nh)

+ LÖnh chuyÓn kh«ng ®iÒu kiÖn, lÖnh chuyÓn cã ®iÒu kiÖn

+ LÖnh lÆp l¹i

+ KÕt thóc
2 / Ph­¬ng ph¸p s¬ ®å khèi :

+Dïng c¸c h×nh vÏ m« t¶ c¸c ®éng t¸c, c¸c mòi tªn chØ thø tù thùc hiÖn c¸c ®éng t¸c .



.F.


B¾t ®Çu Nhãm lÖnh

2,3 ...


§iÒu

kiÖn
LÖnh 1 KÕt thóc .T.





ThÝ dô vÒ mét sè thuËt gi¶i th­êng gÆp :
1 / Trao ®æi gi¸ trÞ cña 2 biÕn A vµ B th«ng qua biÕn trung gian C :

B0 B¾t ®Çu

B1 NhËp gi¸ trÞ cho A vµ B

B2 C lÊy gi¸ trÞ cña A

B3 A lÊy gi¸ trÞ cña B

B4 B lÊy gi¸ trÞ cña C

B5 Th«ng b¸o kÕt qu¶

B6 KÕt thóc



2 / T×m phÇn tö nhá nhÊt trong d·y sè A 1 ,A 2 ,...,A n :
B0 B¾t ®Çu

B1 NhËp c¸c gi¸ trÞ N , A 1 ,A 2 ,...,A n

B2 G¸n i = 2

B3 NÕu A i < A 1 th× A 1 = A i

B4 T¨ng i lªn 1 ®¬n vÞ

B5 NÕu i<=N th× quay vÒ B3 ( LÖnh lÆp )

B6 NÕu i > N th× A 1 nhá nhÊt

B7 Th«ng b¸o kÕt qu¶

B8 KÕt thóc

3 / DuyÖt d·y A 1 , A 2 , ... , A n xem cã phÇn tö X hay kh«ng :
B0 B¾t ®Çu

B1 NhËp c¸c gi¸ trÞ N, A 1 ,A 2 ,...,A n

B2 G¸n trÞ i=1

B3 NÕu i >N th× chuyÓn sang B6

B4 NÕu A i <> X th× t¨ng i lªn 1 ®¬n vÞ , ChuyÓn vÒ B3

B5 Th«ng b¸o kÕt qu¶ : cã X trong d·y A 1 ,A 2 ,...,A n , råi chuyÓn sang B7

B6 Th«ng b¸o kÕt qu¶ : Kh«ng cã X trong d·y A 1 ,A 2 ,...,A n ,

B7 KÕt thóc ch­¬ng tr×nh .


4 / S¾p xÕp d·y A 1 ,A 2 ,...,A n , theo thø tù t¨ng dÇn :
B0 B¾t ®Çu

B1 NhËp N, A 1 ,A 2 ,...,A n

B2 G¸n i=1

B3 G¸n k=i+1

B4 NÕu A i <= A k th× B6

B5 Thùc hiÖn thuËt to¸n ®æi gi¸ trÞ A i vµ A j

B6 T¨ng j lªn 1 ®¬n vÞ

B7 NÕu j <= N th× chuyÓn vÒ B4

B8 T¨ng i lªn 1 ®¬n vÞ

B9 NÕu i < N th× chuyÓn vÒ B3

B10 Th«ng b¸o d·y ®· s¾p t¨ng lµ A 1 ,A 2 ,...,A n .

B11 KÕt thóc .




5 / ThuËt to¸n Lïa bß vµo chuång : T×m sè nguyªn d­¬ng bÐ nhÊt kh«ng cã trong d·y A 1 ,A 2 ,...,An nguyªn d­¬ng kh«ng lín h¬n 32.000
B0 B¾t ®Çu

B1 NhËp N , A 1 ,A 2 ,...,A n .

B2 Trªn trôc sè ®¸nh dÊu c¸c ®iÓm A 1 ,A 2 ,...,A n .

B3 x = 1


B4 DuyÖt trªn trôc sè, nÕu thÊy x lµ ®iÓm nguyªn ch­a ®­îc ®¸nh dÊu th× chuyÓn sang b­íc B6

B5 T¨ng x lªn 1 ®¬n vÞ

B6 Th«ng b¸o sè nguyªn d­¬ng bÐ nhÊt ch­a cã trong d·y lµ X

B7 KÕt thóc


6 / ThuËt to¸n t×m ¦íc chung lín nhÊt cña 2 sè nguyªn A vµ B :
B0 B¾t ®Çu

B1 NhËp 2 sè nguyªn A vµ B

B2 G¸n A = A , B =  B 

B3 NÕu A =0 vµ B=0 th× B9

B4 NÕu A=0 vµ B <>0 th× B10

B5 NÕu B=0 vµ A <>0 th× B11

B6 G¸n d­ cña phÐp chia A cho B vµo biÕn D ( D = A mod B )

B7 NÕu D = 0 th× chuyÓn sang B10

B8 G¸n A = B ; B = D ; D = A mod B chuyÓn vÒ B7

B9 Th«ng b¸o UCLN kh«ng tån t¹i , chuyÓn vÒ Bkt

B10 Th«ng b¸o kÕt qu¶ : ¦íc sè chung lín nhÊt lµ sè B , chuyÓn vÒ Bkt

B11 Th«ng b¸o kÕt qu¶ : ¦íc sè chung lín nhÊt lµ sè A

Bkt KÕt thóc
7 / ThuËt to¸n t×m sè nguyªn tè :
B0 B¾t ®Çu

B1 NhËp sè N

B2 NÕu N=2 hoÆc N=3 th× chuyÓn sang B8

B3 G¸n i=-1

B4 NÕu (N mod 2 =0) hoÆc (N Mod 3 =0) th× chuyÓn sang B 9

B5 T¨ng i lªn 6 ®¬n vÞ

B6 NÕu (N mod i <> 0) vµ (N mod (i+2) <>0) vµ ( i*i <= N ) chuyÓn sang B 5

B7 NÕu i*i <= N th× chuyÓn sang B 9

B8 Th«ng b¸o : N lµ sè nguyªn tè , chuyÓn tíi B10

B9 Th«ng b¸o : N lµ hîp sè

B10 KÕt thóc ch­¬ng tr×nh

BiÓu diÔn thuËt to¸n: T×m ­íc chung lín nhÊt cña 2 sè nguyªn b»ng s¬ ®å khèi








A :=  A  B¾t §Çu

B :=  B 







A=0 vµ B=0 .T. Kh«ng cã

UCLN


.T.

A<>0 vµ B=0 UCLN lµ A







.T. UCLN lµ B



B<>0 vµ A=0










D := A mod B




.T.


D = 0 KÕt thóc


A := B


B := D

D := A mod B








8 / ThuËt to¸n t×m c¨n bËc 2 cña sè kh«ng ©m A :

B0 B¾t ®Çu

B1 NhËp sè kh«ng ©m A vµ sai sè cho phÐp 

B2 X 0 = 1 ( X lµ gi¸ trÞ gÇn ®óng ®Çu tiªn cña c¨n bËc 2 cña A )

B3 X = X 0

B4 X o = ( X + A/X ) / 2

B5 KiÓm tra :  X 0 - X  <  th× chuyÓn sang B6 cßn kh«ng th× chuyÓn vÒ b­íc B3

B6 Th«ng b¸o c¨n bËc hai cña A lµ X 0

B7 KÕt thóc

9 / T×m nghiÖm gÇn ®óng cña mét ®a thøc F(x) b»ng thuËt to¸n chia ®«i :

B0 B¾t ®Çu

B1 NhËp c¸c hÖ sè cña ®a thøc vµ ®é sai sè cho phÐp 

B2 NhËp 2 gi¸ trÞ A vµ B sao cho F(A) <0 vµ F(B) >0

B3 NÕu  B - A  <  th× chuyÓn tíi B10

B4 X = ( A+B )/2

B5 TÝnh F(X)

B6 NÕu F(X) >0 th× B = X , chuyÓn vÒ B3

B7 NÕu F(X) <0 th× A=X , chuyÓn vÒ B3

B8 NÕu F(X) = 0 th× ChuyÓn tíi B10

B10 Th«ng b¸o nghiÖm lµ X

B11 KÕt thóc



10 / ThuËt to¸n Greedy Algorithm víi bµi to¸n t« mµu
Bµi to¸n : Cho tËp n ®iÓm gäi lµ tËp G , c¸c ®iÓm nµy ®­îc ®¸nh sè tõ 1 ®Õn N vµ ®­îc nèi víi nhau bëi mét sè ®o¹n th¼ng . H·y t« mµu cho c¸c ®iÓm theo nguyªn t¾c : 2 ®iÓm cã ®o¹n th¼ng nèi chóng ph¶i t« b»ng 2 mµu kh¸c nhau . Nªu c¸ch t« mµu cho c¸c ®iÓm sao cho cµng dïng Ýt mµu cµng tèt .

Gîi ý x©y dùng thuËt to¸n : CÇn tæ chøc 2 tËp : TËp ®iÓm ®· t« mµu D vµ tËp ®iÓm ch­a t« mµu C .Mçi lÇn cã 1 ®Ønh ®­îc t« mµu th× kÕt n¹p thªm ®Ønh ®ã vµo D , tËp C lo¹i trõ ®Ønh ®ã . Dïng mµu 1 t« cho ®Ønh 1 . Sè l­îng lín nhÊt c¸c mµu ®· dïng lµ MD=1. Chän ®Ønh i ch­a t« mµu , cho tËp mµu T lµ rçng , t×m tÊt c¶ c¸c ®Ønh k nèi víi i , nÕu ®Ønh k ®· ®­îc t« mµu th× ghi l¹i mµu cña ®Ønh k vµo tËp mµu T , so T víi tËp mµu ®· dïng TMD gåm c¸c mµu tõ 1 tíi MD , nÕu cã mµu cña TMD kh«ng thuéc T th× chän nã lµm mµu cña ®Ønh i , ng­îc l¹i ph¶i chän mµu MD+1 lµm mµu cho ®Ønh i ; t¨ng MD lªn 1 ®¬n vÞ ; tho¸t khái viÖc chän mµu cho ®Ønh i . Qu¸ tr×nh tiÕp tôc cho ®Õn khi tÊt c¶ c¸c ®Ønh ®Òu ®­îc t« mµu
Râ rµng thuËt to¸n trªn ®· t×m mäi kh¶ n¨ng tèt nhÊt ®Ó g¸n mµu cho 1 ®Ønh . Song lêi gi¶i theo thuËt to¸n nµy ch­a tèi ­u ( Ch­a lµ lêi gi¶i tèt nhÊt ) v× viÖc chän mµu tèt nhÊt cho 1 ®Ønh i ch­a ch¾c b¶o ®¶m cã lîi cho viÖc chän mµu cña c¸c ®Ønh tiÕp sau i

Sau nµy chóng ta sÏ ®Ò cËp tíi mét thuËt to¸n kh¸c cã tÝnh tèi ­u ®Ó gi¶i bµi to¸n t« mµu nµy .



11 / T×m kiÕm nhÞ ph©n trªn m¶ng ®· ®­îc s¾p thø tù

B0 B¾t ®Çu

B1 NhËp sè X vµ d·y A gåm N phÇn tö

B2 G¸n ®Çu := 1 ; cuèi := N

B3 KiÓm tra ®Çu <= cuèi nÕu sai th× chuyÓn vÒ B 8

B4 gi÷a := ( ®Çu + cuèi ) div 2

B5 NÕu X > A[gi÷a] th× ®Çu := gi÷a +1

B6 NÕu X < A[gi÷a] th× cuèi := gi÷a -1

B7 NÕu X= A[gi÷a] th× cuèi := -1

B8 NÕu cuèi = -1 th× th«ng b¸o cã X trong m¶ng ,cßn ng­îc l¹i th× th«ng b¸o kh«ng cã X trong m¶ng

B9 KÕt thóc .
12 / S¾p xÕp gän tõng B¨ng víi thao t¸c ®æi chç trùc tiÕp 2 phÇn tö :
Bµi to¸n : Cho d·y sè gåm N sè , chØ gåm sè 1,2,3 (1<=N<=1000). Mét thao t¸c ®æi chç gi÷a 2 phÇn tö cña d·y lµ trao ®æi trùc tiÕp gi¸ trÞ 2 phÇn tö nµy cho nhau .B»ng sè Ýt nhÊt c¸c thao t¸c ®æi chç , h·y s¾p d·y thµnh d·y kh«ng gi¶m .
Gîi ý :

§Õm sè sè 1 cña d·y lµ s1 , sè sè 2 lµ s2 ; ®Æt T2=s1+1,T3 = s1+ s2 + 1 , gäi d·y tõ vÞ trÝ 1 ®Õn vÞ trÝ T2-1 lµ b¨ng 1, tõ T2 ®Õn T3-1 lµ b¨ng 2 , cßn l¹i tõ T3 ®Õn N lµ b¨ng 3

Muèn cã ph­¬ng ¸n s¾p tèt nhÊt , ta chia c¸c thao t¸c thµnh 3 lo¹i cã thø tù ­u tiªn :

Lo¹i 1 : Thao t¸c tèt : ®æi sè 1 ë b¨ng 2 cho sè 2 ë b¨ng 1 , hoÆc ®æi sè 1 ë b¨ng 3 cho sè 3 ë b¨ng 1

Lo¹i 2 : Thao t¸c b¾t buéc : x¶y ra trong hoµn c¶nh kh«ng cßn c¸ch gi¶i quyÕt kh¸c n÷a : ThÝ dô nh­ ë b¨ng 2 kh«ng cßn sè 1 , chØ cßn sè 1 ë b¨ng 3 , trong tr­êng hîp nµy ®µnh ph¶i ®æi sè 2 ë b¨ng 1 cho sè 1 ë b¨ng 3 ; hoÆc nh­ ë b¨ng 3 kh«ng cßn sè 1 , chØ cßn sè 1 ë b¨ng 2 , trong tr­êng hîp nµy ®µnh ph¶i ®æi sè 3 ë b¨ng 1 cho sè 1 ë b¨ng 2 ;

Lo¹i 3 : Thao t¸c cuèi cïng : Lµ nh÷ng thao t¸c cßn l¹i , ph¶i hoµn thµnh nèt,mang tÝnh hiÓn nhiªn vÒ c¸ch thøc thùc hiÖn , thø tù thùc hiÖn kh«ng ¶nh h­ëng sù tèi ­u . ThÝ dô : Khi ®· xÕp xong B¨ng 1 , do ®é dµi c¸c b¨ng ®· tÝnh to¸n s½n nªn cã bao nhiªu sè 3 trong b¨ng 2 th× còng cßn bÊy nhiªu sè 2 trong b¨ng 3 .MÆt kh¸c thø tù trong 1 b¨ng kh«ng quan träng nªn cã thÓ thùc hiÖn c¸c thao t¸c ®æi chç hoµn toµn tuú ý cho c¸c cÆp (sè 3 trong b¨ng 2 - sè 2 trong b¨ng 3 )
B0 B¾t ®Çu

B1 NhËp N vµ d·y A(N) ;

B2 i := 1

B3 NÕu i > S1 th× vÒ B11

B4 NÕu (A[i] = 1 ) th× i:=i+1 vµ vÒ B3

B5 TÜm vÞ trÝ sè 1 trong b¨ng 2 gäi lµ vÞ trÝ x (kh«ng cã th× x=0)

TÜm vÞ trÝ sè 1 trong b¨ng 3 gäi lµ vÞ trÝ y (kh«ng cã th× y=0)

B6 NÕu x=0 vµ y = 0 th× B11

B7 NÕu A[i] =2 th× B9

B8 NÕu A[i] =3 th× B10

B9 NÕu x>0 th× (®æi A[i] vµ A[x] ; t¨ng i := i+1 ; vÒ B3 ) cßn kh«ng ( x=0 , y>0) th× (®æi A[i] víi A[y]; t¨ng i := i+1 ; vÒ B3 )

B10 NÕu y>0 th× (®æi A[i] vµ A[y] ; t¨ng i := i+1 ; vÒ B3 ) cßn kh«ng ( y=0 , x>0) th× (®æi A[i] víi A[x]; t¨ng i := i+1 ; vÒ B3 )

B11 (§· xong b¨ng 1), i = T2

B12 NÕu i>T2-1 th× tíi B15

B12 NÕu A[i]=2 th× i:=i +1 vµ vÒ B12

B13 T×m vÞ trÝ sè 2 trong b¨ng 3 , gäi vÞ trÝ nµy lµ z

B14 §æi A[i] vµ A[z] ; t¨ng i := i+1 , vÒ B12

B15 HiÖn d·y ®· xÕp t¨ng

B16 KÕt thóc

B kh¸i niÖm s¬ gi¶n vÒ kiÓu d÷ liÖu


C¸c th«ng tin trong thùc tÕ cÇn xö lý rÊt ®a d¹ng. CÇn m« h×nh ho¸ c¸c th«ng tin nµy ®Ó viÖc qu¶n lý vµ xö lý nã thuËn lîi . Mäi ng«n ng÷ lËp tr×nh ®Òu x©y dùng mét sè kiÓu d÷ liÖu c¬ së , vµ víi ph­¬ng tiÖn cña ng«n ng÷ nµy cã thÓ t¹o thµnh nh÷ng kiÓu d÷ liÖu phøc t¹p h¬n tõ c¸c kiÓu c¬ së ( ta nãi ng«n ng÷ nµy cã tÝnh cÊu tróc trong tæ chøc d÷ liÖu ).

ThÝ dô trong ng«n ng÷ Pascan cã mét sè kiÓu d÷ liÖu c¬ së :

KiÓu sè nguyªn ( Integer ), kiÓu sè thùc ( Real ), kiÓu kÝ tù ( Char ), kiÓu l«gÝc (Boolean), kiÓu v« h­íng liÖt kª ( Enumerated scalar ) , kiÓu ®o¹n con ( Subrange ) , kiÓu x©u kÝ tù ( String ) .

Trong Pascan cßn cã nh÷ng kiÓu d÷ liÖu cã cÊu tróc : KiÓu m¶ng ( Array ), kiÓu tËp hîp (Set of ...), kiÓu b¶n ghi ( Record ) , kiÓu File , kiÓu con trá ...vµ nh÷ng kiÓu d÷ liÖu phøc hîp nh­ : KiÓu danh s¸ch , kiÓu Stack , kiÓu Queue , kiÓu ®å thÞ , kiÓu c©y ...

ThÝ dô ®Ó biÓu diÔn th«ng tin vÒ ®iÓm sè c¸c m«n To¸n , Lý ,Ho¸ cña 1 líp häc cã thÓ tæ chøc trªn kiÓu M¶ng cã c¸c phÇn tö lµ c¸c Record nh­ sau :

Type Hocsinh = Record

stt : Byte ;

Hoten : String;

Nam_nu : Boolean;

Toan,Ly,Hoa , Tb : Real;

End;
Lophoc = Array[1..50] of Hocsinh;


C - C¸c cÊu tróc ®iÒu khiÓn


Ng«n ng÷ lËp tr×nh cßn cung cÊp cho ng­êi lËp tr×nh nh÷ng c«ng cô diÔn ®¹t thuËt to¸n ®ã lµ c¸c cÊu tróc ®iÒu khiÓn ( Control Struture ) . C¸c cÊu tróc ®iÒu khiÓn c¬ b¶n lµ :

1 / PhÐp g¸n ( Assignment )

2 / CÊu tróc tuÇn tù ( Sequential )

3 / CÊu tróc lùa chän rÏ nh¸nh ( Selection )

4 / CÊu tróc lÆp cã ®iÒu kiÖn vµ kh«ng ®iÒu kiÖn ( Iteration )

* PhÐp g¸n

PhÐp g¸n lµ phÐp t¹o gi¸ trÞ míi cho mét vïng nhí cña m¸y tÝnh , vïng nhí nµy ®· ®­îc cÊp ph¸t cho mét biÕn nµo ®ã do ng­êi lËp tr×nh yªu cÇu .




LÖnh : BiÕn := BiÓu thøc


Chó ý : KiÓu d÷ liÖu cña biÕn vµ biÓu thøc ph¶i nh­ nhau .
* CÊu tróc tuÇn tù :

Trong ch­¬ng tr×nh c¸c lÖnh ®­îc viÕt theo thø tù tõ trªn xuèng d­íi . Trong ®o¹n lÖnh kh«ng chøa lÖnh rÏ nh¸nh hoÆc lÖnh lÆp sÏ theo nguyªn t¾c thø tù : LÖnh nµo viÕt trªn ®­îc thùc hiÖn tr­íc , viÕt d­íi ®­îc thùc hiÖn sau .


* CÊu tróc rÏ nh¸nh ( Lùa chän )
a) NÕu ®iÒu kiÖn tho¶ m·n th× thùc hiÖn lÖnh 1 cßn kh«ng th× thùc hiÖn lÖnh 2 .

b) NÕu ®iÒu kiÖn tho¶ m·n th× thùc hiÖn lÖnh 1 cßn kh«ng th× chuyÓn xuèng lÖnh tiÕp theo lÖnh 1 .

c)

NÕu biÓu thøc ®iÒu kiÖn nhËn gi¸ trÞ thø 1 th× thùc hiÖn lÖnh 1



NÕu biÓu thøc ®iÒu kiÖn nhËn gi¸ trÞ thø 2 th× thùc hiÖn lÖnh 2

NÕu biÓu thøc ®iÒu kiÖn nhËn gi¸ trÞ thø 3 th× thùc hiÖn lÖnh 3

............................................................................................

NÕu biÓu thøc ®iÒu kiÖn nhËn gi¸ trÞ thø n th× thùc hiÖn lÖnh n


* CÊu tróc LÆp :
a) Lo¹i 1 : Trong khi ®iÒu kiÖn tho¶ m·n th× thùc hiÖn nhãm lÖnh

b) Lo¹i 2 : Thùc hiÖn nhãm lÖnh cho ®Õn khi ®iÒu kiÖn kh«ng ®­îc tho¶ m·n

c) Lo¹i 3 : Thùc hiÖn nhãm lÖnh mét sè lÇn ®Þnh tr­íc

d )Lo¹i 4 : Thùc hiÖn v« h¹n lÇn nhãm lÖnh hoÆc 1 phÇn nhãm lÖnh nÕu kh«ng gÆp lÖnh tho¸t khái vßng lÆp .

D - Yªu cÇu chung khi viÕt ch­¬ng tr×nh
Sau khi c©n nh¾c d÷ liÖu vµ thuËt gi¶i, chuyÓn sang viÕt ch­¬ng tr×nh. Chóng ta cÇn tr¶ lêi l¹i mét lÇn n÷a c¸c c©u hái:

+ Môc ®Ých cña ch­¬ng tr×nh lµ g× ?

+ D÷ liÖu vµ thuËt gi¶i ®· hîp lý ch­a? (C©u hái nµy cßn cÇn tr¶ lêi trong suèt qu¸ tr×nh viÕt vµ c¶i tiÕn ch­¬ng tr×nh)

+ Dµn bµi chung (nh÷ng nÐt lín) cña ch­¬ng tr×nh?

+ T¹i sao l¹i tiÕn hµnh nh­ vËy? Cã thÓ lµm kh¸c ®­îc kh«ng?

Cuèi cïng, b¾t tay vµo viÕt ch­¬ng tr×nh, cÇn tiÕn hµnh c¸c b­íc sau:

1 / NhËp d÷ liÖu. Ph­¬ng ph¸p nhËp ph¶i ®óng yªu cÇu ®Ò ra.

2 / KiÓm tra l¹i d÷ liÖu ®· nhËp, ®iÒu chØnh l¹i b­íc 1 nÕu thÊy cßn sai sãt.

4 / Th«ng b¸o t×nh tr¹ng d÷ liÖu nÕu d÷ liÖu cho cã sai sãt.

5 / ViÕt ch­¬ng tr×nh chÝnh gåm c¸c c«ng viÖc nµo. Chó ý t¹o Menu ®Ó tr×nh bµy giao diÖn gi÷a ng­êi sö dông vµ kÕt qu¶ ch­¬ng tr×nh trªn mµn h×nh.

6 / Theo tõng phÇn viÖc ®· x¸c ®Þnh trong ch­¬ng tr×nh chÝnh, lÇn l­ît viÕt c¸c ch­¬ng tr×nh con (Procedure vµ Function). ViÕt ®­îc ch­¬ng tr×nh con nµo cÇn thö nghiÖm ngay ch­¬ng tr×nh con ®ã .

7 / §­a th«ng tin ra ( kÕt qu¶ cña bµi to¸n ) theo ®óng yªu cÇu ®Ò ra .

8 / Thö nghiÖm l¹i víi d÷ liÖu nhá sau ®ã lµ c¸c d÷ liÖu cã gi¸ trÞ ®Æc biÖt , råi ®Õn bé d÷ liÖu lín h¬n nh­ng ®· biÕt truíc kÕt qu¶ , cuèi cïng nÕu cã ®iÒu kiÖn cÇn so s¸nh kÕt qu¶ cña c¸c c¸ch , c¸c bµi gi¶i kh¸c nhau cña bµi to¸n nµy.

9 / C¶i tiÕn l¹i ch­¬ng tr×nh. Chó ý l­u gi÷ l¹i ch­¬ng tr×nh cò tr­íc khi c¶i tiÕn.

10 / L­u gi÷ ch­¬ng tr×nh ®óng qui c¸ch , b¶o ®¶m sau nµy ch­¬ng tr×nh cã thÓ ch¹y l¹i nh­ lÇn ®· thö nghiÖm thµnh c«ng nhÊt . Nh÷ng chi tiÕt cuèi cïng võa c¶i tiÕn nh­ng kh«ng thµnh c«ng , ph¶i lo¹i bá khái ch­¬ng tr×nh .

ViÕt ch­¬ng tr×nh víi tinh thÇn nh­ trªn , cã thÓ sÏ t¹o hiÖu qu¶ tèt cho ch­¬ng tr×nh hiÖn thêi vµ t¨ng c­êng phong c¸ch lËp tr×nh s¸ng sña râ rµng cña tõng ng­êi sau nµy .



ThÝ dô mét ch­¬ng tr×nh viÕt b»ng Turbo Pascan
( §Ò bµi : NhËp tõ bµn phÝm sè nguyªn d­¬ng N vµ gi¸ trÞ c¸c phÇn tö cña d·y A gåm N sè nguyªn . S¾p xÕp l¹i c¸c phÇn tö cña d·y A theo thø tù t¨ng dÇn )
(* PhÇn khai b¸o *)

Uses Crt;

Const Max = 10;

Var N : Integer;

A : Array[1..Max] of Integer;
(* Ch­¬ng tr×nh con : nhËp N vµ d·y A(N ) gåm N sè nguyªn *)

Procedure Nhap;

Var i : Integer;

Begin


Repeat

Write('Nhap N = ');

{$I-} Readln(N); {$I+}

Until ( IoResult =0 ) and (N>0);

For i:=1 to N do

Repeat


Write('A[',i:2,'] = ');

{$I-} Readln(A[i]); {$I+}

Until (IoResult =0 ) ;

End;


(* Ch­¬ng tr×nh con : hiÖn trªn mµn h×nh d·y A(N) *)

Procedure Hien;

Var i : Integer;

Begin


For i:=1 to N do Write(A[i]:5);

Writeln;


End;
(* Ch­¬ng tr×nh con tr¸o gi¸ trÞ cña 2 biÕn x vµ y cho nhau *)

Procedure Traococ( Var x,y : Integer);

Var c : Integer;

Begin


c := x;

x := y;


y := c;

End;
(* Ch­¬ng tr×nh con : s¾p t¨ng d·y *)

Procedure Sap;

Var i,j : Integer;

Begin

For i:=1 to N-1 do



For j:=i+1 to N do

If A[i] > A[j] then Traococ(A[i],A[j]);

End;
(* Ch­¬ng tr×nh chÝnh *)

BEGIN


Clrscr;

Nhap;


Hien;

Sap;


Hien;

Readln;


END.

Phô lôc ch­¬ng 1


Mét sè ch­¬ng tr×nh

minh ho¹ thuËt to¸n nªu ë trang 5 - 7


{ Bµi 1 ThuËt to¸n tr¸o cèc }
Uses Crt;

Var A,B,C : Integer;

Begin

Clrscr;


Write('Nhap so A : ');

Readln(A);

Write('Nhap so B : ');

Readln(B);

C := A;

A := B;


B := C;

Writeln('A = ',A:5,#13#10'B = ',B:5);

Readln;

End.
{ Bµi 2 T×m phÇn tö nhá nhÊt trong d·y }


Uses Crt;

Const Max = 10;

Var j : Integer;

A : Array[1 .. Max] of Integer;

Begin

Clrscr;


For j:=1 to Max do

Begin


Write('A[',j:2,'] = ');

Readln(A[j]);

End;

j := 2;


Repeat

If A[j] < A[1] then A[1] := A[j];

Inc(j);

Until j>Max;



Writeln('So nho nhat la ',A[1]);

Readln;


End.
{ Bµi 3 DuyÖt d·y theo thø tù , t×m phÇn tö X }
Uses Crt;

Const Max = 10;

Var i,X : Integer;

A : Array[1..Max] of Integer;

Procedure Baoco;

Begin


Writeln(X,' co trong day ');

Readln;


Halt;

End;


Procedure Khongco;

Begin


Writeln(X,' khong co trong day ');

Readln;


End;

Begin


Clrscr;

Write('Nhap X = '); Readln(X);

Writeln('Nhap day A ');

For i:=1 to Max do

Begin

Write('A[',i:2,'] = ');



Readln(A[i]);

End;


i := 1;

While i<= Max do

Begin

If A[i] = X then Baoco { Trong Baoco co lenh Halt }



Else Inc(i);

End;


If i>max then Khongco;

End.


{ Bµi 4 S¾p xÕp d·y b»ng ph­¬ng ph¸p Næi bät - Ph­¬ng ph¸p s¾p xÕp kÐm nhÊt }
Uses Crt;

Const Max = 10;

Var N : Integer;

A : Array[1..Max] of Integer;

Procedure Nhap;

Var i : Integer;

Begin

Write('Nhap N = ');



Readln(N);

For i:=1 to N do

Begin

Write('A[',i:2,'] = ');



Readln(A[i]);

End;


End;

Procedure Hien;

Var i : Integer;

Begin


For i:=1 to N do

Write(A[i]:5);

Writeln;

End;


Procedure Traococ( Var x,y : Integer);

Var c : Integer;

Begin

c := x;


x := y;

y := c;


End;
Procedure KieuFor;

Var i,j : Integer;

Begin

For i:=1 to N-1 do



For j:=i+1 to N do

If A[i] > A[j] then Traococ(A[i],A[j]);

Hien;

End;


BEGIN

Clrscr;


Nhap;

KieuFor;


Readln;

END.
{ Bµi 5 Ph­¬ng ph¸p Lïa bß vµo chuång ! }


Uses Crt;

Const Max = 32000;

M = 10;

Var x,N : Integer;



A : Array[1..M] of Integer;

B : Array[1..Max] of Boolean;

Procedure Nhap;

Var i : Integer;

Ok : Boolean;

Begin


Write('Nhap N = ');

Repeat


{$I-} Readln(N); {$I+}

Until (IoResult=0) and (N<=10) and (N>0);

Writeln('Nhap mang ',N,' so nguyen duong : ');

For i:=1 to N do

Begin

Write('A[',i:2,'] = ');



Repeat

Readln(A[i]);

Ok := (IoResult=0) and (A[i]<=32000) and (A[i]>0);

Until Ok;

End;

End;


Procedure Thuchien;

Var i,j : Integer;

Begin

FillChar(B,Sizeof(B),False);



For i:=1 to Max do

For j:= 1 to N do

If i=A[j] then B[i]:= true;

For x:=1 to Max do

If B[x]=False then

Begin


Write('So nguyen duong nho nhat khong thuoc mang: ');

Writeln(x);

Readln;

Halt;


End;

End;


BEGIN

Clrscr;


Nhap;

Thuchien;

Readln;

END.
{ Bµi 6 ThuËt to¸n t×m USCLN cña 2 sè }


Uses Crt;

Var A,B,La,Lb : Integer;

Procedure Nhap(i : Char;Var x : Integer);

Var Ok : Boolean;

Begin

Write('Nhap so nguyen ',i,' = ');



Repeat

{$I-} Readln(x); {$I+}

Ok := (IoResult=0);

Until Ok;

End;

Procedure Hien(x : Integer);



Begin

Write('UCLN(',LA:5,',',LB:5,') = ',x);

Readln;

Halt;


End;

Procedure Hien2;

Begin

Writeln(' Moi so nguyen deu = UCLN(0, 0) ');



Readln;

Halt;


End;

Procedure Tim;

Var D : Integer;

Begin


A := Abs(A);

B := Abs(B);

If (A=0) and (B<>0) then Hien(B);

If (B=0) and (A<>0) then Hien(A);

If (A=0) and (B=0) then Hien2;

D := A mod B;

While D<>0 do { Chu y neu dung Repeat can tranh chia cho 0 }

Begin


A := B;

B := D;


D := A mod B;

End;


Hien(B);

End;


BEGIN

Clrscr;


Nhap('A',A);

Nhap('B',B);

La := A;

Lb := B;


Tim;

Readln;


END.

{ Bµi 7 T×m sè nguyªn tè - ThuËt to¸n tèt }
Uses Crt,dos;

Const Max = 400000; { 192/100 giay --> 50000 & 2269/100 giay --> 400000 }

Var N , i : LongInt;

h,m,s,p : Word;

T : LongInt;

Begin


Clrscr;

Gettime(h,m,s,p);

t := 6000*m + 100*s +p;

Write(2:8);

Write(3:8);

For N := 5 to Max do

If (N mod 2 <> 0) and (N mod 3 <> 0) then

Begin


i := -1;

Repeat


Inc(i,6);

Until (N mod i =0) or (N mod (i+2)=0) or (sqr(i)>N);

If sqr(i)>N then Write(N:8);

End;


Gettime(h,m,s,p);

t := 6000*m + 100*s +p - t;

Writeln;

Writeln('Mat thoi gian la : ', T);

Readln;
End.
{ Bµi 8 T×m c¨n bËc hai cña 1 sè }
Uses Crt;

Var A,E,X0 : Real;

Procedure Baoloi;

Begin


Writeln('Loi du lieu nhap : ');

Readln;


Halt;

End;


Procedure Nhap;

Var Ok : Boolean;

Begin

Write('Nhap so trong can bac 2 : ');



Repeat

{$I-} Readln(A); {$I+}

Ok := (IoResult=0) and (A>=0);

If not Ok then BaoLoi;

Until Ok;

Write('Nhap do chinh xac : ');

Repeat

{$I-} Readln(E); {$I+}



Ok := (IoResult=0) and (E>=0.000001) ;

If not Ok then BaoLoi;

Until Ok;

End;


Procedure Lam;

Var X : Real;

Begin

X0 := 1;


Repeat

X := X0;


X0 := (X + A/X)/2;

Until Abs(X0-X) < E;

End;

Procedure Hien;



Begin

Writeln('can bac 2 cua ',A:8:2,' la ',X0:8:2,' voi do chinh xac ',E:8:6);

End;

BEGIN


Clrscr;

Nhap;


Lam;

Hien;


Readln;

END.
{ Bµi 9 T×m nghiÖm ®a thøc b»ng thuËt to¸n chia ®«i cung }


Uses Crt;

Const Max = 10;

e = 0.0001;

Type Mang = Array[1..Max] of Real;

Var A : Mang;

x1,x2 : Real;

N : Byte;

Procedure Nhap1;

Var i : Byte;

Begin


Clrscr;

Write('N = ');

Repeat

{$I-} Readln(N); {$I+}



Until (IoResult=0) and (N>0) and (N

For i:=N downto 0 do

Repeat

Write('A[',i:2,']=');



{$I-} Readln(A[i]); {$I+}

Until (IoResult=0);

End;

Function F(x:Real):Real;



Var i : Byte;

p : Real;

Begin

p := A[n]*x+A[n-1];



For i:=2 to n do

p := p*x+A[n-i];

F := p;

End;


Procedure Nhap2;

Var dem : Byte;

Ok : Boolean;

Begin


Writeln;

dem := 0;

Repeat

Write('Nhap x1 : F(x1)<0 x1 = ');



{$I-} Readln(x1); {$I+}

Ok := (IoResult=0) and (F(x1)<0);

If not Ok then

Begin


Inc(dem);

Writeln('Nhap sai yeu cau lan thu ',dem);

End;

Until Ok or (dem =3);



Writeln;

dem := 0;

Repeat

Write('Nhap x2 : F(x2)>0 x2 = ');



{$I-} Readln(x2); {$I+}

Ok := (IoResult=0) and (F(x2)>0);

If not Ok then

Begin


Inc(dem);

Writeln('Nhap sai yeu cau lan thu ',dem);

End;

Until Ok or (dem =3);



End;

Procedure Timnghiem;

Var x,p : Real;

Begin


x := (x1+x2)/2;

p := F(x);

While Abs(p) > e do

Begin


If p>0 then x2 := x;

If p<0 then x1 := x;

If p = 0 then

Begin


Write('Nghiem dung la x= ',x:10:4);

Readln;


Halt;

End;


x := (x1+x2)/2;

p := F(x);

End;

Writeln('nghiem gan dung la ',x:10:4);



End;

BEGIN


Nhap1;

Nhap2;


Timnghiem;

Readln


END.

1 -3 0 2


x1= 2 x2=4 --> x=2.732
{ Bµi 10 T« mµu b»ng ph­¬ng ph¸p Greedy }
Uses Crt;

Const Max = 14;

Var A : Array[1..Max,1..Max] of 0..1;

Mau : Array[1..Max] of Byte;

N : Integer;

dato,chuato : Set of Byte;

Procedure Nhap;

Var i,j : Integer;

F : Text;

Begin


FillChar(A,Sizeof(A),0);

Assign(F,'Tomau.txt');

Reset(F);

Readln(F,N);

While not Eof(F) do

Begin


Read(F,i);Readln(F,j);

A[i,j] := 1;

A[j,i] := 1;

End;


End;

Procedure Hien;

Var i,j : Integer;

Begin


Writeln;

For i:=1 to N do

Begin

For j:=1 to N do Write(A[i,j]:4);



Writeln;

End;


End;

Procedure Thongbao;

var i : Integer;

Begin


Write('Da to mau : ');

For i:=1 to N do

If i in dato then Write(i:4);

Writeln;


Write('Chua to mau : ');

For i:=1 to N do

If i in chuato then Write(i:4);

Writeln;


Writeln;

Write('Danh sach dinh : ');

For i:=1 to N do

Write(i:4);Writeln;

Write('Mau da to la : ');

For i:=1 to N do

Write(Mau[i]:4);

End;


Function Kt(x,m : Integer): Boolean;

Var i : Integer;

Begin

Kt := False;



For i:=1 to N do

If (A[x,i]=1) and (m=Mau[i]) then Exit;

Kt := True;

End;


Procedure Greedy;

Var i : Integer;

Lienquan : Array[1.. Max] of Byte;

Mp,Maxm,j : Integer;

Begin

Dato := [];



Chuato :=[];

For i:=1 to N do chuato := chuato +[i];

Mau[1]:=1;

dato:= dato+[1];

chuato := chuato-[1];

Maxm := 1;

For i:=1 to N do

Begin


If i in chuato then

Begin


FillChar(Lienquan,Sizeof(Lienquan),0);

For j:=1 to N do

If (A[i,j]=1) and (Mau[j]>0) then

Lienquan[Mau[j]] := 1;

For j:=1 to N do

If Lienquan[j]=0 then

Begin

mp := j;


j := N;

End;


If mp<=N then

Begin


Mau[i] := mp;

dato := dato + [i];

Chuato := chuato -[i];

End


Else

Begin


Inc(Maxm);

Mau[i]:=Maxm ;

dato := dato + [i];

Chuato := chuato -[i];

End;

End;


End;

End;


BEGIN

Clrscr;


Nhap;

Hien;


Greedy;

Thongbao;

Readln;

END.
{Bµi 11 : T×m phÇn tö X trong d·y s¾p thø tù b»ng ph­¬ng ph¸p chia ®«i }


Uses Crt;

Const Max = 1000;

Var A : Array[1.. Max] of Integer;

N,X : Integer;

Procedure Nhap;

Var i : Integer;

Begin

Write('So phan tu cua mang : N = ');



Readln(N);

Randomize;

For i:=1 to N do A[i] := Random(100);

End;


Procedure Hien;

Var i : Integer;

Begin

For i:=1 to N do



Begin

If i mod 480 =0 then Readln;

Write(A[i]:4);

End;


End;

Procedure PPchiadoi;

Procedure Sap;

Var i,j,c : Integer;

Begin

For i:=1 to N-1 do



For j:=i+1 to N do

If A[j]

Begin

c := A[i];



A[i] := A[j];

A[j] := c;

End;

End;


Procedure NhapN;

Begin


Writeln;

Write('Nhap so X can tim trong mang , X = ');

Readln(X);

End;


Procedure Thuchien;

Var g,d,c : Integer;

Begin

d := 1;


c := N;

While d<=c do

Begin

g := (d+c) div 2;



If X > A[g] then d := g+1;

If X < A[g] then c := g-1;

If X = A[g] then c := -1

End;


If c = -1 then Writeln('Co ',x:4,' trong mang ') Else

Writeln('Khong co ' ,x:4,' trong mang ');

End;

Begin


Sap;

Writeln;


Hien;

NhapN;


Thuchien;

End;


BEGIN

Clrscr;


Nhap;

Hien;


PPchiadoi;

Readln;


END.

Ch­¬ng 2 Lµm quen víi PAScaL

A - B¾t ®Çu tõ kh¸i niÖm
I / Giíi thiÖu vÒ ng«n ng÷ PASCAL :
PASCAL lµ mét trong nh÷ng ng«n ng÷ lËp tr×nh cÊp cao ®­îc gi¸o s­ Niklaus Wirth ë tr­êng §¹i häc Zurich ( Thuþ sÜ ) thiÕt kÕ vµ c«ng bè vµo n¨m 1971 . ( B¶n tãm t¾t chØ cã 29 trang ! ) Sau ®­îc söa ®æi trong n¨m 1972 vµ ngµy cµng ®ù¬c chuÈn ho¸ , ®Õn nay trë thµnh ng«n ng÷ phæ cËp trong d¹y lËp tr×nh còng nh­ ®­îc øng dông réng r·i trªn c¸c m¸y vi tÝnh .
Ng«n ng÷ Pascal nhanh chãng cã ¶nh h­ëng s©u réng vµ chiÕm ®­îc c¶m t×nh cña nh÷ng ng­êi lËp tr×nh v× nhiÒu nguyªn nh©n ; trong ®ã cã nguyªn nh©n ®¸ng kÓ lµ tÝnh cÊu tróc chÆt chÏ vµ khoa häc . TÝnh cÊu tróc cña ng«n ng÷ nµy thÓ hiÖn trªn 3 mÆt :
1) Tæ chøc d÷ liÖu cã tÝnh cÊu tróc .

2) X©y dùng ®­îc ®Çy ®ñ c¸c cÊu tróc ®iÒu khiÓn ®Ó thùc hiÖn gi¶i thuËt

3) T¹o cho ch­¬ng tr×nh kh¶ n¨ng cÊu tróc .
V× vËy khi lËp tr×nh , cÇn cè g¾ng khai th¸c hÕt søc m¹nh cña ng«n ng÷ nµy vÒ ph­¬ng diÖn cÊu tróc , nh»m ®¹t tíi c¸c bµi gi¶i to¸n cã hiÖu suÊt cao.
II / Nh÷ng kh¸i niÖm cÇn thiÕt :
1 ) C¸c KÝ tù :

C¸c kÝ tù trong ng«n ng÷ Pascal gåm :

+ 26 ch÷ c¸i la tinh hoa : A, B,... Z ( m· sè tõ 65 tíi 90 trong b¶ng m· ASC I I )

+ 26 ch÷ c¸i la tinh th­êng a,b... z ( m· sè 97 --> 122 )

+ KÝ tù g¹ch nèi : _ ( m· sè 95 )

+ 10 kÝ tù ch÷ sè : 0,1,2,...,9 (m· sè 48 --> 57 )


+ Céng ‘+’ , trõ ‘- ‘ , nh©n ‘*’ , chia ‘ / ’, b»ng nhau ‘ = ‘ , lín h¬n ‘ > ‘ , nhá h¬n ’ < ‘

dÊu më ngoÆc ‘(‘ hoÆc dÊu ®ãng ngoÆc ‘)’

+ C¸c kÝ tù ®Æc biÖt kh¸c :

‘.’ , ‘;’ , ‘:’ , ‘[‘ , ‘ ]’ , ‘{‘ , ‘}’ , ‘? ‘ , ‘! ‘ ,‘ \ ‘ , ‘&’ , ‘%’ , ‘#’ , ‘$’

+ KÝ tù dÊu c¸ch (cßn gäi lµ dÊu trèng - cã m· sè 32 ) T¹o 1 kho¶ng c¸ch b»ng ®é réng chøa 1 kÝ tù , dÊu c¸ch dïng ®Ó ph©n c¸ch 2 tõ .
2) C¸c tõ kho¸ : Lµ c¸c tõ riªng cña Pascan ®· ®­îc x¸c ®Þnh ng÷ nghÜa tr­íc , ng­êi lËp tr×nh ph¶i tu©n theo ng÷ nghÜa nµy , kh«ng ®­îc dïng tõ kho¸ vµo c¸c ®Þnh nghÜa kh¸c
Danh s¸ch c¸c tõ kho¸ :

Program , Begin , End, Procedure , Function , Unit , Implementation , Interface ...

Uses ,Const, Type , Var , Label , Array , String ,Record , Set of ... , File of ...

If ... then ... Else ... , Case ... of ,

For ... to ... do , For ... downto ... do , While ... do , Repeat ... until

With , goto , Exit, Halt ,Forward ,And , or, xor ,not, in , div , mod , SHL ,SHR



3 ) Tªn Lµ d·y c¸c kÝ tù ch÷ c¸i hoÆc ch÷ sèdÊu g¹ch nèi dïng ®Ó x¸c ®Þnh c¸c ®¹i l­îng kh¸c nhau trong ch­¬ng tr×nh .

Qui ®Þnh ®Æt tªn :

+ ChiÒu dµi tèi ®a 127 kÝ tù .

+ Kh«ng ®­îc ®Æt kÝ tù ch÷ sè lµm kÝ tù ®Çu cña tªn .

+ Kh«ng ®­îc ®Æt tªn trïng víi tõ kho¸ .

Nªn ®Æt tªn cã tÝnh gîi nhí ®Ó dÔ theo dâi vµ hiÖu chØnh ch­¬ng tr×nh , kh«ng nªn ®Æt tªn qu¸ dµi vµ trïng víi c¸c tªn chuÈn nªu d­¬Ý ®©y


4) Tªn chuÈn :

Tªn chuÈn lµ nh÷ng tªn ®­îc Pascal ®Æt tr­íc vµ ®Þnh nghÜa s½n .



Danh s¸ch c¸c tªn chuÈn

Boolean , Char , Integer , Real , Byte , Text ...

False , True , MaxInt ,

Abs , Chr , Cos , Sin , Arctan , Eof , Eoln

Exp , Ln , Odd , Ord ,

Round , Trunc , Sqr , Sqrt , Pred , Succ,

Dispose , New , Close,Get , Put , Read , Readln , Write , Writeln , Reset , ReWrite

...


B - C¸c kiÓu d÷ liÖu ®¬n gi¶n vµ phÐp to¸n t­¬ng øng
I / KiÓu sè nguyªn :


Tõ kho¸

Ph¹m vi

Sè byte nhí

Integer

-32768 .. 32767

2 Byte

Byte

0 .. 255

1 Byte

Word

0 .. 65535

2 Byte

ShortInt

-128 .. 127

1 Byte

LongInt

-2147483648.. 2147483647

4 Byte

Nh÷ng qui ®Þnh vÒ kiÓu sè nguyªn :

+ Kh«ng g¸n trÞ v­ît qu¸ ph¹m vi cña kiÓu .

+ C¸c ch÷ sè ph¶i viÕt liÒn nhau

+ Sè ©m : ph¶i ®Æt dÊu trõ ngay s¸t ch÷ sè ®Çu tiªn cña sè

+ Kh«ng ®­îc sö dông dÊu chÊm thËp ph©n .

+ §Ó viÕt sè d­íi d¹ng c¬ sè 16 ( d¹ng Hexa ) ®Æt dÊu $ s¸t ch÷ sè ®Çu .

C¸c phÐp to¸n ( operater ) :

a) PhÐp to¸n sè häc :

Céng : + Cho kÕt qu¶ lµ sè nguyªn

Trõ : - Cho kÕt qu¶ lµ sè nguyªn

Nh©n : * Cho kÕt qu¶ lµ sè nguyªn

Chia : / Cho kÕt qu¶ lµ sè thùc

Div : Cho th­¬ng nguyªn cña phÐp chia

Mod : D­ nguyªn cña phÐp chia .

b) PhÐp to¸n quan hÖ :

= ( b»ng )

> ( lín h¬n )



< ( nhá h¬n )

>= ( Kh«ng nhá thua )



<= ( Kh«ng lín h¬n )

<> ( Kh¸c )

KÕt qu¶ cña c¸c phÐp to¸n quan hÖ lµ KiÓu Boolean ( Cã 2 gi¸ trÞ : True, False)


II / KiÓu thùc :


KiÓu

Ph¹m vi

Sè ch÷ sè cã nghÜa

Sè Byte

Single

1.5E-45 .. 3.4E+38

7-8

4

Real

2.9E-39 .. 1.7E+38

11-12

6

Double

5.0E-324 .. 1.7E+308

15-16

8

Extended

3.4E-4932 .. 1.1E+4932

19-20

10

Comp

-9.2E+18 .. 9.2E+18

19-20

8

+ Trong 4 kiÓu trªn , ph¹m vi ®­îc hiÓu nh­ lµ trÞ tuyÖt ®èi cña ph¹m vi .

+ C¸ch viÕt sè ë cét ph¹m vi lµ c¸ch viÕt ch÷ sè kiÓu ®éng ,

1.5E-45 = 1.5 * 10 -45 ; 3.4E+38 = 3.4 * 10 38

+ KiÓu sè thùc víi mode th­êng dïng lµ Real . Cßn c¸c kiÓu cßn l¹i ph¶i dïng mode 8087 ( §Çu ch­¬ng tr×nh ph¶i cã h­ãng biªn dÞch {$N+}. ) C¸c phÐp to¸n trªn kiÓu sè thùc : Còng cã c¸c phÐp to¸n nh­ kiÓu nguyªn ; nh­ng kh«ng cã phÐp DIV vµ MOD vµ kÕt qu¶ cña mäi phÐp to¸n trªn Real lµ Real ; kÕt qu¶ cña mäi phÐp to¸n trªn Extended lµ Extended
III / KiÓu Boolean :
KiÓu Boolean chØ cã 2 gi¸ trÞ : True vµ False . ( trong ®ã False < True )

Mét gi¸ trÞ kiÓu Boolean chiÕm 1 Byte bé nhí .

C¸c phÐp to¸n l«gic trªn kiÓu Boolean :
PhÐp AND PhÐp OR





True

False

True

True

True

False

True

False







True

False

True

True

False

False

False

False

PhÐp XOR PhÐp NOT





True

False

True

False

True

False

True

False

X = True --> Not ( x ) = False

X = False --> Not ( x) = True

IV / KiÓu KÝ tù : ( KiÓu Char )
Mét kÝ tù chiÕm 1 byte bé nhí .Mçi kÝ tù t­¬ng øng víi 1 m· sè , ghi trong b¶ng m· ASC I I (American Standar Code Information Interchange ). Cã tÊt c¶ 256 kÝ tù ®¸nh sè tõ M· sè 0 tíi m· sè 255 . VËy kiÓu kÝ tù cã 256 gi¸ trÞ . C¸c kÝ tù tõ 0 ®Õn 31 lµ c¸c kÝ tù ®iÒu khiÓn , kh«ng in ra ®­îc , chóng dïng ®Ó ®iÒu khiÓn qu¸ tr×nh vµo , ra c¸c thiÕt bÞ ngo¹i vi

ThÝ dô : KÝ tù cã m· sè 13 b¸o hiÖu hÕt dßng trªn mµn h×nh vµ m¸y in

KÝ tù cã m· sè 10 chuyÓn con trá mµn h×nh xuèng ®Çu dßng d­íi , vµ chuyÓn ®Çu kim in xuèng ®Çu dßng in tiÕp theo .

KÝ tù cã m· sè 7 lµm ph¸t chu«ng kªu . ..



Chó ý :

+ §Ó biÓu diÔn kÝ tù , ph¶i ®Æt kÝ tù trong dÊu nh¸y . ThÝ dô : ‘a’ ‘A’ ‘]’ ... hoÆc dïng hµm Char thÝ dô : Char(97) , Char(65) , Char(93) ... hoÆc dïng kÝ hiÖu #97 , #65 , #93 ...


Sau ®©y lµ 1 ch­¬ng tr×nh nhá hiÖn c¸c kÝ tù vµ m· sè cña chóng lªn mµn h×nh :
Uses crt;

Var i : Byte;

BEGIN

Clrscr;


For i:=33 to 255 do Write(i:4,Char(i):2,#32#32);

Readln;


END.
V / KiÓu X©u kÝ tù : ( KiÓu String )

X©u kÝ tù lµ d·y c¸c kÝ tù ®Æt gi÷a 2 dÊu nh¸y ®¬n . Sè kÝ tù cña x©u kh«ng qu¸ 255 .

C¸c phÐp to¸n trªn x©u kÝ tù sÏ ®Ò cËp ë phÇn sau .Cã thÓ t¹o ra kiÓu x©u kÝ tù cã ®é dµi n ( 1<=n<255) b»ng khai b¸o

Type Tªn_X©u = String[n];

Var Tªn_biÕn : Tªn_x©u;


C - D÷ liÖu kiÓu m¶ng
Khai b¸o m¶ng 1 chiÒu :

+ M¶ng cã N phÇn tö , chØ sè cña c¸c phÇn tö lµ sè nguyªn tõ 1 ®Õn N

Type Tªn_kiÓu = Array[1..N] of ;

Var Tªn_biÕn : Tªn_kiÓu ;

+ M¶ng cã N phÇn tö , chØ sè cña c¸c phÇn tö lµ sè nguyªn tõ -1 ®Õn N-2

Type Tªn_kiÓu = Array[-1..N-2] of ;

+ M¶ng cã 10 phÇn tö , chØ sè cña c¸c phÇn tö lµ kÝ tù tõ A  ®Õn K

Type Tªn_kiÓu = Array[ A .. K] of ;

Khai b¸o m¶ng 2 chiÒu :

+ M¶ng cã N xN phÇn tö , chØ sè cña c¸c phÇn tö lµ cÆp sè nguyªn tõ (i,j)

Type Tªn_kiÓu = Array[1..N,1..N ] of ;



Khai b¸o m¶ng 3 chiÒu :

+ M¶ng cã N xN xN phÇn tö , chØ sè cña c¸c phÇn tö lµ bé 3 sè nguyªn tõ (i,j,k)

Type Tªn_kiÓu = Array[1..N,1..N ,1..N ] of ;


Chó ý :
Mçi phÇn tö thø i cña m¶ng 1 chiÒu ( m¶ng A víi chØ sè nguyªn ch¼ng h¹n ) ®­îc t­¬ng øng víi 1 « nhí trong m¸y Muèn n¹p hoÆc lÊy gi¸ trÞ « nhí ®ã , ph¶i th«ng qua phÇn tö thø i cña m¶ng t­¬ng øng víi « nhí Êy kÝ hiÖu lµ A[i] ,

Mçi phÇn tö cã chØ sè (i,j) cña m¶ng 2 chiÒu ( m¶ng A víi chØ sè lµ cÆp sè nguyªn ch¼ng h¹n ®­îc kÝ hiÖu A[i,j] trong ®ã i lµ chØ sè hµng ,j lµ chØ sè cét


Nh­ vËy viÖc duyÖt c¸c gi¸ trÞ cña c¸c phÇn tö cña m¶ng rÊt dÔ dµng . Song cÇn l­u ý biÕn chØ sè cña m¶ng kh«ng ®­îc v­ît ra ngoµi ph¹m vi ®· khai b¸o . ThÝ dô M¶ng A khai b¸o cã 10 phÇn tö víi chØ sè tõ -5 ®Õn 4 th× kÝ hiÖu A[5] lµ ph¹m lçi .

Nh­îc ®iÓm cña kiÓu m¶ng lµ tèn bé nhí do khai b¸o ban ®Çu ph¶i l­êng tr­íc mäi gi¸ trÞ cña d·y nµo ®ã ®Òu ®­îc ®­a vµo m¶ng , nªn kÝch th­íc m¶ng sÏ lín , nh­ng thùc tÕ cã thÓ kh«ng dïng hÕt c¸c phÇn tö cña m¶ng ®· khai b¸o.


D - Mét sè hµm th«ng dông
1) ABS(x) : gi¸ trÞ tuyÖt ®èi cña x cã kiÓu nh­ x
2) SQR(x) : B×nh ph­¬ng cña x cã kiÓu nh­ x
3) SQRT(x) : C¨n bËc hai cña x cã kiÓu Real
4) Sin(x) : sin cña x cã kiÓu Real
5) Cos(x) : c«sin cña x cã kiÓu Real
6) Arctan(x) : a rctg cña x cã kiÓu Real
7) Ln(x) : Loga c¬ sè e cña x cã kiÓu Real
8) Exp(x) : cho e x
9) Random(n) : Cho mét sè nguyªn ngÉu nhiªn tõ 0 tíi n-1 ( n nguyªn )
10) Odd (n) : cho gi¸ trÞ True nÕu n lÎ ; cho gi¸ trÞ False nÕu n ch½n
11) Round(x) : lµ sè nguyªn lµm trßn cña sè thùc x
12) Trunc(x) : lµ sè nguyªn ,b»ng phÇn nguyªn cña sè thùc x
13) Int(x) : lµ sè thùc , b»ng phÇn nguyªn cña sè thùc x
14) Frac(x) : lµ sè thùc , b»ng phÇn thËp ph©n cña sè thùc x
Víi c¸c kiÓu d÷ liÖu v« h­íng ®Õm ®­îc ( KiÓu sè nguyªn :Integer,Byte, LongInt, ShortInt, Word, KiÓu L«gic : Boolean, KiÓu kÝ tù : Char ) cã quan hÖ thø tù nªn cßn ®­îc x©y dùng c¸c hµm sau ®©y : ORD , PRED , SUCC
ThÝ dô :

ORD(10) = 10 , PRED(10) = 9 , SUCC(10) = 11

ORD(‘B’) = 66 , PRED(‘B’) =‘A’ , SUCC(‘B’) =‘C’

ORD(False) = 0 , ORD(True) = 1 ,

ORD(3*4=12) = 1 , ORD(3*4=11) = 0 ,

PRED(True) = False , SUCC(False) = True


15) INC(x,k) : T¨ng sè nguyªn x lªn thªm k ®¬n vÞ ( x := x+k )

16) DEC(x,k) : Gi¶m sè nguyªn x ®i k ®¬n vÞ ( x := x-k )


e - CÊu tróc mét ch­¬ng tr×nh d¹ng ®¬n gi¶n
Mét ch­¬ng tr×nh TURBO PASCAN cã c¸c thµnh phÇn sau :
(* PhÇn khai b¸o ch­¬ng tr×nh *)

Program Tªn_ch­¬ng_tr×nh;

Uses Tªn _c¸c_ Unit_ cÇn _thiÕt ;

Label Tªn_nh·n;

Const Tªn_h»ng = Gi¸_trÞ_cña_h»ng;

Type Tªn_kiÓu : KiÓu_h»ng ;

Var Tªn_biÕn : KiÓu_biÕn;
(* PhÇn th©n ch­¬ng tr×nh *)

Procedure Tªn_thñ_tôc_1(Tªn_tham_trÞ ; Var Tªn_tham_biÕn : KiÓu_tham_biÕn);

Uses Tªn _c¸c_ Unit_ cÇn _thiÕt ;

Label Tªn_nh·n;

Const Tªn_h»ng = Gi¸_trÞ_cña_h»ng;

Type Tªn_kiÓu : KiÓu_h»ng ;

Var Tªn_biÕn : KiÓu_biÕn;

Begin


(* PhÇn th©n cña thñ tôc 1 gåm c¸c lÖnh nµo ®ã *)

End ;


......
Procedure Tªn_thñ_tôc_n(Tªn_tham_trÞ ; Var Tªn_tham_biÕn : KiÓu_tham_biÕn);

Uses Tªn _c¸c_ Unit_ cÇn _thiÕt ;

Label Tªn_nh·n;

Const Tªn_h»ng = Gi¸_trÞ_cña_h»ng;

Type Tªn_kiÓu : KiÓu_h»ng ;

Var Tªn_biÕn : KiÓu_biÕn;

Begin

(* PhÇn th©n cña thñ tôc n gåm c¸c lÖnh nµo ®ã *)



End ;

Function Tªn_Hµm(Tªn_tham_trÞ; Var Tªn_tham_biÕn : KiÓu_tham_biÕn):KiÓu_gi¸_trÞ_hµm ;

Uses Tªn _c¸c_ Unit_ cÇn _thiÕt ;

Label Tªn_nh·n;

Const Tªn_h»ng = Gi¸_trÞ_cña_h»ng;

Type Tªn_kiÓu : KiÓu_h»ng ;

Var Tªn_biÕn : KiÓu_biÕn;

Begin


(* PhÇn th©n cña hµm gåm c¸c lÖnh nµo ®ã *)

End ;


BEGIN

(* Th©n cña ch­¬ng tr×nh chÝnh gåm c¸c lÖnh , trong ®ã cã c¶ lÖnh gäi thñ tôc vµ hµm *)



END.

Chó ý : Khi khai b¸o h»ng hoÆc biÕn , m¸y sÏ cÊp ph¸t vïng nhí cho chóng . Gi¸ trÞ trong vïng nhí nµy chÝnh lµ gi¸ trÞ cña h»ng vµ biÕn t­¬ng øng . ThÝ dô

Var x : Integer;



ch : Char;

S : String[30];

y : Real;

Nam : Boolean;

th× x ®­îc cÊp ph¸t vïng nhí 2 Byte , Ch ®­îc cÊp ph¸t vïng nhí 1 Byte , S ®­îc cÊp ph¸t vïng nhí 31 Byte , y ®­îc cÊp ph¸t vïng nhí 4 Byte ., nam ®­îc cÊp ph¸t vïng nhí 1 Byte ...


f - B­íc ®Çu sö dông phÇn mÒm TURBO PASCAN 7.0
TURBO PASCAN lµ phÇn mÒm nh»m so¹n th¶o, söa ch÷a , biªn dÞch vµ ch¹y ch­¬ng tr×nh .

: files -> news -> attachs
news -> Chỉ số giá tiêu dùng, chỉ số giá vàng và đô la Mỹ tháng 02 năm 2007
news -> Nhập khẩu tháng 10 và 10 tháng năm 2005
news -> Coâng vieäc: nhaân vieân baùn haøNG
news -> Thoâng baùo tuyeån duïng maõ soá: 1208-903 Coâng vieäc: phuï vieäc nhaø
news -> Coâng vieäc: nhaân vieân thu ngaâN; nhaân vieân giöÕ xe
news -> Thoâng baùo tuyeån duïng maõ soá: 1210-1257 Coâng vieäc: phuï vieäc nhaø
news -> Thoâng baùo tuyeån duïng maõ soá: 1210-1161 Coâng vieäc: phuï vieäc nhaø
attachs -> TRƯỜng thpt quang minh số : 46/ktnb-thptqm cộng hòa xã HỘi chủ nghĩa việt nam
attachs -> PHẦn chung cho tất cả thí sinh (7,0 điểm) Câu I
attachs -> ĐẠi học quốc gia hà NỘi lý LỊch khoa họC


  1   2   3


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2019
được sử dụng cho việc quản lý

    Quê hương