1. Giới thiệu về ngôn ngữ lập trình là gì ?
tải về 0.58 Mb.
|
| a. Cấu trúc rẽ nhánh
- Rẽ nhánh dạng khuyết: if <đk thoả mãn> then - Rẽ nhánh dạng đủ: if <đk thoả mãn> then L nh L nh 2 - Cấu lệnh lựa chọn: case Giá trị 1: Thực hiện lệnh 1 Giá tHịì2nhT1ực hiện lệnh 2 Giá trị n: Thực hiện lệnh n else Thực hiện lệnh (n+1) endL nh 1 L nh 1 L nh n Hình 3
b. Cấu thúc lặp + Lặp một số lần định trước: Dạng 1: for i:=m to n do Thực hiện lệnh với i nhận các giá trị nguyên tăng từ m tới n với bước nhảy bằng 1 Dạng 2: for i:=n downto m do Tương tự như dạng 1 nhưng bước nhảy giảm bằng 1
Khi điều kiện còn đúng thì còn thực hiện lệnh, quá trình lặp kết thúc khi điều kiện sai (hình 1) + Lặp với điều kiện sau: repeat Khi điều kiện còn sai thì còn thực hiện lệnh, quá trình lặp kết thúc khi điều kiện đúng 3.3 Cách 3: Sử dụng giả ngôn ngữ có cấu trúc tựa ngôn ngữ lập trình bậc cao Là phương pháp diễn tả giải thuật dựa vào các cấu trúc điều khiển, cùng với các từ khoá của một ngôn ngữ lập trình bậc cao nào đó. Trong giáo trình này ta sẽ sử dụng ngôn ngữ tựa Pascal để diễn tả giải thuật. Cách diễn đạt này đã tiếp cận gần hơn với ngôn ngữ lập trình. Ví dụ: Với thuật giải tìm UCLN ở trên ta có thể diễn đạt như sau while ab begin
if a>b then thay a bởi a-b else thay b bởi b-a end
write ước chung lớn nhất là a 4. Thiết kế giải thuật 4.1. Mô-đun hoá và việc giải quyết bài toán Những bài toán ta gặp trong thực tế thường là phức tạp, trong trường hợp đó người ta thường chia bài toán thành những bài toán nhỏ và dễ giải quyết hơn. Nghĩa là coi bài toán ban đầu là Mô- đun chính, ta chia nó thành các Mô- đun con, và mỗi Mô- đun con này có thể lại được chia thành các Mô- đun nhỏ hơn... Cách giải quyết bài toán như vậy người ta thường gọi là chiến thuật "Chia để trị"(divide and conquer). Trong khi lập trình việc chia chương trình chính thành các chương trình con thể hiện tính có cấu trúc của ngôn ngữ lập trình về mặt chương trình
Ta có sơ đồ sau: Ngôn ngữ tự nhiên Giả ngôn ngữ Ngôn ngữ lập trình 4.3. Phân tích thuật giải Phân tích giải thuật phải căn cứ vào 3 tiêu chuẩn đối với một giải thuật: Tính dừng, tính đúng đắn, tính đơn giản và hiệu quả. Việc kiểm tra giải thuật là một phần hết sức quan trọng, lý tưởng là khi có thể khẳng định một cách hình thức tính đúng đắn của giải thuật. Tuy nhiên trong thực tế thời gian và công sức để viết ra một cách cẩn thận và đầy đủ tất cả những chi tiết chứng minh tính đúng đắn của một giải thuật phức tạp thường là không cho phép. Người lập trình thường áp dụng các biện pháp sau: - Chứng minh một cách suy diễn rằng những bước trong giải thuật là đúng đắn. Nghĩa là giải thuật bắt đầu bằng một khẳng định (giả thiết) về dữ liệu vào và dùng phương pháp suy luận lôgic để chỉ ra rằng việc thực hiện giải thuật sẽ cho một khẳng định (kết luận) về đầu ra. - Thể hịên giải thuật bằng một ngôn ngữ lập trình và thử thực hiện chương trình với các bộ dữ liệu vào mà kết quả ta đã biết trước. Thường thì các lỗi về cú pháp và lỗi lúc thực hiện chương trình thường dễ tìm và sửa chữa còn các lỗi lôgic thường khó phát hiện hơn nhiều. - Có đôi lúc viêc kiểm tra chương trình phải thực hiện thủ công, kiểm tra từng bước, từng thủ tục của chương trình chính. Kỹ thuật này được gọi là “đi bộ qua chương trình”(Walking through the program) - Quan tâm đặc biệt tới thời gian thực hiện chương trình, thời gian thực hiện phụ thuộc rất nhiều vào việc tổ chức dữ liệu đưa vào (kích thước dữ liệu).
Thuật giải chọn được diễn tả như sau: Tìm phần tử nhỏ nhất trong dãy số và hoán vị nó với phần tử đầu tiên, tìm phần tử nhỏ nhất kế tiếp và hoán vị nó với phần tử thứ hai. Tiếp tục quá trình này đến khi toàn bộ dãy số được sắp xếp. procedure Selection_Sort; begin
for i:=1 to n-1 do begin m:=i
for j:=i+1 to n do if aj end
end Ví dụ
Dãy số ban đầu : 3 6 -2 7 5 i=1 -2 6 3 7 5 i=2 -2 3 6 7 5 i=3 -2 3 5 7 6 i=4 -2 3 5 6 7
for i:=2 to n do begin k:=ai j:=i while aj-1>k do begin aj:=aj-1, j:=j-1 end aj:=k end
Ví dụ Dãy số ban đầu : 3 6 -2 7 5 i=2 3 6 -2 7 5 i=3 -2 3 6 7 5 i=4 -2 3 6 7 5 i=5 -2 3 5 6 7 5.3 Sắp xếp nổi bọt (bubble sort) Thuật giải này còn có tên gọi khác là sắp xếp bằng cách đổi chỗ trực tiếp (exchange sort), thuật giải nổi bọt được diễn tả như sau: Duyệt dãy số theo thứ tự từ phải sang trái nếu hai phần tử kề cận ngược thứ tự thì đổi chỗ cho nhau. Như vậy sau lượt duyệt đầu tiên phần tử đầu tiên sẽ là phần tử nhỏ nhất, sau lượt thứ hai phần tử nhỏ thứ hai được chuyển lên vị trí thứ hai...cứ như vậy dãy số sẽ được sắp xếp tăng dần. procedure Bubble_Sort begin
for i:=1 to n-1 do for j:=n downto i+1 do if aj end
Ví dụ Dãy số ban đầu : 3 6 -2 7 5 i=1 -2 3 6 5 7 i=2 -2 3 5 6 7 i=3 -2 3 5 6 7 i=4 -2 3 5 6 7 6. Giải thuật tìm kiếm (Searching) Cùng với các thuật giải sắp xếp, các thuật giải tìm kiếm cũng đóng một vai trò quan trọng trong khi xủ lí số liệu. Bài toán tìm kiếm đặt ra như sau: Giả sủ ta có một dãy số a1, a2,...., an, ta phải tìm vị trí của phần tử có giá trị bằng giá trị X cho trước. Chúng ta sẽ xét hai thuật giải tìm kiếm đó là tìm kiếm tuần tự (sequential searching) và tìm kiếm nhị phân (binary searching). 6.1 Tìm kiếm tuần tự (sequential searching) Đây là thuật giải tìm kiếm đơn giản nhất, ta sẽ duyệt tuần tự dãy số, thuật giải sẽ kết thúc khi tìm thấy phần tử bằng giá trị X hoặc khi duyệt hết dãy số nhưng không có phần tử nào có giá trị là X procedure Sequential_Searching
i:=1
while ai≠ X do i:=i+1 if i=n+1 then không có phần tử cần tìm else vị trí phần tử cần tìm là i end
Giả sử dãy số đã được sắp xếp tăng dần a1≤a2≤.....≤an (trường hợp sắp xếp giảm dần thì
procedure Binary_Searching begin left:=1
repeat mid:=[(left+right)/2] (*Kí hiệu [a] nghĩa là lấy phần nguyên của số thực a*) if X else left:=mid+1 until (X=amid) or(left>right) if X=amid then vị trí cần tìm là mid else không có phần tử cần tìm
Ví dụ: Tìm phần tử 28 trong dãy số sau [4 15 28 33 67 99 103] Lặp lần 1 [4 15 28] Lặp lần 2 [28]
Trong khi thiết kế giải thuật ta thường thiết kế dưới dạng các mô- đun. Khi giải thuật được cài đặt thành chương trình thí các mô- đun sẽ tương ứng với các chương trình con (hàmfunction và thủ tục- procedure), Chương trình con được gọi là đệ qui nếu trong thân của nó có lời gọi trực tiếp hoặc gián tiếp đến chính bản thân nó. Đệ qui có ý nghĩa đặc biệt quan trọng trong các định nghĩa toán học Ví dụ 1: Định nghĩa số tự nhiên + 0 là số tự nhiên + Số tiếp theo của một số tự nhiên là một số tự nhiên Ví dụ 2: Định nghĩa n! + 0!=1
+ n!=n*(n-1)! nếu n>0 - Định nghĩa một phép đệ qui gồm có 2 phần + Trường hợp suy biến: Giúp cho quá trình đệ qui kết thúc + Phần đệ qui (hay phần qui nạp): Trong đó tác động cần được thực hiện cho giá trị hiện thời của các tham số được định nghĩa bằng các tác động hay giá trị được định nghĩa trước đây Trong ví dụ định nghĩa n! thì trường hợp suy biến định nghĩa 0!, phần qui nạp định nghĩa n! qua các giá trị của n và giá trị của (n-1)! Dễ nhận xét, nếu (n-1)! đã tính được thì n! sẽ dễ dàng tính được. Với cách suy diễn tương tự, (n-1)! sẽ tính được nếu như (n-2)! đã tính được... cuối cùng 1! sẽ tính được nếu 0! đã tính được. Ta thấy rằng 0! đã cho trong định nghĩa. Do vậy đi ngược từ cuối, vì 0! đã tính được nên 1! cũng tính được,....,sau khi (n-1)! đã có ta sẽ nhận được n! Minh hoạ: Tính 3! 3!=3*2!=3*2=6 2!=2*1!=2*1=2 1!=1*0!=1*1=1 0!=1
Giải thuật được viết dưới dạng thủ tục hàm (tựa Pascal) như sau: function giaithua(n) begin
if n=0 then giaithua:=1 (* trường hợp suy biến*) else giaithua:=n*giaithua(n-1) (* phần đệ qui*) end Chú ý: Không phải lúc nào tính đệ qui trong cách giải bài toán cũng thể hiện rõ nét và dễ phát hiện như ví dụ trên. Do đó muốn biết giải thuật của một bài toán có thể thiết kế dưới dạng giải thuật đệ qui được hay không? Có thể thấy câu trả lời qua việc trả lời các câu hỏi sau : + Có thể định nghĩa được bài toán dưới dạng một bài toán cùng loại nhưng “nhỏ” hơn không? + Kích thước của bài toán sẽ giảm đi ở mỗi bước gọi đệ qui như thế nào? + Trường hợp nào của bài toán được coi là trường hợp suy biến? 7. 2. Ví dụ về giải thuật đệ qui : Bài toán tháp Hà Nội Bài toán Tháp Hà Nội là một ví dụ cổ điển cho thấy thuật toán đệ qui là đặc biệt thích hợp. Có thể giải quyết bài toán một cách dễ dàng nếu dùng đệ qui, nhưng cách giải không đệ qui là tương đối khó. Nội dung bài toán: Tại cọc A có n chiếc đĩa, đĩa to ở dưới, đĩa nhỏ ở trên. Chuyển các đĩa từ cọc A sang cọc C có thể nhờ cọc B làm vị trí trung chuyển theo các quy tắc sau: - Mỗi lần chỉ được chuyển một đĩa và phải là đĩa ở trên cùng - Đĩa lớn không bao giờ được phép nằm trên đĩa nhỏ
Một truyền thuyết cho rằng các thầy tu ở Điện Bramah được cho một bài toán đố với một nền vàng có 3 kim vàng trên 1 cọc có 64 đĩa vàng. Khi họ chuyển các đĩa vàng theo các luật của bài toán trên, nếu mỗi giây chuyển được một đĩa và họ bắt đầu công việc từ năm 0, đến khi hoàn thành công việc thì sẽ là ngày tận thế. Những người mới bắt đầu có thể giải bài toán một cách dễ dàng với số các đĩa là bé, nhưng họ sẽ rất khó khăn khi số đĩa tăng lên 7,8 và lớn hơn. Tuy nhiên với một nhà lập trình thì có thể giải bài toán một cách không mấy khó khăn. Cách giải: Nếu có một đĩa, chuyển nó từ cọc A sang cọc C. Bài toán giải được với n=1 Giả sử rằng bài toán có nghiệm với n-1 đĩa , nghiệm với n đĩa có thể nhận được một cách dễ dàng nhờ dùng phép đệ quy: + Chuyển n-1 đĩa trên cùng ở cọc A sang cọc B, dùng cọc C làm trung chuyển + Chuyển đĩa còn lại ở cọc A sang cọc C + Chuyển n-1 từ cọc B sang cọc C, dùng cọc A làm trung chuyển Ta có thể viết giải thuật của bài toán Tháp Hà Nội như sau: procedure Move(n,A,B,C) (* Chuyển n đĩa từ cọc A sang cọc C, dùng cọc B làm trung chuyển*)
if n=1 then chuyển đĩa từ A sang C else begin
Move(n-1,A,C,B) (* Chuyển n-1 đĩa từ A sang B, dùng C làm trung chuyển*) Move(1,A,’ ‘,C) (* Chuyển 1 đĩa từ cọc A sang cọc C*) Move(n-1,B,A,C) (* Chuyển n-1 đĩa từ B sang C, dùng A làm trung chuyển*) end end
Bài tập chương VI: Thuật giải Viết giải thuật cho các bài toán sau: 1. Tính n giai thừa: n! =1.2...n với n>1 2. Tính các tổng: S=1/2 + 1/4 +...+ 1/(2k) Q=1.1!+2.2!+...+n.n! 3. Tìm và in ra tất cả các số chính phương nhỏ hơn một số cho trước, cho biết có bao nhiêu số chính phương như vậy. 4. Viết chương trình giải bài toán cổ: " Vừa gà vừa chó, bó lại cho tròn, ba mươi sáu con, một trăm chân chẵn. Hỏi có bao nhiêu gà, bao nhiêu chó?" 5. Viết chương trình tìm ước số chung lớn nhất của 2 số nguyên dương cho trước. Каталог: dulieu -> files dulieu -> CHƯƠng tổng quan môn học quản trị logistics kinh doanh 1Logistics trong nền kinh tế hiện đại dulieu -> Bé lao ®éng th¬ng binh céng hoµ x· héi chñ nghÜa viÖt nam dulieu -> Bài tập Kiểm toán căn bản gv : ncs. ThS phan Thanh Hải LỜi ngõ dulieu -> TỰ do nội tâm jacques Philippe Người dịch, Lm. Minh Anh (Gp. Huế) TỰ do nội tâM dulieu -> Nguyễn Thị Hồng Ngát BỘ giáo dục và ĐÀo tạO files -> Danh môc hå s¬ tµi nguyªn m i trêng (thu håi-giao ®Êt) files -> Danh mục dữ liệu về khí TƯỢng thủy văn tại trung tâm công nghệ thông tin files -> BỘ giáo dục và ĐÀo tạo số: 33 /2007/QĐ-bgdđT tải về 0.58 Mb. Chia sẻ với bạn bè của bạn:
|