BÀI TOÁN và THUẬT TOÁN

Chia sẻ: phanthai91

Ta cần diễn tả thuật toán bằng một ngôn ngữ sao cho máy tính có thể hiểu và thực hiện được, ngôn ngữ đó gọi là ngôn ngữ lập trình. Kết quả diễn tả thuật toán như vậy gọi là chương trình.

Bạn đang xem 10 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: BÀI TOÁN và THUẬT TOÁN

CHƯƠNG TRÌNH TIN HỌC LỚP 10


Chương I

Bài 4. BÀI TOÁN và  
          THUẬT TOÁN

GV: Đặng Bá Sáu 1
I. BÀI TOÁN
• Xét các yêu cầu sau :




Trong TOÁN HỌC Trong TIN HỌC
Trong các yêu cầu trên, yêu cầu
Yêu cầu 1 và 4 được Tất cả các yêu cầu trên
nào được xem như là một bài toán?
xem là bài toán đều được xem là bài toán
GV: Đặng Bá Sáu  2
Khái niệm bài toán trong 
Tin học?



Bài toán là việc nào đó ta 
muốn máy tính thực hiện.

GV: Đặng Bá Sáu  3
Các yếu tố cần quan tâm khi giải 
một bài toán
TOÁN HỌC TIN HỌC THUẬT NGỮ
- Giả thiết Đưa vào máy           Input
thông  tin gì     
TOÁN HỌC?
- Kết luận Cần lấy ra          Output
thông tin gì 


 Trong Tin học, để phát biểu một bài toán, ta cần 
trình bày rõ Input và Output của bài toán đó.
GV: Đặng Bá Sáu  4
CÁC VÍ DỤ
VD1 : Giải phương trình bậc hai
2

ax + bx + c = 0 (a ≠ 0).
 Input  : Các số thực a,b,c (a ≠ 0)
 Output : Số thực x thỏa : ax2+bx+ c = 0

VD2 : Tìm giá trị nhỏ nhất của các số
trong một dãy số.
 Input    : Các số trong dãy số.
 Output : Giá trị nhỏ nhất trong dãy số.
GV: Đặng Bá Sáu 5
CÁC VÍ DỤ (tt)
VD3 : Tìm ước chung lớn nhất của hai
số nguyên dương a và b.
 Input   :  ? số nguyên dương a và b.
Hai
 Output : ?
UCLN của a và b.
VD4 : Xếp loại học tập các học sinh
trong lớp.
 Input    : ?ảng điểm của học
B
 Output  : ?ảng xếp loại học tập.
sinh.
B
GV: Đặng Bá Sáu 6
Nê mộ    o và hỉ õ
u  tbàit án  c r  
I ,Out  ủa   o
nput  putc bàit án 
đó?

Xem thêm các ví dụ trong SGK/24, 25



GV:ĐặngBá 
    Sáu  7
TÓM LẠI

Một bài toán được cấu tạo bởi 2 thành
phần cơ bản :

 Input(Các thông tin đã có)
 Output (Các thông tin cần tìm từ Input)




8 GV: Đặng Bá Sáu
II. THUẬT TOÁN
Bài toán

Bằng cách nào?
Input Output


Giải bài toán
Thuật toán


Hướng dẫn các thao tác cho máy
thực hiện để tìm ra lời giải
GV: Đặng Bá Sáu  9
BÀI TOÁN

THUẬT TOÁN
Input Output
(Thao tác 1Thao tác 2...Thao tác n)


