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

tải về 301.83 Kb.

trang	1/3
Chuyển đổi dữ liệu	05.08.2016
Kích	301.83 Kb.
	#13277

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 trng 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 ₁,A ₂,...,A _n :
B0 B¾t ®Çu

B1 NhËp c¸c gi¸ trÞ N , A ₁,A ₂,...,A _n

B2 G¸n i = 2

B3 NÕu A _i< A ₁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 ₁nhá nhÊt

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

B8 KÕt thóc

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

B1 NhËp c¸c gi¸ trÞ N, A ₁,A ₂,...,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 ₁,A ₂,...,A _n , råi chuyÓn sang B7

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

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

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

B1 NhËp N, A ₁,A ₂,...,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 ₁,A ₂,...,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 ₁,A ₂,...,A_nnguyªn d¬ng kh«ng lín h¬n 32.000
B0 B¾t ®Çu

B1 NhËp N , A ₁,A ₂,...,A _n.

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

B3 x = 1

B4 DuyÖt trªn trôc sè, nÕu thÊy x lµ ®iÓm nguyªn cha ®î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 cha 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 ₀ = 1 ( X lµ gi¸ trÞ gÇn ®óng ®Çu tiªn cña c¨n bËc 2 cña A )

B3 X = X ₀

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

B5 KiÓm tra :  X ₀- 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 ₀

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 cha 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 cha 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 cha tèi u ( Cha lµ lêi gi¶i tèt nhÊt ) v× viÖc chän mµu tèt nhÊt cho 1 ®Ønh i cha 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 .

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ý cha? (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 nhng ®· 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ó ý lu gi÷ l¹i ch¬ng tr×nh cò tríc khi c¶i tiÕn.

10 / Lu 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 nhng 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;

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;

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;

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;

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;

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;

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;

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;

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;

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 .

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 )

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è vµ 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

+ §Ó 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

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 ³⁸

+ 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 ; nhng 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 ...

Var i : Byte;

BEGIN

Clrscr;

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

Readln;

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 lu ý 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 , nhng 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 ;

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

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

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

End ;

BEGIN

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

tải về 301.83 Kb.

Chia sẻ với bạn bè của bạn:

1 2 3