1. Khái niệm bài toán

SBD Họ và tên Văn Toán Lí Anh Tổng Kết quả

105 Lê Thị Thu 8.5 10.0 7.0 9.0 102 Vũ Ngọc Sơn 6.0 8.5 8.5 5.0 215 Trần Thuỷ 7.0 7.0 6.5 6.5 211 Nguyễn Anh 4.5 5.0 7.0 7.5 245 Phan Vân 5.0 2.0 3.5 4.5

Ví dụ 1: Quản lí điểm trong một kì thi bằng máy tính.

Yêu cầu :

Hãy xác định thông tin đưa vào (Input) và thông tin cần lấy ra (Output)

Input: SBD, Họ và tên, Văn, Toán, Lí, Anh.

 Output: Tổng điểm, Kết quả thi của học sinh.

53 Đỗ

42.5 Đỗ

41 Đỗ

33.5 Đỗ 22

Ví dụ 2: Giải phương trình bậc nhất ax + b = 0.

Yêu cầu :

Hãy xác định thông tin đưa vào (Input) và thông tin cần lấy ra (Output)

Input: Các hệ số a, b.

 Output: Nghiệm của phương trình.

Với a = 1, b = -5

 Phương trình có nghiệm x = 5

1. Khái niệm bài toán

Là việc nào đó ta muốn máy thực hiện để từ thông tin

đ

a vào (INPUT) tìm đ

ợc thông tin ra (OUTPUT).

Ví dụ 3: Tìm ước số chung lớn nhất của hai số nguyên dương.

INPUT: Hai số nguyên dương M và N.

OUTPUT: ước số chung lớn nhất của M và N.

Ví dụ 4: Bài toán xếp loại học tập của một lớp.

INPUT: Bảng điểm của học sinh trong lớp.

OUTPUT: Bảng xếp loại học lực của học sinh.

Bài 4. Bài toán và thuật Toán

2. Khái niệm thuật toán

Từ INPUT làm thế nào để tìm

ra OUTPUT ? Các em cần tìm ra

cách giải của bài toán.

Xét ví dụ 2: Giải phương trình bậc nhất ax + b = 0.

B1: Xác định hệ số a, b;

B2: Nếu a=0 và b=0 => Phương trình vô số nghiệm =>B5;

B3: Nếu a=0 và b≠0 => Phương trình vô nghiệm =>B5;

B4: Nếu a≠0 => Phương trình có nghiệm x=-b/a =>B5;

B5: Kết thúc.

Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đ

ợc sắp xếp theo một trình tự xác

định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận đ

ợc Output cần tìm.

Có hai cách thể hiện một thuật toán:

 Cách 1: Liệt kê các bước.

 Cách 2: Vẽ sơ đồ khối.

Quy ước các hỡnh khối trong sơ đồ thuật toán

Dùng để nhập và xuất dữ liệu.

Dùng để gán giá trị và tính toán.

Dựng để thể hiện thao tỏc so sỏnh.

Qui định trỡnh tự thực hiện cỏc thao tỏc.

ĐK

Cách 2: Vẽ sơ đồ khối

3. Mét sè vÝ dô vÒ thuËt to¸n

VD1. Tính chu vi và diện tích của hình chữ nhật khi biết chiều daì a và chiều rộng b.

*XĐBT: - Input: 2 số thực a, b.

- Output: chu vi và diện tích của hình chữ nhật

*Thuật toán:

Cách 2: Vẽ sơ đồ khối Nhập a, b

CV (a+b)*2;

DT  a*b;

Đưa CV và DT ra mh rồi kết

thúc

3. Mét sè vÝ dô vÒ thuËt to¸n

VD2. Cho số nguyên dương A. Hãy tính và xuất ra màn hình A là số chẵn hay A là số lẻ.

*XĐBT: - Input: Số nguyên dương A (A>0).

- Output: A là số chẵn hay A là số lẻ.

*Thuật toán:

Cách 1: Liệt kê các bước:

- B1: Nhập số nguyên dương A;

- B2: Nếu A=0 thì quay lại B1;

- B3: Nếu A mod 2=0 thì thông báo ra mh A là số chẵn rồi kết thúc; ngược lại thì thông báo ra mh A là số lẻ rồi kết thúc;

- Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác;

- Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo;

- Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.

*Các tính chất của thuật toán:

B1: NhËp a, b, c;

B2: TÝnh = b² – 4ac;

B3: NÕu < 0 => TB PT v« nghiÖm rồi kt;

B4: NÕu = 0

=> TB PT cã nghiÖm kÐp x = -b/2a rồi kt;

B5: NÕu > 0

=> TB PT cã hai nghiÖm x1, x2 = (-b  )/2a rồi kt;

3. Mét sè vÝ dô vÒ thuËt to¸n

VD3. ThuËt to¸n gi¶i phư¬ng tr×nh bËc hai (a  0).

C¸ch 1: LiÖt kª c¸c bưíc

Nhập vào a, b, c

 = b ^- 4ac

 < 0 TB PT vô nghiệm rồi kt

 = 0 TB PT có nghiệm x= -b/2a

đ

s

Sơ đồ thuật toán giải phương trình bậc hai

2

PT có 2 nghiệm x1,x2= ( -b )/2a

B1

B2

B3

B4

B5

s

đ

a,b,c= 1 3 5

 = 3*3 - 4*5 = - 11

-11 < 0 PT v« nghiÖm

 = 0 PT cã nghiÖm x = -b/2a KT

-11

 5

3 1

c b

a

S

PT cã 2 nghiÖm x1, x2 = (-b  )/2a

§

S

 = b*b - 4*a*c nhËp vµo a,b,c

 < 0

M« pháng thuËt to¸n gi¶i phư¬ng tr×nh bËc hai

Bé TEST 1:

a,b,c= 1 2 1

 = 2*2 - 4*1*1 = 0

PT v« nghiÖm

PT cã nghiÖm x=-b/2a BD

0

 1

2 1

c b

a

S

PT cã 2 nghiÖm x1, x2 = (-b  )/2a

§

S

 = b*b - 4*a*c nhËp vµo a,b,c

 < 0

M« pháng thuËt to¸n gi¶i phư¬ng tr×nh bËc hai

Bé TEST 2:

§

 = 0 PT cã nghiÖm kÐp x=-1

a,b,c= 1 -5 6

 = 25 - 24 = 1

TB PT v« nghiÖm rồi KT

PT cã nghiÖm x=-b/2a rồi kt BD

1

 6

-5 1

c b

a

S

PT cã 2 nghiÖm x1, x2 = (-b  )/2a

§

S

 = b*b - 4*a*c nhËp vµo a,b,c

 < 0

M« pháng thuËt to¸n gi¶i ph¬ng tr×nh bËc hai

Bé TEST 3:

§

 = 0

PT cã nghiÖm x1 = 3 x2 = 2

Thuật toán tìm max

3

Người ta đặt 5 quả bóng có kích thớc khác nhau trong hộp đã được đậy nắp như hình bên. Chỉ dùng tay hãy tìm ra quả bóng có kích thước lớn nhất .

Qu¶ nµy lín nhÊt

Qu¶ nµy míi lín

nhÊt

å! Qu¶

nµy lín h¬n T×m ra qu¶ lín nhÊt råi!

Cïng t×m thuËt to¸n

MAX

Thuật toán tìm số lớn nhất trong một dãy số nguyên

Xác định bài toán:

INPUT: Số nguyên dương N và dãy N số nguyên a₁, a₂, …, a_N (a_i với i: 1→N).

OUTPUT: Số lớn nhất (Max) của dãy số.

ý tưởng:

- Đặt giá trị Max = a₁.

- Lần lượt cho i chạy từ 2 đến N, so sánh giá trị a_i với giá trị Max, nếu a_i > Max thì

Max nhận giá trị mới là a_i.

C¸ch 1: LiÖt kª c¸c bưíc

B1: NhËp N vµ d·y a₁,…, a_N; B2: Max  a₁; i  2;

B3: NÕu i > N th× ®a ra gi¸ trÞ Max råi kÕt thóc;

B4:

Bíc 4.1: NÕu a_i > Max th× Max  a_i; Bíc 4.2: i  i+1 råi quay l¹i B3.

Đ S

Đ S

Nhập N và dóy a1,…,aN

Max  a1 ; i  2 i > N ?

