Bai 4 Bai toan va thuat toan

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (275.56 KB, 22 trang )

(1)<div class='page_container' data-page=1>

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

(SGK thí điểm)

Chương I

Bài 4.

BÀI TỐN và

</div>
(2)<div class='page_container' data-page=2>

• Xét các yêu cầu sau :

1. Giải phương trình bậc hai ax

+bx+c=0

2. Viết một dịng chữ ra màn hình máy tính.

3. Quản lý các cán bộ trong một cơ quan.

4. Tìm ước chung lớn nhất của hai số

nguyên dương a và b.

5. Xếp loại học tập các học sinh trong lớp.

I. BÀI TOÁN

Trong TIN HỌC
Trong TOÁN HỌC

Yêu cầu 1 và 4 được 
xem là bài toán

Tất cả các yêu cầu trên 
đều được xem là bài toán



Trong các yêu cầu trên, yêu cầu

</div>
(3)<div class='page_container' data-page=3>

Khái niệm

bài toán

bài toán

trong

trong

Tin học?

Bài tốn

là việc nào đó

</div>
(4)<div class='page_container' data-page=4>

TIN HỌC

Đưa vào máy 
 thông tin gì

Cần lấy ra

thơng tin gì

TOÁN HỌC?

Các yếu tố cần quan tâm khi

giải một bài toán

 Trong Tin học, để phát biểu một bài tốn, ta cần

trình bày rõ Input và Output của bài tốn đó.

TỐN HỌC

-

Giả thiết

-

Kết luận

THUẬT NGỮ

Input

</div>
(5)<div class='page_container' data-page=5>

CÁC VÍ DỤ

VD1 :

Giải phương trình bậc hai

ax

2

+ bx + c = 0 (a ≠ 0).



Input

:

Các số thực a,b,c (a ≠ 0)



Output

:

Số thực x thỏa : ax

+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ố.

</div>
(6)<div class='page_container' data-page=6>

VD3 :

Tìm ước chung lớn nhất của hai số

nguyên dương a và b.



Input :



Output :

VD4 :

Xếp loại học tập các học sinh trong

lớp.



Input :



Output :

UCLN của a và b.

Hai số nguyên dương a và b.

CÁC VÍ DỤ (tt)

?

</div>
(7)<div class='page_container' data-page=7>

Nêu m t bài toán và

ộ

ch rõ Input, Output

ỉ

c a bài tốn đó?

ủ

</div>
(8)<div class='page_container' data-page=8>

TĨM LẠI

Một bài tốn được cấu tạo bởi 2 thành

phần cơ bản :



Input

(Các thơng tin đã có)

</div>
(9)<div class='page_container' data-page=9>

II. 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

Bài tốn

Input

Bằng cách nào?

Output

Giải bài tốn

</div>
(10)<div class='page_container' data-page=10>

Input

THUẬT TỐN

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à 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 đó, từ Input của bài tốn

này, ta nhận được Output cần tìm.

BÀI TỐN

Thuật tốn để giải một bài tốn là :

• Một dãy hữu hạn các thao tác.

• Các thao tác được sắp xếp theo một

trình tự xác định.

• Sau khi thực hiện dãy thao tác đó, từ

</div>
(11)<div class='page_container' data-page=11>

MƠ TẢ CÁC THAO TÁC

TRONG THUẬT TỐN

Có 2 cách mơ tả

Liệt kê

Dùng sơ đồ khối

Nêu ra tuần tự các thao

tác cần tiến hành

</div>
(12)<div class='page_container' data-page=12>

Giải tốn thơng thường:

 Nếu a = 0 thì () khơng

phải là pt bậc nhất.

Neáu b = 0 thì

()

vô

s nghiệm.

ố

+

Nếu b

≠

0 thì

()

vô

nghiệm.

 Nếu a ≠ 0 thì () có

nghiệm x = -b/a.

a) LIỆT KÊ

LIỆT KÊ :

• Bước 1 : Nhập a, b.

• Bước 2 : Nếu a = 0 thì
quay lại bước 1, ngược lại
thì qua bước 3.

• Bước 3 : Gán cho x giá
trị -b/a, rồi qua bước 4.

• Bước 4 : Đưa ra kết quả
x và kết thúc.

</div>
(13)<div class='page_container' data-page=13>

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

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 phép tốn

: Quy định trình tự thực hiện các

thao tác

</div>
(14)<div class='page_container' data-page=14>

VD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0

Nhaäp a, b

a = 0

x = -b/a

Sai

Đúng

Đưa ra x và kết thúc

• Bước 1

:

Nhập a, b.

• Bước 2 :

Nếu a = 0 thì

quay lại bước 1, ngược

lại thì qua bước 3.

• Bước 3 :

Gán cho x

giá trị -b/a, rồi qua bước

4.

• Bước 4 :

Đưa ra kết

quả x và kết thúc.

</div>
(15)<div class='page_container' data-page=15>

Ta cần diễn tả thuật tố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

.

</div>
(16)<div class='page_container' data-page=16>

III. VÍ DỤ VỀ THUẬT TỐN

Bài tốn 1 :

Cho dãy số gồm N số sau (N = 5):

11 6 20 4 8

</div>
(17)<div class='page_container' data-page=17>