Thuật toán để giải một bài toán là :
Thuột toán hữugiải n cácbài toán là một dãy
• Mậ t dãy để hạ một thao tác.
hữu hạn các thao tác được sắp xếp theo
• Các thao xác định sắ xế sau khi thự
một trình tự tác được saopcho p theo một c
trình tự thao ịnh.
hiện dãy xác đtác đó, từ Input của bài toán
này, ta nhận được Output cần tìm.
• Sau khi thực hiện dãy thao tác đó, từ
Input ta tìm được Output của bài toán.
GV: Đặng Bá Sáu  10
MÔ TẢ CÁC THAO TÁC
TRONG THUẬT TOÁN
Nêu ra tuần tự các
thao tác cần tiến hành
Liệt kê
Có 2 cách mô tả
Dùng sơ đồ
khối
Dùng một số biểu tượng
thể hiện các thao tác
GV: Đặng Bá Sáu  11
a) LIỆT KÊ
VD : Tìm nghiệm phương trình bậc nhất tổng
quát : ax + b = 0 (q)
Giải toán thông thường:
LIỆT KÊ :
 Nế u a = 0 thì (( ) không • Bước 1 : Nhập a, b.
phải là pt bậc nhất. • Bước 2 : Nếu a = 0 thì
+ Neáu b = 0 thì (( ) quay lại bước 1, ngược lại
voâ số nghieäm. thì qua bước 3.
+ Neáu b ≠ 0 thì (( ) • Bước 3 : Gán cho x giá
voâ nghieäm. trị -b/a, rồi qua bước 4.
 Nế ua ≠ 0 thì (( ) có • Bước 4 : Đưa ra kết quả
nghiệm x = -b/a. x và kết thúc.
GV: Đặng Bá Sáu 12
b) DÙNG SƠ ĐỒ KHỐI
 Trong sơ đồ khối, người ta dùng một số
biểu tượng thể hiện các thao tác như :
: Thể hiện các thao tác nhập, xuất
dữ liệu
: Thể hiện các phép toán

: Thể hiện các thao tác so sánh

: Quy định trình tự thực hiện các
thao tác
GV: Đặng Bá Sáu 13
VD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0

LIỆT KÊ SƠ ĐỒ KHỐI

N haäp   
a,b
• Bước 1 : Nhập a, b.
• Bước 2 : Nếu a = 0 thì
quay lại bước 1, ngược Ñ uùn
  = 
a  0 g
lại thì qua bước 3.
• Bước 3 : Gán cho x Sai
giá trị -b/a, rồi qua
bước 4.  x  ­ a
  = b/
• Bước 4 : Đưa ra kết
quả x và kết thúc. Ñ öa  x  keát
ra  vaø  
GV: Đặng Bá Sáu  14
thuùc
LƯU Ý
Ta  cần  diễn  tả  thuật  toán  bằng  một 
ngôn  ngữ  sao  cho  máy  tính  có  thể 
hiểu và thực hiện được, ngôn ngữ đó 
gọi  là  ngôn  ngữ  lập  trình.  Kết  quả 
diễn  tả  thuật  toán  như  vậy  gọi  là 
chương trình.

GV: Đặng Bá Sáu  15
III. VÍ DỤ VỀ THUẬT TOÁN

Bài toán 1 : 
Cho dãy số gồm N số sau (N = 5):
11    6    20    4     8    
Tìm giá trị NHỎ NHẤT của dãy số trên ?




GV: Đặng Bá Sáu  16
H Ö Ô ÙNG   AÃN:
D
- Goïi M i laø giaù trò nhoû
n Min
nhaát caàn tìm.
- Gaùn M i baèng giaù trò
n Min=6
phaàn töû ñaàu tieân cuûa 11 6 20 4 8
daõy.i = 2
Gán
Min=11 Min=4
- Laàn löôït so saùnh M i n
vôùi caùc phaàn töû tieáp Giaù trò nhoû
theo trong daõy. Taïi moãi nhaát: 4
vò trí so saùnh :
Biến i lưu trữ vị trí
+ Neáu Min lôùn hôn giaù
tiếp theo mà Min sẽ
trò Tăng i lên 1 đcaàn so saùnh
+ phaàn töû ơn vị so sánh
trong daõy thì laáy giaù trò
cuûa phaàn töû ñoù gaùn laïi
cho Min.
GV: Đặng Bá Sáu  17
SƠ ĐỒ KHỐI : N haäp    daõy  1, ,
N vaø  a …  
aN

 M i =  1  i = 2
  n  a ,

Sai Ñ öa  M i
ra  n 
i  i
n  a
Ñ uùng
M i =  i
n  a


     i
  i= +1
GV: Đặng Bá Sáu  18
LIỆT KÊ








GV: Đặng Bá Sáu  19
4. VÍ DỤ VỀ THUẬT TOÁN (tt)
Bài toán 2 : 


Tìm giá trị LỚN NHẤT của một dãy số với Input và 
Output như sau:
• Input    : Số nguyên dương N và dãy N số 
a1,...,aN.
• Output : Giá trị lớn nhất (Max) của dãy số.


Mô tả thuật toán để giải bài toán này theo cả 2 
cách liệt kê và dùng sơ đồ khối.

GV: Đặng Bá Sáu  20
CÁC THUẬT NGỮ CHÍNH 
*Một dãy hữu hạn các thao tác.
• Bài toán *Các thao tác được sắp xếp theo
một trình tự xác định.
Là việc nào đó ta muốn
*Sau khi thực hiện dãy thao tác
• Input đó, từ máy tính thựược ện
Input ta tìm đ c hi Output
Các thông tin đã có
của bài toán.
• Output (các giả thiết)
Các thông tin cần tìm
• Thuật toán từ Input (kết luận)
Dùng các biểu tượng qui
• Sơ đồ khối ước để thể hiện các
GV: Đặng Bá Sáu 
thao tác trong thuật toán21
BÀ IT ẬP  Ề  H À
  V N

 Bài1,3,4,5,6 
       
trang  – 
27  28 
( K)
SG
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản