Bạn đang xem: Các dạng bài tập thuật toán tin học lớp 10 kèm hướng dẫn giải chi tiết Tại DongnaiArt

Trước khi áp dụng thành công các cách giải của từng dạng bài tập trong thuật toán máy tính lớp 10, các em cần ôn tập kỹ lý thuyết, nắm rõ bản chất của dạng bài, tránh các trường hợp phát sinh vấn đề trong học tập. Học vẹt có thể nhanh quên và nhầm lẫn khi hình thức hơi khác so với cách làm cơ bản.

Tóm tắt lý thuyết về các bài toán và thuật toán trong Bài 10:

Phiên bản tóm tắt giúp bạn xem lại các kiến ​​thức cơ bản và giúp bạn dễ dàng hiểu bản chất của các bài tập hơn.

Khái niệm vấn đề

– Các bài toán là những gì con người muốn máy tính thực hiện.

– Các yếu tố của câu hỏi:

+ Enter: Thông tin đã biết, nhập thông tin của máy tính.

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

-Ví dụ, để tìm ước số chung lớn nhất của hai số nguyên dương, hãy:

+ Dữ liệu vào: Hai số nguyên dương a, b.

+ output: ước chung lớn nhất của a và b

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

a) Các khái niệm

Thuật toán là một chuỗi hữu hạn các thao tác được sắp xếp theo một thứ tự nhất định để sau khi thực hiện chuỗi hoạt động đó, chúng ta nhận được kết quả mà chúng ta đang tìm kiếm từ đầu vào cho bài toán.

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

– Sử dụng phép liệt kê: Chỉ định thứ tự các thao tác cần thực hiện.

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

c) Các thuộc tính của thuật toán

– Tính ổn định: Thuật toán phải kết thúc sau một số lượng hữu hạn hoạt động.

– Tính xác định: Sau khi thực hiện một phép toán, thuật toán kết thúc hoặc có đúng 1 phép toán xác định cần thực hiện tiếp theo.

– Tính đúng đắn: Sau khi thuật toán được thực hiện, chúng ta phải nhận được kết quả mà chúng ta đang tìm kiếm.

Một số dạng bài tập thuật toán máy tính lớp 10 trang 1 và hướng dẫn cách giải:

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

• Xác định vấn đề

– Đầu vào: n là số nguyên dương;

– Dữ liệu ra: “n là số nguyên tố” hoặc “n không phải 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ó có đúng hai ước số 1 và n”

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

– Nếu 1

n <4 thì n là số nguyên tố.

-n≥4: tìm ước số đầu tiên i> 1.

+ Nếu i & lt; n thì n không nguyên tố (vì n có ít nhất 3 ước số 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, hãy chú ý đến “n không phải là số nguyên tố”, kết thúc;

-bước 3: Nếu n <4, thì lưu ý "n là số nguyên tố", kết thúc;

– Bước 4: i 2;

– Bước 5: Nếu tôi là ước của n, hãy chuyển đế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ông báo “n là số nguyên tố”, ngược lại, thông báo “n không phải là số nguyên tố”, kết thúc;

b) Sơ đồ khối

Lưu ý:

n là số nguyên tố nếu n> = 4 và không có ước số nào giữa 2 và căn bậc hai của n.

Loại 2: Sắp xếp theo Exchange

• Xác định vấn đề

– Đầu vào: dãy a gồm n số nguyên a1, a2, …, an

– Đầu ra: Mảng a được sắp xếp theo trình tự không giảm.

• Ý tưởng

– Đối với mỗi cặp mục liền kề trong dãy, nếu mục trước lớn hơn mục sau, chúng tôi hoán đổi chúng. (Số lớn được đẩy đến vị trí xác định ở cuối dãy).

– Lặp lại nhiều lần, thực hiện nhiều phép so sánh mỗi lần, cho đến khi không xảy ra hoán đổi nữa.

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

a) Cách liệt kê

– Bước 1: Nhập n, các mục a1, a2,…, an;

-bước 2: m n;

– bước 3: nếu m & lt; 2 thì cung cấp trình tự đã sắp xếp a và kết thúc;

Xem Thêm : Chứng chỉ TOEFL: Mọi điều bạn cần biết

– Bước 4: mm – 1, i 0;

– Bước 5: i ← i + 1;

– bước 6: nếu tôi> m thì quay lại bước 3;

– Bước 7: Nếu ai đó & gt; ai + 1 hoán đổi ai và ai + 1 với nhau;

-bước 8: quay lại bước 5;

b) Sơ đồ khối

Dạng 3: Câu hỏi Tìm kiếm

• Xác định vấn đề

– Đầu vào: Dãy a gồm n số nguyên phân biệt a1, a2, …, an và một số nguyên k (phím)

Ví dụ: a bao gồm các số nguyên ″ 5 7 1 4 2 9 8 11 25 51 ″ và k = 2 (k = 6).

– Đầu ra: Vị trí i cho ai = k hoặc thông báo k không được tìm thấy trong chuỗi. Vị trí của 2 trong dãy là 5 (không tìm thấy 6)

• Ý tưởng

Tìm kiếm tuần tự được thực hiện theo cách tự nhiên: bắt đầu từ cụm từ đầu tiên, chúng tôi so sánh giá trị của cụm từ được đề cập với khóa cho đến khi gặp cụm từ hoặc chuỗi bằng với khóa đã được xem xét. Không tìm thấy khóa trong phạm vi giá trị.

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

a) Cách liệt kê

– Bước 1: Nhập n, mục nhập a1, a2, …, an và giá trị khóa k;

– Bước 2: i 1;

-bước 3: nếu ai = k thì khai báo chỉ mục i, rồi kết thúc;

– Bước 4: i ← i + 1;

– Bước 5: Nếu i> n thì lưu ý rằng dãy a không có số hạng nào bằng k thì kết thúc;

-bước 6: quay lại bước 3;

b) Sơ đồ khối

Dạng 4: Tìm kiếm nhị phân

• Xác định vấn đề

– Dữ liệu vào: Dãy a là dãy tăng dần gồm n số nguyên phân biệt a1, a2, …, an và một số nguyên k.

Ví dụ: Dãy a bao gồm các số nguyên 2 4 5 6 9 21 22 30 31 33 và k = 21 (k = 25)

– Đầu ra: Không tìm thấy thông báo k ở vị trí i tại ai = k hoặc theo thứ tự. Vị trí 21 trong chuỗi là 6 (không tìm thấy 25)

• Ý tưởng

Sử dụng bản chất của trình tự sắp xếp tăng dần a, chúng tôi đã tìm ra một cách nhanh chóng để thu hẹp tìm kiếm bằng cách so sánh k với các từ ở giữa (giữa) phạm vi tìm kiếm và sau đó chỉ một trong ba trường xuất hiện. :

-Nếu a giữa = k thì tìm chỉ mục, kết thúc;

– nếu nằm giữa & gt; k thì thu hẹp tìm kiếm thành từ ada (range) → in – 1;

– Nếu giữa & lt; k thu hẹp tìm kiếm chỉ giữa + 1 → kết thúc (phạm vi).

Lặp lại quy trình trên cho đến khi tìm thấy khóa k trên phạm vi a hoặc phạm vi tìm kiếm trống.

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

a) Cách liệt kê

– Bước 1: Nhập n, mục nhập a1, a2, …, an và giá trị khóa k;

– Bước 2: Đầu tiên ← 1; Kết thúc ← n;

-Bước 3: Giữa ← [(đầu + cuối) / 2];

– Bước 4: Nếu ami = k thì khai báo chỉ số trung gian, sau đó kết thúc;

– bước 5: nếu abetween>; k thì đặt end = middle – 1 rồi chuyển sang bước 7;

– Bước 6: +1 ở giữa đầu;

– Bước 7: Nếu đầu> cuối cùng, thông báo k không được tìm thấy trên chuỗi thì hãy kết thúc;

– Bước 8: Quay lại Bước 3.

b) Sơ đồ khối

Một số bài tập trắc nghiệm về bài toán và thuật toán bài 10:

Phần 1:

A. Hiển thị các hoạt động tính toán

b. Thực hiện thao tác so sánh

c. Chỉ định thứ tự hoạt động

d. Hiển thị các hoạt động nhập và xuất dữ liệu

Câu 2: Các thuật toán rất quan trọng:

