Các bớc giải bài toán trong tin học Chu Thị Tú Anh

1

Phần
Phần Phần
Phần I
II
I:
::
:
mở đầu
mở đầumở đầu
mở đầu A
AA
A-

- Lí do chọn đề tài
Lí do chọn đề tài Lí do chọn đề tài
Lí do chọn đề tài Trong những năm gần đây, việc đào tạo về Công nghệ thông tin (CNTT) đ trở
thành nhu cầu ngày càng cấp thiết hơn đối với mọi ngời, từ nhân viên bán hàng, kỹ s,
bác sĩ và phóng viên đến nhà doanh nghiệp, cán bộ quản lí Phù hợp với xu thế phát triển

pháp nghiên cứu pháp nghiên cứu
pháp nghiên cứu Phơng pháp chủ yếu khi viết chuyên đề: Các bớc
Các bớc Các bớc
Các bớc giải bài toán trong tin
giải bài toán trong tin giải bài toán trong tin
giải bài toán trong tin
học
họchọc
học

là nghiên cứu Sách giáo khoa và một số tài liệu tham khảo, từ đó tổng hợp chắt lọc
các kiến thức và nội dung cần thiết để xây dựng chuyên đề.
C
CC
C-

- Đối tợng nghi
Đối tợng nghi Đối tợng nghi
Đối tợng nghiên cứu
ên cứuên cứu
ên cứu Chuyên đề viết ra với mục đích phục vụ cho quá trình dạy và học tin học trong

Vì vậy, mỗi một ngôn ngữ lập trình thờng cung cấp một số kiểu dữ liệu chuẩn cho
biết phạm vi giá trị có thể l trữ, dung lợng bộ nhớ cần thiết để lu trữ và các phép toán
tác động lên dữ liệu.
Trong ngôn ngữ Pascal ta có sơ đồ các kiểu dữ liệu nh sau:

BOOLEAN
INTEGER
BASIC TYPE REAL
CHAR
SIMPLE TYPE

DATA TYPE USER DEFINED SUBRANGE
TYPE ENUMERATED
STRUCTURE
TYPE ARRAY
SET
RECORD
STRING
FILE

BOOLEAN: Kiểu logic chỉ có thể nhận một trong hai giá trị TRUE hoặc FALSE
INTEGER: Kiểu số nguyên (-32768 32767)
REAL: Kiểu số thực (2.9x10
-39
1.7x10
38
)
CHAR: Kiểu kí tự gồm 256 kí tự trong bộ m ASCII.
SUB_RANGE: Kiểu miền con của một kiểu sơ cấp


DiemTB:real;
Ketqua:Boolean;
End;
SET: Kiểu tập hợp gồm một số các đối tợng có cùng kiểu cơ sở.
Ví dụ:
TYPE
Chucai= SET OF Char;
Chuso= SET OF 0 9;

Các bớc giải bài toán trong tin học Chu Thị Tú Anh

4

STRING: Kiểu xâu gồm một dy các kí tự.
Ví dụ:
TYPE
TRUONG: STRING[50];
HOTEN:STRING;

FILE: Kiểu tệp gồm một tập hợp các dữ liệu có liên quan với nhau và có cùng
kiểu đợc nhóm lại thành một dy và đợc lu trữ trên bộ nhớ nhớ ngoài.
Ví dụ:
TYPE
Tep=FILE of integer;
Bai=text;
cần thực hiện, cần thi hành để từ những cái đ có A có đợc cái phải tìm B.
2- Xác định bài toán:
Theo sơ đồ trên thì xác định bài toán có nghĩa là xác định A, B và nếu có thể đợc
thì xác định luôn các thao tác đợc phép sử dụng để đi từ A đến B.
3- Bài toán trong tin học:
Một bài toán trên máy tính cũng mang đầy đủ các tính chất của một bài toán tổng
quát đ nói ở trên nhng có thể đợc diễn dạt theo môt cách nói khác.
* A: là input hay còn gọi là thông tin vào.
* B: là output hay còn gọi là thông tin ra.
* là chơng trình tạo ra từ các lệnh cơ bản của máy cho phép biến đổi từ
A thành B.
4- Những khó khăn:
Để xác định một bài toán trên máy tính ta thờng gặp những khó khăn sau:
- Thông báo về A hay B không đầy đủ và không rõ ràng.
- Thông báo về các điều kiện đặt ra cho cách giải thờng không đợc nêu ra một
cách minh bạch.
5- Một số ví dụ:
Ví dụ 1: Tìm ớc chung lớn nhất của hai số nguyên dơng M và N.
Input: hai số nguyên dơng M và N.
Output: Ước chung lớn nhất của M và N.

