Lý thuyết tin học 10: bài 4

Nội dung bài học kinh nghiệm bài Bài tân oán cùng thuật toán tiếp sau đây để giúp những em khám phá khái biệm bài bác tân oán vào Tin học, định nghĩa thuật toán, cách màn biểu diễn thuật toán, gọi được quan hệ nam nữ giữa những tư tưởng "Bài toán" – "Thuật toán" – "Ngôn ngữ lập trình", rèn cho các em tài năng màn trình diễn những thuật tân oán tra cứu tìm nhị phân, search kiếm tuần tự; thuật toán bố trí bằng cách tráo đổi;... Mời các em thuộc quan sát và theo dõi ngôn từ bài học.

Bạn đang xem: Lý thuyết tin học 10: bài 4


1. Tóm tắt lý thuyết

1.1. Khái niệm bài xích toán

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

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

2. Luyện tập Bài 4 Tin học 10

2.1. Trắc nghiệm

2.2. các bài tập luyện SGK

3. Hỏi đápBài 4 Tin học 10


a. Khái niệmBài toán là 1 trong những vấn đề nào đó mà bé fan hy vọng máy tính xách tay thực hiệnCác nguyên tố của một bài xích toán:Input: tin tức đã biết, biết tin gửi vào lắp thêm tínhOutput: tin tức đề xuất tra cứu, thông báo lấy ra tự sản phẩm tínhb. Ví dụTìm USCLN của 2 số ngulặng dươngTìm số lớn nhất trong 3 số nguyên ổn dương a,b,cTìm nghiệm của phương trình bậc nhất: ax + b = 0 (a≠0)...
a. Khái niệm

Thuật toán nhằm giải một bài toán là:

Một dãy hữu hạn những thao tác (tính dừng)Các thao tác được triển khai theo một trình từ xác định (tính xác định)Sau lúc tiến hành hoàn thành dãy các thao tác kia ta cảm nhận Output đầu ra của bài toán thù (tính đúng đắn)b. Cách màn biểu diễn thuật toán

Có 2 phương pháp để trình diễn thuật toán:

Cách dùng cách thức liệt kê: Nêu ra tuần tự các thao tác nên tiến hànhVí dụ: Cho bài toán Tìm nghiệm của pmùi hương trình bậc 2: ax2 + bx + c = 0 (a≠0)?Xác định bài toánInput: Các số thực a, b, cOutput: Các số thực x thỏa mãn nhu cầu ax2+ bx + c = 0 (a≠0)Thuật toán:Cách 1: Nhập a, b, c (a≠0)Cách 2: Tính Δ = b2 – 4acCách 3: Nếu Δ>0 thì pmùi hương trình có 2 nghiệm là(x_1=frac-b+sqrt riangle2a) ; (x_2=frac-b-sqrt riangle2a)rồi kết thúcCách 4: Nếu Δ = 0 thì pmùi hương trình có nghiệm kép (x_1,2=frac-b2b)rồi xong thuật toán thù.Nếu không chuyển thanh lịch bước tiếp theoCách 5: Tóm lại phương trình vô nghiệm rồi kết thúcCách sử dụng sơ đồ vật khốiHình thoi
*
: miêu tả thao tác so sánh;Hình chữ nhật
*
: biểu đạt những phxay tính toán;Hình ô van
*
: biểu lộ thao tác nhập, xuất dữ liệu;Các mũi tên
*
: hiệ tượng trình tự thực hiện các làm việc.

Xem thêm: Các Dạng Toán Có Lời Văn Lớp 3 00 Bài Toán Có Lời Văn Cơ Bản Lớp 3


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


Bài toán 1: Kiểm tra tính nguim tố

1. Xác định bài xích toán

Input: N là một vài nguyên ổn dươngOutput:N là số nguyên tố hoặcN không là số nguim tốĐịnh nghĩa: "Một số nguyên ổn dương N là số nguim tố trường hợp nó chỉ tất cả đúng nhị ước là 1 cùng N"Tính chất:Nếu N = 1 thì N không là số nguyên ổn tốNếu 1

2. Ý tưởng

NN>=4: Tìm ước i trước tiên > 1 của NNếu i Nếu i = N thì N là số ngulặng tố

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

a) Cách liệt kê

Cách 1: Nhập số nguim dương N;Cách 2: Nếu N=1 thì thông báo "N ko là số nguyên ổn tố", kết thúc;Bước 3: Nếu NBước 4:(i leftarrow2 ;)Cách 5: Nếu i là ước của N thì cho đến bước 7Bước 6: (i leftarrow i +1)rồi quay lại bước 5; (Tăng i lên 1 1-1 vị)Cách 7: Nếu i = N thì thông báo "N là số nguim tố", ngược chở lại thì thông tin "N không là số ngulặng tố", kết thúc;

b) Sơ vật dụng khối

*

Hình 1.Sơ đồ vật khối hận thuật toán thù khám nghiệm tính nguim tố của một trong những nguyên ổn dương N

Lưu ý:Nếu N >= 4 cùng không có ước trong phạm vi từ 2 mang lại phần nguyên ổn căn uống bậc 2 của N thì N là số nguyên ổn tố

Bài toán 2: Sắp xếp bằng phương pháp tráo đổi

1. Xác định bài xích toán

Input: Dãy A có N số nguyên a1, a2,…,anlấy ví dụ như : Dãy A bao gồm các số nguyên: 2 4 8 7 1 5Output: Dãy A được thu xếp thành dãy ko giảmDãy A sau khoản thời gian sắp xếp: 1 2 4 5 7 8

2. Ý tưởng

Với mỗi cặp số hạng đứng liền kề vào hàng, giả dụ số trước > số sau ta thay đổi vị trí bọn chúng lẫn nhau. (Các số phệ sẽ tiến hành đẩy dần về địa điểm xác minh cuối dãy)Việc này tái diễn các lượt, mỗi lượt thực hiện những lần đối chiếu cho đến Lúc không tồn tại sự đổi ở đâu xảy ra nữa

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

Bước 1. Nhập N, những số hạng a1, a2,…,an;Bước2. trước hết Gọi M là số số hạng cầnđối chiếu, vậy M sẽ chứa giá trịcủa N:(M leftarrow N);Bước3. Nếu số số hạng nên đối chiếu Bước4. M cất quý giá bắt đầu là số phép so sánhnên thực hiện vào lượt:(M leftarrow M-1). Hotline i là số lắp thêm tự của mỗi lần đối chiếu, trước tiên i 0;Bước5. Để thực hiện lần so sánh mới,i tăng thêm 1 (lần đối chiếu lắp thêm i)Bước6. Nếu lần đối chiếu thiết bị i> số phnghiền đối chiếu M:đã hoàn toàn M số phnghiền so sánh của lượt này.Lặp lại bước 3, bắt đầu lượt kế (với số sốhạng bắt buộc so sánh new đó là M đang sút 1sinh hoạt bước 4);Bước7. So sánh 2 bộ phận làm việc lần thứ i là ai với ai+1.Nếu ai > ai+1 thì tráo thay đổi 2 bộ phận này;Bước8. Quay lại bước 5

a) Đối chiếu, sinh ra công việc liệt kê

Bước 1: Nhập N, những số hạng a1, a2,…,an;Cách 2:(M leftarrow N ;)Bước 3: Nếu M Bước 4:(M leftarrow M-1 ; i leftarrow 0 ;)Bước 5:( i leftarrow i - 1 ;)Bước 6: Nếu i > M thì trở về bước 3;Bước 7: Nếu ai > ai+1 thì tráo thay đổi ai với ai+1 cho nhau;Cách 8: Quay lại bước 5;

b) Sơ đồ vật khối

*

