Thuật Giải trong pascal7.0

[boy_cobi1996]

[FONT=&quot]THUẬT GIẢI[/FONT]​

[FONT=&quot]Mục tiêu bài học:[/FONT]
[FONT=&quot] - Xác định được tập dữ liệu vào, dữ liệu ra, biết phân chia công việc thành các bước. Sau mỗi bước bao giờ cũng cho 1 kết quả xác định không phụ thuộc vào người hay máy thực hiện mà chỉ phụ thuộc vào dữ liệu vào.
- Chỉ ra tính khả thi của các bước thực hiện. Tính dừng sau một số hữu hạn bước. Nắm được 3 cách biểu diễn thuật toán.[/FONT]
[FONT=&quot]1. Khái niệm thuật giải
[/FONT][FONT=&quot]Thuật giải giải một bài toán nào đó là một dãy các thao tác đơn giản được sắp xếp theo một trình tự xác định rõ ràng và kết thúc sau một số hữu hạn bước nhằm biến đổi dữ liệu vào (input) của một bài toán thành dữ liệu ra (output) mô tả lời giải bài toán đó.
Ví dụ . Bài toán kiểm tra tính nguyên tố.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Cho: số nguyên dương N;
Cần biết: N có là số nguyên tố hay không?[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Thuật giải Ơclid giải bài toán trên
- Input: a, b nguyên dương
- Output: UCLN của a và b
Bước 1: nhận vào số a và số b
Bước 2: chia a cho b tìm số dư r
Bước 3: Nếu r = 0 thì chuyển đến bước 5
Bước 4: gán giá trị b cho a, gán giá trị r cho b. Quay về bước 2
Bước 5: thông báo kết quả UCLN là b;
Bước 6: Kết thúc.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]2. Các tính chất của thuật giải[/FONT]
[FONT=&quot]2.1. Có dữ liệu vào (input)[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Mỗi thuật giải có thể có một hoặc nhiều dữ liệu vào.[/FONT]
[FONT=&quot] 2.2. Xác định dữ liệu ra (output)[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Sau khi thuật giải đã được thực hiện xong, tuỳ theo chức năng mà thuật giải đảm nhiệm ta có thể thu được một số dữ liệu ra xác định[/FONT]
[FONT=&quot]2.3. Tính xác định[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Tính xác định của thuật giải đòi hỏi ở mỗi bước các thao tác phải hết sức rõ ràng, không thể gây nên sự nhập nhằng, lẫn lộn, tuỳ tiện.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]2.4. Tính kết thúc (tính dừng)[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Thuật giải phải dừng sau một số hữu hạn bước thực hiện.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]2.5. Tính hiệu quả[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Một yêu cầu quan trọng là với input đúng thuật giải phải cho output đúng.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]2.6. Tính phổ dụng[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Một thuật giải được xem là có tính phổ dụng cao nếu nó có thể giải bất kỳ bài toán nào trong một lớp lớn các bài toán.[/FONT]

[FONT=&quot]1. Liệt kê từng bước[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Thuật giải Ơclid ở trên được diễn tả theo hình thức liệt kê từng bước.
2. Lưu đồ(sơ đồ khối)
Lưu đồ là công cụ giúp ta diễn tả thuật giải một cách trực quan. Lưu đồ được tạo bởi 4 loại khối nối với nhau bằng các cung[/FONT]

[FONT=&quot]- Khối thao tác được biểu diễn bằng hình chữ nhật. Trong khối này ta viết một hoặc một dãy các thao tác như gán trị, tính toán biểu thức v.v... Khối thao tác có 1 cung đi đến và 1 cung đi ra.
- Khối điều kiện được biểu diễn bằng hình thoi. Trong khối này ta viết một biểu thức logic. Tuỳ theo giá trị của biểu thức logic là đúng hay sai mà việc thực hiện tiếp theo sẽ được chỉ dẫn bởi một trong hai cung đi ra mang dấu + (cho trường hợp đúng) hoặc dấu - (cho trường hợp sai). Như vậy khối điều kiện có 1 cung đi đến và 2 cung đi ra.
- Hai khối đặc biệt là khối bắt đầu và khối kết thúc được biểu diễn bằng hình ellip chỉ rõ điểm bắt đầu và điểm kết thúc (điểm dừng) của thuật giải. Khối bắt đầu không có cung đi đến và có 1 cung đi ra. Khối kết thúc có 1 cung đi đến và không có cung đi ra.
Chúng ta dùng lưu đồ diễn tả thuật giải Ơclid tìm UCLN của hai số nguyên dương.
Thuật giải Ơclid
+Dữ liệu vào - Số nguyên a > 0; b > 0[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot] [/FONT][FONT=&quot]+Dữ liệu ra - USCLN của a và b[/FONT]

3. Giả mã lệnh
Khi thể hiện thuật giải bằng giả mã lệnh, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó. Ở đây chúng ta vay mượn các khái niệm của ngôn ngữ lập trình pascal.
3.1. Lệnh gán
Tên biến :=biểu thức;
3.2. Lệnh rẽ hai nhánh
a. Lệnh rẽ hai nhánh dạng khuyết
Nếu điều kiện thì câu lệnh
b. Lệnh rẽ hai nhánh dạng đầy đủ
Nếu điều kiện thì câu lệnh 1
còn câu lệnh 2;
[FONT=&quot] [/FONT]
[FONT=&quot]4. Ví dụ
[/FONT][FONT=&quot] Người A nghĩ trong đầu một số nguyên X trong đoạn từ 1 đến 100. Người B hỏi, người A trả lời hoặc đúng hoặc sai. Sau không quá 7 lần hỏi đáp người B biết số X là số nào. Viết thuật giải cho bài toán này.
[/FONT][FONT=&quot]4.1. Dùng ngôn ngữ liệt kê từng bước
[/FONT][FONT=&quot]Bước 1 Gán T := 1 ; P := 100;
Bước 2 Lấy thương nguyên của tổng (T + P) chia cho 2 rồi gán cho G.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Bước 3 Kiểm tra điều kiện X > G nếu đúng thì chuyển đến bước 4, còn sai thì chuyển đến bước 5;[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]Bước 4 Lấy G + 1 gán cho T; chuyển đến bước 6;
Bước 5 Lấy G gán cho P;
Bước 6 Kiểm tra điều kiện T = P nếu sai thì chuyển đến bước 2;
Bước 7 Trả lời X = T ;
Bước 8 Kết thúc;[/FONT]
[FONT=&quot]4.2 Dùng sơ đồ khối[/FONT]
[FONT=&quot]

[/FONT][FONT=&quot][/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]4.3. Dùng giả mã lệnh
[/FONT][FONT=&quot]Biến nguyên không âm T, P, G, X;
Bắt đầu
T :=1; P :=100;
Lặp
G := (P+T) div 2;[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]nếu X > G thì T :=G+1
còn P :=G;
X.nếu; [/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]đến T = P;
Thông báo X = P;
Kết thúc.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]1. Thuật giải là gì? Thuật giải có những tính chất cơ bản nào? [/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]2. Có mấy cách biểu diễn thuật giải.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]3. Hãy viết thuật giải vẽ đồ thị của hàm số y = |ax| (với a khác 0) thông qua đồ thị của hàm số y = ax.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]4. Trình bày tính chất xác định của thuật giải và nêu rõ ý nghĩa của tính chất này.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]5. Hãy phát biểu thuật giải để giải bài toán sau: "Có một số quả táo. Dùng cân hai đĩa (không có quả cân) để xác định quả táo nặng nhất"(giả sử mỗi đĩa cân có thể đựng được nửa số quả táo).[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]6. Xác định dữ liệu vào và dữ liệu ra cho các thuật giải sau đây:[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]a) Rút gọn một phân số.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]b) Kiểm tra xem ba số cho trước a, b và c có thể là độ dài ba cạnh của một tam giác hay không?[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]c) Tính trung bình cộng của hai số.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]d) Dùng một cốc phụ để tráo nuớc ở hai cốc cho trước.[/FONT]
[FONT=&quot]e) Tìm chu vi và diện tích của hình tròn có bán kính cho trước.[/FONT]
[FONT=&quot] [/FONT]
[FONT=&quot]7. Có hai bình A và B. Bình A có dung tích 8 lít, bình B có dung tích 5 lít. Trình bày các bước thực hiện để lấy được 2 lít nước.[/FONT]
[FONT=&quot]8. Có 3 bình A, B, C. Bình A có dung tích 8 lít và đựng đầy 8 lít rượu, bình B có dung tích 5 lít, bình C có dung tích 3 lít. Trình bày các bước thực hiện để có được 4 lít rượu ở bình A và 4 lít rượu ở bình B.
9. Một người có 1 con gấu, 1 con dê và 1 cái bắp cải. Nếu không có người ở bên chúng thì con gấu sẽ ăn thịt con dê hoặc con dê sẽ ăn bắp cải. Thuyền chỉ có thể chở được người đó với con gấu hoặc con dê hoặc bắp cải. Người đó làm thế nào để mang chúng sang sông.
10.Có 4 người phải qua một cái cầu, trời tối họ chỉ có một chiếc đèn. Cầu chỉ đi được tối đa 2 người. Như vậy qua cầu phải có đèn và nhiều nhất là chỉ đi được 2 người cùng một lúc. Biết rằng người thứ nhất đi qua cầu hết 1 phút. Người thứ hai đi qua cầu hết 2 phút. Người thứ ba đi qua cầu hết 5 phút. Người thứ tư đi qua cầu hết 10 phút. Hãy tìm cách cho 4 người này qua cầu sao cho tổng số thời gian ít nhất[/FONT]

[FONT=&quot]____________[/FONT]​