Các bớc giải bài toán trong tin học Chu Thị Tú Anh

6

Ví dụ 2: Bài toán tìm kiếm nhị phân:
Cho dy A tăng gồm N số nguyên khác nhau a
1
, a
2

chất lợng của việc giải quyết bài toán.
- Một bài toán cho dù đợc diễn đạt bằng thông báo chính xác đến đâu đi chăng nữa
thì phần lớn thông tin về A và B là tiềm ẩn trong đầu ngời giải. Thông báo về A hoặc B
chỉ là biểu tợng gợi nhớ tới các thông tin tiềm ẩn đó.
- Bớc đầu tiên để xác định một bài toán là phải phát biểu lại bài toán một cách
chính xác theo ngôn ngữ riêng của mình vì đó chính là cách tiếp cận bài toán, hiểu bài
toán.
- Bớc kế tiếp là tìm hiểu các thông tin Input A và thông tin Output B, tìm các mối
liên giữa chúng.
Các bớc giải bài toán trong tin học Chu Thị Tú Anh

7

II_ Bớc 2: Chọn cấu trúc dữ liệu để biểu diễn bài toán:
1- Một số lu ý khi chọn cấu trúc dữ liệu:
- Cấu trúc dữ liệu phải biểu diễn đợc đấy đủ các thông tin nhập và xuất của bài
toán.
- Cấu trúc dữ liệu phải phù hợp với thao tác của thuật toán mà ta lựa chọn để giải
quyết bài toán.
- Cấu trúc dữ liệu phải phù hợp với điều kiện cho phép của ngôn ngữ lập trình và
MTĐT đang đợc sử dụng.
2- Một số ví dụ:
Ví dụ 1: Tìm ớc chung lớn nhất của hai số nguyên dơng M và N.
M, N là các số nguyên dơng nên cấu trúc dữ liệu nguyên dơng là hợp lý. Có thể

Tìm thuật toán là bớc quan trọng nhất để giải quyết một bài toán. Mỗi thuật toán
chỉ có thể giải đợc một bài toán nhng một bài toán có thể có nhiều thuật toán khác
nhau.
Khi thiết kế thuật toán hoặc lựa chọn thuật toán ngời ta thờng quan tâm đến các
tài nguyên nh: thời gian thực hiện, số lợng ô nhớ
Ví dụ: với bài toán tìm kiếm nhị phân, dy đ cho là dy đ đợc sắp xếp nên thuật
toán tìm kiếm nhị phân (sẽ trình bày ở dới đây) cần ít thao tác hơn nhiều so với thuật
toán tìm kiếm tuần tự.
Ví dụ 1: Tìm ớc chung lớn nhất cua hai số nguyên dơng M và N.
Ta có thuật toán Euclide đợc diễn tả bằng lu đồ nh sau:
ƯCLN là M

M>N

M<>N

M:=M
-



a
N

Dau<
-
1;Cuoi<
-
N

Giua:=[(Dau+Cuoi)/2]

A
giua
=k?

Đ
a ra giua rồi

kết thúc
Đúng

A
giua
<k
?


IV_ Bớc 4: Lập trình:
1- Khái niệm:
Lập trình là dùng ngôn ngữ máy tính cụ thể nào đó (ví dụ Pascal) để diễn tả thuật
toán, cấu trúc dữ liệu thành các câu lệnh để máy tính có thể thc hiện đợc và giải quyết
đúng bài toán mà ngời lập trình mong muốn.
2- Kĩ năng lập trình:
- Kĩ năng lập trình là kĩ năng cài đặt thành công các thuật toán bằng một ngôn ngữ
lập trình cụ thể.
- Đ gọi là kĩ năng thì chỉ có thể có đợc thông qua việc tèn luyện tích cực.
- Kinh nghiệm cho thấy một thuật toán hay nhng việc cài đặt lộn xộn, vụng về khi
chạy trên máy tính có thể cho kết quả rất tồi tệ.
3- Phát triển chơng tình bằng cách tinh chế từng bớc:
Tinh chế từng bớc là phơng pháp khoa học, có hệ thống giúp ta phân tích các
thuật toán và cấu trúc dữ liệu từ đó viết thành chơng trình.
Muốn lập trình không phải chỉ nắm vững ngôn ngữ lập trình là đủ, vấn đề cốt yếu
là biết phát triển dần dần để chuyển các ý tởng thành chơng trình hoàn chỉnh.
4- Phơng pháp tinh chế từng bớc:
Ban đầu chơng trình đợc viết bằng những lời tự nhiên (ngôn ngữ tiếng Việt
chẳng hạn).
- ở từng bớc sau, mỗi câu lời đợc phân tích ra chi tiết hơn bằng nhiều câu lời
khác tơng ứng với sự phân tích một công việc thành những công việc nhỏ hơn. Mỗi câu
lời đó là một sự đặc tả công việc.
- Càng ở những bớc sau các lời tự nhiên đợc thay thế bằng câu lời trong ngôn
ngữ lập trình
- Phơng pháp tinh chế từng bớc là một thể hiện của sự t duy, giải quyết vấn đề
từ trên xuống trong đó sự phát triển của các bớc là hớng về phía ngôn ngữ lập trình
đang đợc sử dụng.
4- Các ví dụ:
Ví dụ 1: Bài toán tìm ớc chung lớn nhất của hai số nguyên dơng M, N.