HƯỚNG DẪN:

- Gọi Min là giá trị nhỏ nhất cần
tìm.

- Gán Min bằng giá trị phần tử đầu

tiên của dãy.

- Lần lượt so sánh Min với các
phần tử tiếp theo trong dãy. Tại
mỗi vị trí so sánh :

+ Nếu Min lớn hơn giá trị phần

tử cần so sánh trong dãy thì lấy giá
trị của phần tử đó gán lại cho Min.

- Khi so sánh đến phần tử cuối
cùng trong dãy số thì Min sẽ mang

giá trị nhỏ nhất của dãy.

Gán i = 2

11 6 20 4 8

Min

Min=11

Min=6

Min=4

Giá trị nhỏ nhất:

4

Biến i lưu trữ vị trí

tiếp theo mà Min sẽ
so sánh

</div>
(18)<div class='page_container' data-page=18>

SƠ ĐỒ KHỐI :

SƠ ĐỒ KHỐI : Nhập N và dãy a1,…, aN

Min = a1 , i = 2
i <=N

Min > ai

Min = ai
 i = i+1

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

Sai
Đúng

</div>
(19)<div class='page_container' data-page=19>

LIỆT KÊ



Bước 1 :

Nhập N và dãy a

1

,…, a

N

.



Bước 2 :

Đặt Min= a

1

, i=2;



Bước 3 :

Nếu i<=N thì thực hiện bước 4, nếu

khơng thì chuyển đến bước 5.



Bước 4 :

4.1.

Neáu Min > a

i

thì đặt Max=a

i

.

4.2.

Tăng i một đơn vị rồi quay về bước 3

</div>
(20)<div class='page_container' data-page=20>

Bài tố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.

</div>
(21)<div class='page_container' data-page=21>

CÁC THUẬT NGỮ CHÍNH

Là việc nào đó ta muốn

máy tính thực hiện

Các thơng tin đã có

(các giả thiết)

Các thơng tin cần tìm

từ Input (kết luận)

*Một dãy hữu hạn các thao tác.
*Các thao tác được sắp xếp theo
một trình tự xác định.

*Sau khi thực hiện dãy thao tác
đó, từ Input ta tìm được Output
của bài toán.

Dùng các biểu tượng qui

ước để thể hiện các thao

tác trong thuật tốn

• Bài tốn

• Input

• Output

• Thuật tốn

</div>
(22)<div class='page_container' data-page=22>

Bai 4 Bai toan va thuat toan

<b>CHƯƠNG TRÌNH TIN HỌC LỚP 10</b>

<b> (SGK thí điểm)</b>

<b>Chương I</b>

<b>Bài 4.</b>

<b>BÀI TỐN và </b>

•

<b>Xét các yêu cầu sau :</b>

1. Giải phương trình bậc hai ax

+bx+c=0

2. Viết một dịng chữ ra màn hình máy tính.

3. Quản lý các cán bộ trong một cơ quan.

4. Tìm ước chung lớn nhất của hai số

nguyên dương a và b.

5.

Xếp loại học tập các học sinh trong lớp.

<b>I. BÀI TOÁN</b>

<b>I. BÀI TOÁN</b>



<b>Trong các yêu cầu trên, yêu cầu </b>

<b>Khái niệm </b>

<b>Khái niệm </b>

<i><b>bài toán</b></i>

<i><b><sub>bài toán</sub></b></i>

<b> trong </b>

<b><sub> trong </sub></b>

<b>Tin học?</b>

<b>Tin học?</b>

<i><b>Bài tốn</b></i>

<b> là việc nào đó </b>

<b>TIN HỌC</b>

<b>Cần lấy ra </b>

<b>thơng tin gì </b>

<b>TOÁN HỌC?</b>

<b>TOÁN HỌC?</b>

<b>Các yếu tố cần quan tâm khi </b>

<b>Các yếu tố cần quan tâm khi </b>

<b>giải một bài toán</b>

<b>giải một bài toán</b>

<b>TỐN HỌC</b>

-

<b> Giả thiết</b>

-

<b> Kết luận</b>

<b> </b>

<b>Input</b>

<b> </b>

<b>CÁC VÍ DỤ</b>

<b>VD1 :</b>

<b>Giải phương trình bậc hai </b>

<b>ax</b>

<b>+ bx + c = 0 (a ≠ 0).</b>

<b>Input</b>

<b>:</b>

Các số thực a,b,c (a ≠ 0)

<b>Output</b>

<b>:</b>

Số thực x thỏa : ax

+bx+ c = 0

<b>VD2 :</b>

<b>Tìm giá trị nhỏ nhất của các số </b>

<b>trong một dãy số.</b>

<b>Input :</b>

Các số trong dãy số.

<b>VD3 :</b>

<b>Tìm ước chung lớn nhất của hai số </b>

<b>nguyên dương a và b.</b>

<b>Input : </b>

<b>Output :</b>

<b>VD4 :</b>

<b>Xếp loại học tập các học sinh trong </b>

<b>lớp. </b>

<b>Input :</b>

<b>Output :</b>

UCLN của a và b.

Hai số nguyên dương a và b.

<b>CÁC VÍ DỤ (tt)</b>

?

?

?