Đề tài Cấu trúc dữ liệu và giải thuật căn bản

Ch­¬ng 1.      thiÕt kÕ gi¶i thuËtvµ ®Ö quy

1. C¸c kh¸i niÖm

1.1. Gi¶i thuËt vµ cÊu tróc d÷ liÖu

a. Giíi thiÖu m«n häc

Khi gi¶i mét bµi to¸n ta cÇn:

• ThiÕt lËp c¸c th«ng tin vµo, gåm d÷ liÖu ban ®Çu
• CÊu tróc l¹i c¸c d÷ liÖu ®Ó cã thÓ ®­a ®­îc vµo m¸y tÝnh
• X©y dùng c¸c gi¶i thuËt (thuËt to¸n) ®Ó gi¶i bµi to¸n trªn m¸y

§©y chÝnh lµ néi dung m«n häc CÊu tróc d÷ liÖu vµ gi¶i thuËt

b. §Þnh nghÜa gi¶i thuËt

Gi¶i thuËt lµ d·y c¸c c©u lÖnh chÆt chÏ x¸c ®Þnh tr×nh tù thao t¸c trªn mét ®èi t­îng nµo ®ã sao cho sau h÷u h¹n b­íc nhËn ®­îc kÕt qu¶ mong muèn.

c. C¸c VÝ dô

- T×m ­íc sè chung lín nhÊt cña 2 sè nguyªn d­¬ng x, y

Gi¶i thuËt t×m ¦SCLN th«ng qua c¸c b­íc:

B­íc 1: NÕu x > y g¸n x := x - y, nÕu kh«ng th× y:= y - x;

B­íc 2: Thùc hiÖn b­íc 1 cho ®Õn khi x = y;

B­íc 3: ¦SCLN = x (hoÆc = y)

§©y lµ mét gi¶i thuËt víi B­íc 1, B­íc 2 h÷u h¹n b­íc (gi¶i thuËt ¥clid)

Víi x = 24, y= 18

x := 24 - 18 = 6, y = 18

y := 18 - 6 = 12, x = 6

y := 12 - 6 = 6 = x, dõng ¦SCLN = 6

d. D÷ liÖu vµ cÊu tróc d÷ liÖu

- D÷ liÖu lµ nh÷ng th«ng tin ban ®Çu, gåm nh÷ng ®¹i l­îng ®Þnh l­îng.

- §Ó gi¶i bµi to¸n ng­êi ta ph¶i s¾p xÕp d÷ liÖu theo mét cÊu tróc hîp lý nµo ®ã ®Ó viÖc gi¶i bµi to¸n ®­îc dÔ dµng. Vµ viÖc s¾p xÕp ®ã ®­îc gäi lµ cÊu tróc d÷ liÖu.

1.2. Ng«n ng÷ diÔn ®¹t gi¶i thuËt

a. DiÔn ®¹t theo ng«n ng÷ tù nhiªn

VÝ dô phÇn 1b ë trªn ®· dïng ng«n ng÷ tù nhiªn ®Ó diÔn ®¹t.

b. DiÔn ®¹t theo gi¶ Pascal

Xen gi÷a ng«n ng÷ lËp tr×nh Pascal ®Ó diÔn ®¹t gi¶i thuËt.

VÝ dô:

B­íc 1: If x > y then x := x – y Else y := y- x;

B­íc 2: Thùc hiÖn B­íc 1 Until x = y;

c. DiÔn ®¹t d­íi d¹ng thñ tôc hoÆc hµm cña mét ng«n ng÷ lËp tr×nh nµo ®ã (Pascal, C,…)

Trong khu«n khæ m«n häc ta sö dông ng«n ng÷ lËp tr×nh Pascal

1.3. Mét sè c©u lÖnh cña Pascal

(Tù häc)

1.4. C¸c b­íc ®Ó gi¶i mét bµi to¸n

- M«®un ho¸ bµi to¸n (ph©n r· bµi to¸n): chia bµi to¸n lín ra c¸c bµi to¸n con vµ viÕt c¸c thñ tôc thùc hiÖn chóng.

- Tinh chØnh m«®un (module) theo mét ng«n ng÷ nµo ®ã

- R¸p l¹i thµnh ch­¬ng tr×nh

VÝ dô 1:

Function USCLN (x, y: interger): interger

Begin

Repeat

If x > y Then x := x- y Else y ;= y – x;

Until x = y;

USCLN := x;

End;