Writeln(ƯCLN của ,a,,,b, la:,M);
Readln
End.

Ví dụ 2: Bài toán tìm kiếm nhị phân:
Tinh chế lần 1: ý tởng của thuật toán
Sử dụng tính chất dy A là dy tăng, ta thu hẹp nhanh phạm vi tìm kiếm sau mỗi
lần so sánh khoá với số hạng đợc chọn. Để làm điều đó là chọn số hạng a
giua
ở giữa dy
để so sánh với k, trong đó giua=






+
2
1N
.
Khi đó chỉ xảy ra một trong 3 trờng hợp:
+ Nếu a
giua
= k thì đa ra chỉ số giua cần tìm. Việc tìm kiếm kết thúc.
+ Nếu a
giua
> k thì do A là dy đ sắp xếp tăng nên việc tìm kiếm tiếp theo sẽ thực
hiện trên dy a
1


+
2
CuoiDau
.
B5- Nếu a
giua
= k thì thông báo chỉ số giua rồi kêt thúc.
B6- Nếu a
giua
> k thì đặt Cuoi<-giua-1 rồi quay lại B3
B7- Nếu a
giua
< k thì đặt Dau<-giua+1 rồi quay lại B3
B3.2: Nếu Dau > Cuoi thì thông báo dy A không có số hạng nào có giá trị
bằng k rồi kết thúc.

* Tinh chế lần 3:
Bắt đầu.
B1- Nhập dữ liệu: N, các số hạng của dy: a
1
, a
2
, a
N
.
B2- Dau<-1; Cuoi<-N;
B3- While Dau < Cuoi và cha tìm thấy k thì
1. Tính - giua=


BEGIN
Clrscr;
Write(Nhap so phan tu cua day so N=); readln(N);
Writeln(Nhap cac phan tu cua day so tang:);
For i:=1 to N do
Begin
Write(PT thu ,i, la:); readln(A[i]);
End;
Write(Nhap k=); readln(k);
Dau:=1; Cuoi:=N; Timthay:=false;
While (Dau< Cuoi) and not(Timthay) do
Begin
Giua:=(Dau+Cuoi) mod 2;
If A[giua] = k then Timthay:=true
Else if A[giua]>k then Cuoi:=giua-1
Else Dau:=giua+1;
End;
If Timthay then writeln(Chi so tim duoc la:,giua)
Else writeln(Khong tim thay!);
Readln
END.
V-bớc 5: Hiệu chỉnh:
Sau khi đợc viết xong, chơng trình vẫn còn có thể có nhiều lỗi khác cha phát
hiện đợc nên có thể không cho kết quả đúng. Vì vậy, cần phải chạy thử chơng trình với
một số bộ Input tiêu biểu phụ thuộc vào đặc thù của bài toán và bằng cách nào đó ta đ
biết trớc Output. Các bộ Input và Output tơng ứng này đợc gọi là các Test. Nếu có sai
sót ta phải sửa chơng trình và thử lại.
Ví dụ 1: Với thuật toán tìm kiếm nhị phân ta có thể Test chơng trình với các bộ
test tơng ứng với kết quả là tìm thấy hoặc không tìm thấy.
Ví dụ 2: Với bài toán giải phơng trình bậc hai: Ta có thẻ Test chơng trình với các

Chu Thị Tú Anh