A. Độ chắc chắn, Khả năng kết nối, Tính đúng đắn

b. Sửa chữa, liên kết, xác định

c. Tính ổn định, chắc chắn, đúng đắn

d. Tuần tự: từ đầu vào đến đầu ra

Câu 3: Trong khoa học máy tính, sơ đồ khối là:

Xem Thêm : Chinh phục thử thách với Bongvip: Nhà cái đáng tin cậy cho những người chơi đam mê

A. Ngôn ngữ lập trình cấp cao

b. Sơ đồ mô tả thuật toán

c. Sơ đồ cấu trúc máy tính

d. Thiết kế sơ đồ vi điện tử

Câu 4 : Chọn phát biểu đúng về bài toán và thuật toán:

A. Trong máy tính, chúng ta có thể coi các vấn đề như những thứ chúng ta muốn máy tính thực hiện

b.Một thuật toán (thuật toán) giải bài toán là một dãy hữu hạn các phép toán được sắp xếp theo một thứ tự nhất định sao cho sau khi thực hiện chuỗi các phép toán, từ đầu vào của bài toán này, ta nhận được đầu ra để tìm

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

d. Ba câu trên đều đúng

Câu 5: Thuật toán sắp xếp hoán đổi các dãy số theo thứ tự tăng dần dừng lại khi nào?

A. Khi m = 1 và không còn chuyển vị nữa

b. Khi số tối đa trôi về cuối dãy

c. khi ai> ai + 1

d. Tất cả các tùy chọn

Câu 6 : Thuật toán tìm giá trị nhỏ nhất trong một dãy số nguyên bằng phương pháp được liệt kê dưới đây:

Bước 1: Nhập n, các mục a1, a2, …, an;

Bước 2: Ai tối thiểu, i 2;

Bước 3: Nếu tôi & lt; n thì hãy đưa ra giá trị nhỏ nhất và kết thúc;

Bước 4:

Bước 4.1: Nếu ai đó & gt; min thì min ai;

Bước 4.2: i i + 1, quay lại bước 3.

Đã chọn sai bước trong thuật toán trên:

A. Bước 2

b. Bước thứ ba

c. Bước 4.1

d. Bước 4.2

Câu 7: Một thuật toán tốt là một thuật toán:

A. Thời gian chạy nhanh

b. Giảm bớt bộ nhớ

c. a và b đều đúng

d. Tất cả các tùy chọn đều sai

Câu 8: Đầu vào cho câu hỏi: “Trao đổi giá trị của hai biến thực a và c với một biến trung gian b” là:

A. Hai số thực a, c

b. Hai số thực a, b

c. Hai số thực b, c

d. Ba số thực a, b, c

Câu hỏi 9: Câu hỏi về kiểm tra số nguyên tố của số nguyên dương n. Hãy xác định đầu ra của câu hỏi này?

A. n là số nguyên tố

b. n không phải là số nguyên tố

c. n là số nguyên tố hoặc n không phải số nguyên tố

d. Tất cả các ý trên đều sai

Phần 10: “… (1) là một dãy hữu hạn của … (2), được sắp xếp theo một thứ tự xác định sao cho khi thực hiện chuỗi hoạt động này, từ vấn đề of … (3), We get … (4) found ”. Cụm từ còn thiếu là gì?

A. đầu vào-đầu ra-thuật toán-hoạt động

b. Thuật toán-Hoạt động-Đầu vào-Đầu ra

c. Thuật toán-Hoạt động-Đầu ra-Đầu vào

d. hoạt động-thuật toán-đầu vào-đầu ra

Trả lời

Phần 1:

Trả lời: Một

Giải thích:

Khi thuật toán được biểu diễn bằng lưu đồ (sơ đồ khối):

+ Hình chữ nhật biểu diễn một phép tính.

+ Kim cương biểu thị sự so sánh.

+ Các mũi tên chỉ định trình tự hoạt động.

+ Hình elip biểu thị các thao tác nhập và xuất dữ liệu.

Câu 2:

Tải xuống tệp miễn phí Trọn bộ Lý thuyết + Nhiều Bài tập Giải thuật Máy tính Cấp 10 trang 1 và hướng dẫn cách giải:

Chúc bạn thành công!