Hình 2. Sơ trang bị khối thuật toánthu xếp bằng cách tráo đổi

Bài toán 3: Tìm tìm tuần tự

1. Xác định bài xích toán

Input : Dãy A có N số nguim khác nhau a1, a2,…,an và một số nguyên k (khóa)lấy ví dụ : Dãy A bao gồm những số nguyên:5 7 1 4 2 9 8 11 25 51 . Và k = 2 (k = 6)Output: Vị trí i cơ mà ai = k hoặc thông báo không kiếm thấy k vào dãy. Vị trí của 2 trong dãy là 5 (không tìm thấy 6)

2. Ý tưởng

Tìm kiếm tuần trường đoản cú được triển khai một bí quyết từ bỏ nhiên: Lần lượt đi trường đoản cú số hạng thứ nhất, ta đối chiếu cực hiếm số hạng vẫn xét với khóa cho đến khi chạm chán một số hạng bởi khóa hoặc hàng đã làm được xét hết nhưng không tìm thấy cực hiếm của khóa trên hàng.

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

a) Cách liệt kê

Cách 1: Nhập N, những số hạng a1, a2,…, aN cùng giá trị khoá k;Cách 2:(i leftarrow 1;)Bước 3: Nếu ai = k thì thông tin chỉ số i, rồi kết thúc;Cách 4:(i leftarrow i + 1;)Bước 5: Nếu i > N thì thông báo hàng A không có số hạng làm sao có giá trị bằng k, rồi kết thúc;Bước 6: Quay lại bước 3;

b) Sơ vật khối

*

Hình 3. Sơ đồ khối thuật toán thù tìm kiếm tuần tự

Bài toán 4: Tìm tìm nhị phân

1. Xác định bài bác toán

Input: Dãy A là hàng tăng gồm N số nguyên ổn khác nhau a1, a2,…,an với một trong những nguyên ổ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)Output đầu ra : Vị trí i mà lại ai = k hoặc thông tin không tìm thấy k trong dãy.Vị trí của 21 trong những dãy là 6(không tìm thấy 25)

2. Ý tưởng

Sử dụng tính chất hàng A đã thu xếp tăng, ta tìm kiếm cách thu thon nhanh hao vùng tìm kiếm tìm bằng phương pháp so sánh k với số hạng trung tâm phạm vi search kiếm (agiữa), khi đó chỉ xảy ra 1 trong các cha ngôi trường hợp:Nếu agiữa= k thìkiếm được chỉ số, kết thúc;Nếu agiữa > k thì việc tìm kiếm thu không lớn chỉ xét từ ađầu (phạm vi) ( ightarrow)agiữa - 1;Nếu agiữa thân + 1 ( ightarrow)acuối (phạm vi).Quá trình trên được lặp lại cho tới Lúc tìm thấy khóa k bên trên hàng A hoặc phạm vi tra cứu kiếm bằng trống rỗng.

Xem thêm: Tìm Số Hạng Đầu Và Công Sai Của Cấp Số Cộng Cực Hay, Lý Thuyết Cấp Số Cộng

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

a) Cách liệt kê

Bước 1: Nhập N, những số hạnga1, a2,…, aN và cực hiếm khoá k;Cách 2: Đầu (leftarrow)1; Cuối (leftarrow)N;Cách 3: Giữa <(Đầu+Cuối)/2>;Bước 4: Nếu aGiữa = k thì thông báochỉ số Giữa, rồi kết thúc;Bước 5: Nếu aGiữa > k thì đặt Cuối = Giữa - 1rồi gửi sang trọng bước 7;Cách 6: Đầu (leftarrow)Giữa + 1;Bước 7: Nếu Đầu > Cuối thì thông báo không tìm thấy khóa k bên trên dãy, rồi kết thúc;Bước 8: Quay lại bước 3.

b) Sơ trang bị khối


Chuyên mục: Kiến thức thú vị