a_i > Max ?

Max  a_i

i  i + 1

Đa ra Max rồi kết thúc

B1: Nhập N và dãy a₁,…,a_N;

B2: Max  a₁; i  2;

B3: Nếu i > N thì đa ra giá trị Max rồi kết thúc;

B4 :

4.1: Nếu a_i > Max thì Max  a_i; 4.2: i  i + 1 rồi quay lại B3.

Cách 2: Sơ đồ khối

§ S

§ S

NhËp N vµ d·y a1,…,aN

Max  a1 ; i  2

I > N ?

a_i> Max ?

Max a_i

i  i+1

§a ra Max råi kÕt thóc Max

i A

7 7

5 5

5

5 4

3 2

6 7

4 1

5

N=5 ; A [ 5 1 4 7 6 ]

Max  5 ; i  2

2 > 5 ?

1> 5 ?

i  2+1 3 > 5 ?

4> 5 ?

i 3+1 4 > 5 ?

7 > 5 ?

Max 7

4

i 4+1 5 > 5 ?

7 > 7 ?

i 5+1

6 > 5 ? Sè lín nhÊt cña d·y lµ 7

M« pháng thuËt to¸n

Víi i = 2 Víi i = 3 Víi i = 4 Víi i = 5

§ S

§ S

NhËp N vµ d·y a1,…,aN

Max  a1 ; i  2

I > N ?

a_i> Max ?

Max a_i

i  i+1

§a ra Max råi kÕt thóc Max

i A

7 7

5 5

5

5 4

3 2

6 7

4 1

5

N=5 ; A [ 5 1 4 7 6 ]

Max  5 ; i  2

2 > 5 ?

1> 5 ?

i  2+1 3 > 5 ?

4> 5 ?

i 3+1 4 > 5 ?

7 > 5 ?

Max 7

4

i 4+1 5 > 5 ?

7 > 7 ?

i 5+1

6 > 5 ? Sè lín nhÊt cña d·y lµ 7

Thuật toán sắp xếp

Hãy tìm cách sắp xếp học sinh đứng chào cờ (hình a) theo thứ tự thấp trớc cao sau (hình b).

Hình a Hình b

Thuật toán sắp xếp bằng tráo đổi

Xác định bài toán:

INPUT: Dãy A gồm N số nguyên a₁, a₂,…, a_N.

OUTPUT: Dãy A được sắp xếp thành dãy không giảm.

Thuật toán tìm kiếm tuần tự

Xác định bài toán:

INPUT: Dãy A gồm N số nguyên a₁, a₂,…, a_N đôi một khác nhau và số nguyên k.

OUTPUT: Chỉ số i mà a_i = k hoặc thông báo không có số hạng nào của A bằng k.

5 4

3 2

1 I

51 25

11 8

9 2

4 1

7 5

A

M« pháng thuËt to¸n t×m kiÕm tuÇn tù

 Víi k = 2 vµ d·y A gåm 10 sè h¹ng nh sau:

T¹i vÞ trÝ i = 5 cã a₅ = 2 = k

 Víi k = 6 vµ d·y A gåm 10 sè h¹ng nh sau:

A 5 7 1 4 2 9 8 11 25 51

I 1 2 3 4 5 6 7 8 9 10 11

Víi mäi i tõ 1→ 10 kh«ng cã a_i cã gi¸ trÞ b»ng 6

5

ý tởng:

Lần lợt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá (k) cho đến khi có sự trùng nhau, nếu đã xét tới số hạng cuối cùng mà không có sự trùng nhau thì có nghĩa là dãy A không có số hạng nào có giá trị bằng k.

C¸ch 1: LiÖt kª c¸c bíc

Bíc 1: NhËp N, c¸c sè h¹ng a₁, a₂,…, a_N vµ gi¸ trÞ kho¸ k;

Bíc 2: i  1;

Bíc 3: NÕu a_i = k th× th«ng b¸o chØ sè i, råi kÕt thóc;

Bíc 4: i  i+1;

Bíc 5: NÕu i > N th× th«ng b¸o d·y A kh«ng cã sè h¹ng nµo cã gi¸ trÞ b»ng k, råi kÕt thóc;

Bíc 6: Quay l¹i B3.