Lớp 10TIn Học

Chọn phát biểu đúng khi nói về Bài toán và thuật toán | Tin học 10

Câu hỏi: Chọn phát biểu đúng khi nói về Bài toán và thuật toán

A. Trong phạm vi Tin học, ta có thể quan niệm bài toán là việc nào đó mà ta muốn máy tính thực hiện

B. Thuật toán (giải thuật) để 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 toán này, ta nhận được Output cần tìm

Bạn đang xem: Chọn phát biểu đúng khi nói về Bài toán và thuật toán | Tin học 10

C. Sơ đồ khối là sơ đồ mô tả thuật toán

D. Cả ba câu trên đều đúng

Trả lời:

Đáp án đúng: B. Thuật toán (giải thuật) để 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 toán này, ta nhận được Output cần tìm

Giải thích: 

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

+ Thuật toán giải thuật để 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 toán này, ta nhận được Output cần tìm. 

+ Sơ đồ khối là sơ đồ mô tả thuật toán.

Cùng THPT Ninh Châu tìm hiểu những kiến thức hữu ích về Bài toán và thuật toán nhé!

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

– Bài toán là một việc nào đó mà con người muốn máy tính thực hiện

– Các yếu tố của một bài toán:

   + Input: Thông tin đã biết, thông tin đưa vào máy tính

   + Output: Thông tin cần tìm, thông tin lấy ra từ máy tính

– Ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương, khi đó:

   + Input: hai số nguyên dương A, B.

   + Output: ước chung lớn nhất của A và B

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

a. Khái niệm

   – Thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 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.

b. Biểu diễn thuật toán

   – Sử dụng cách liệt kê: nêu ra tuần tự các thao tác cần tiến hành

   – Sử dụng sơ đồ khối để mô tả thuật toán.

Ví dụ: Tìm giá trị lớn nhất của 1 dãy số nguyên.

=> Ta có 3 bước thực hiện như sau:

* Xác định BT

– Input: Số nguyên dương N và dãy N số nguyên a1, a2, …, aN.

– Output: Giá trị lớn nhất Max của dãy số.

* Ý tưởng

– Khởi tạo giá trị Max = a1.

– Lần lượt với i từ 2 đến N so sánh ai với Max, nếu ai > Max thì Max = ai.

* Thuật toán:

Cách liệt kê:

+ B1: Nhập N và dãy a1,…,aN;

+ B2: Max ← a1, i ← 2;

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

+ B4: Nếu ai > Max thì Max ← ai;

+ B5: i ← i+1 rồi quay lại bước 3;

Cách lập sơ đồ khối:

– Thuật toán còn được diễn tả bằng sơ đồ khối.

– Quy định:

+ Hình ô van: các thao tác nhập, xuất dữ liệu.

+ Hình thoi: Thao tác so sánh.

+ Hình chữ nhật: Các phép toán.

+ Mũi tên: trình tự thực hiện các thao tác.

Ví dụ: Mô phỏng việc thực hiện thuật toán với N = 8 và dãy số: 5, 1, 4, 7, 6, 3, 15, 11

Ds

5

1

4

7

6

3

15

11

i

2

3

4

5

6

7

8

9

Max

5

5

5

7

7

7

15

15

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

+ 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 một số lần thực hiện thao tác, hoặc là kết thúc hoặc xác định để thực hiện bước 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.

3. Một số ví dụ về thuật toán

Ví dụ 1: Kiểm tra tính nguyên tố của 1 số nguyên dương

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

– Input: N là một số nguyên dương

– Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″

* Ý tưởng:

– Định nghĩa: ″Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N″

– Nếu N = 1 thì N không là số nguyên tố

– Nếu 1 < N < 4 thì N là số nguyên tố

– N ≥ 4: Tìm ước i đầu tiên > 1 của N

   + Nếu i < N thì N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N)

   + Nếu i = N thì N là số nguyên tố

* Xây dựng thuật toán

a. Cách liệt kê

   – Bước 1: Nhập số nguyên dương N;

   – Bước 2: Nếu N = 1 thì thông báo ″N không là số nguyên tố″, kết thúc;

   – Bước 3: Nếu N < 4 thì thông báo ″N là số nguyên tố″, kết thúc;

   – Bước 4: i ← 2;

   – Bước 5: Nếu i là ước của N thì đến bước 7

   – Bước 6: i ← i + 1 rồi quay lại bước 5; (Tăng i lên 1 đơn vị)

   – Bước 7: Nếu i = N thì thông báo ″N là số nguyên tố″, ngược lại thì thông báo ″N không là số nguyên tố″, kết thúc;

b) Sơ đồ khối

Chọn phát biểu đúng khi nói về Bài toán và thuật toán (ảnh 2)

4. Hướng dẫn làm một số bài tập

Câu 1: Trang 44 SGK Tin học 10

Hãy phát biểu một bài toán và chỉ rõ Input và Output của bài toán đó.

Trả lời:

Ví dụ bài toán tính diện tích tam giác

Phát biểu bài toán:

Cho ba cạnh của tam giác ABC là: x, y, z. Hãy tính diện tích tam giác ABC.

– Input: Ba cạnh tam giác x, y, z.

– Output: Diện tích tam giác.

Câu 2: Trang 44 SGK Tin học 10

Dãy các thao tác sau:

Bước 1. Xoá bảng;

Bước 2. Vẽ đường tròn;

Bước 3. Quay lại bước 1; có phải là thuật toán không? Tại sao?

Hãy mô tả thuật toán giải các bài toán sau bàng cách liệt kê hoặc bằng sơ đồ khối.

Trả lời:

Dãy các thao tác sau:

Bước 1. Xoá bảng;

Bước 2. Vẽ dường tròn;

Bước 3. Quay lại bước 1;

Đây không phải là thuật toán, vì không thoả mãn tính chất dừng: đến bước 3 lại quay lại bước 1, nó tạo thành vòng lặp vô hạn không có điều kiện kết thúc.

Câu 3: Trang 44 SGK Tin học 10

Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.

Trả lời:

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

Bước 1. Nhập N, các số hạng a1, a2,…aN và khoá k

Bước 2. i

Bước 3. Nếu ai = k thì thông báo chỉ số i, rồi kết thúc;

Bước 4. i

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ị nào bằng k, rồi kết thúc;

Bước 6. Quay lại bước 3.

Tính dùng cùa thuật toán tìm kiếm tuần tự: nghĩa là thuật toán phải kết thúc sau một số hữu hạn lần bước tính.

Thuật toán chia làm hai trường hợp

– Nếu tìm thấy giá trị cần tìm trong dãy A (ai= k) thì thông báo chỉ số i (vị trí tìm thấy khoá k trong dãy A), rồi kết thúc.

– Nếu không tìm thấy giá trị cần tìm trong dãy A, vì bước 4 thực hiện việc tăng giá trị của i lớn hơn 1, nên sau N lần thì i > N, thông báo dãy A không có giá trị nào bằng k, rồi kết thúc

Đăng bởi: THPT Văn Hiến

Chuyên mục: Lớp 10, Tin Học 10

Trả lời

Email của bạn sẽ không được hiển thị công khai.

Back to top button