BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN

     

Nội dung bài học bài việc và thuật toán bên dưới đây để giúp các em tìm hiểu khái biệm bài toán trong Tin học, tư tưởng thuật toán, cách màn trình diễn thuật toán, đọc được dục tình giữa những khái niệm "Bài toán" – "Thuật toán" – "Ngôn ngữ lập trình", rèn cho những em năng lực biểu diễn các thuật toán tìm kiếm kiếm nhị phân, tìm kiếm tuần tự; thuật toán sắp tới xếp bằng phương pháp tráo đổi;... Mời các em thuộc theo dõi nội dung bài xích học.

Bạn đang xem: Bài 4: bài toán và thuật toán


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

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

1.2. Có mang thuật toán

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

2. Rèn luyện Bài 4 Tin học 10

2.1. Trắc nghiệm

2.2. Bài bác tập SGK

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


a. Khái niệmBài toán là một trong những việc nào này mà con bạn muốn laptop thực hiệnCác nguyên tố của một bài xích toán:Input: tin tức đã biết, thông tin đưa vào sản phẩm tínhOutput: tin tức cần tìm, thông tin mang ra từ sản phẩm công nghệ tínhb. Ví dụTìm USCLN của 2 số nguyên dươngTìm số lớn số 1 trong 3 số nguyê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 việc là:

Một hàng hữu hạn các làm việc (tính dừng)Các làm việc được thực hiện theo một trình từ bỏ xác định (tính xác định)Sau khi thực hiện hoàn thành dãy các làm việc đó ta nhận thấy Output của vấn đề (tính đúng đắn)b. Cách trình diễn thuật toán

Có 2 phương pháp để biểu diễn thuật toán:

Cách dùng phương thức liệt kê: Nêu ra tuần từ bỏ các thao tác cần tiến hànhVí dụ: Cho câu hỏi Tìm nghiệm của phương trình bậc 2: ax2 + bx + c = 0 (a≠0)?Xác định bài xích toánInput: các số thực a, b, cOutput: các số thực x vừa lòng ax2+ bx + c = 0 (a≠0)Thuật toán:Bước 1: Nhập a, b, c (a≠0)Bước 2: Tính Δ = b2 – 4acBước 3: ví như Δ>0 thì phương trình tất cả 2 nghiệm là(x_1=frac-b+sqrt riangle2a) ; (x_2=frac-b-sqrt riangle2a)rồi kết thúcBước 4: ví như Δ = 0 thì phương trình bao gồm nghiệm kép (x_1,2=frac-b2b)rồi dứt thuật toán.Nếu không gửi sang cách tiếp theoBước 5: kết luận phương trình vô nghiệm rồi kết thúcCách sử dụng sơ vật dụng khốiHình thoi
*
: thể hiện thao tác so sánh;Hình chữ nhật
*
: thể hiện những phép tính toán;Hình ô van
*
: thể hiện thao tác nhập, xuất dữ liệu;Các mũi tên
*
: chính sách trình tự triển khai các thao tác.

Xem thêm: Tác Dụng Của Khoai Tây Đắp Mặt Có Tác Dụng Gì, Tác Dụng Của Khoai Tây Trong Làm Đẹp


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


Bài toán 1: đánh giá tính nguyên tố

1. Xác minh bài toán

Input: N là một số trong những nguyên dươngOutput:N là số thành phần hoặcN không là số nguyên tốĐịnh nghĩa: "Một số nguyên dương N là số nguyên tố ví như nó chỉ có đúng hai ước là một trong những và N"Tính chất:Nếu N = 1 thì N ko là số nguyên tốNếu 1

2. Ý tưởng

NN>=4: Tìm cầu i trước tiên > 1 của NNếu i giả dụ i = N thì N là số nguyên tố

3. Thiết kế thuật toán

a) cách liệt kê

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

b) Sơ vật khối

*

Hình 1.Sơ đồ gia dụng khối thuật toán đánh giá tính nhân tố của một vài nguyên dương N

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

Bài toán 2: sắp đến xếp bằng cách tráo đổi

1. Khẳng định bài toán

Input: hàng A bao gồm N số nguyên a1, a2,…,anVí dụ : dãy A gồm các số nguyên: 2 4 8 7 1 5Output: hàng A được thu xếp thành dãy không giảmDãy A sau thời điểm sắp xếp: 1 2 4 5 7 8

2. Ý tưởng

Với từng cặp số hạng đứng liền kề trong dãy, nếu số trước > số sau ta đổi địa điểm chúng cho nhau. (Các số lớn sẽ tiến hành đẩy dần dần về vị trí khẳng định cuối dãy)Việc này lặp lại nhiều lượt, từng lượt triển khai nhiều lần so sánh cho tới khi không tồn tại sự đổi nơi nào xảy ra nữa

3. Tạo thuật toán

Bước 1. Nhập N, các số hạng a1, a2,…,an;Bước2. Đầu tiên call M là số số hạng cầnso sánh, vậy M sẽ đựng giá trịcủa N:(M leftarrow N);Bước3. Nếu như số số hạng cần đối chiếu Bước4. M đựng giá trị new là số phép so sánhcần triển khai trong lượt:(M leftarrow M-1). Hotline i là số vật dụng tự của mỗi lần so sánh, đầu tiên i 0;Bước5. Để triển khai lần so sánh mới,i tạo thêm 1 (lần đối chiếu thứ i)Bước6. Nếu lần so sánh thứ i> số phép so sánh M:đã hoàn chỉnh M số phép đối chiếu của lượt này.Lặp lại bước 3, bước đầu lượt kế (với số sốhạng cần đối chiếu mới chính là M đã sút 1ở bước 4);Bước7. đối chiếu 2 thành phần ở lần sản phẩm i là ai với ai+1.Nếu ai > ai+1 thì tráo thay đổi 2 thành phần này;Bước8. Quay trở về bước 5

a) Đối chiếu, hình thành quá trình liệt kê

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

b) Sơ trang bị khối

*

Hình 2. Sơ thứ khối thuật toánsắp xếp bằng phương pháp tráo đổi

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

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

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

2. Ý tưởng

Tìm tìm tuần trường đoản cú được triển khai một giải pháp tự nhiên: theo thứ tự đi từ số hạng đồ vật nhất, ta so sánh giá trị số hạng vẫn xét với khóa cho đến khi gặp mặt một số hạng bởi khóa hoặc dãy đã có được xét hết mà không kiếm thấy quý hiếm của khóa bên trên dãy.

3. Gây ra thuật toán

a) giải pháp liệt kê

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

b) Sơ đồ dùng khối

*

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

Bài toán 4: tra cứu kiếm nhị phân

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

Input: dãy A là dãy tăng có N số nguyên không giống nhau a1, a2,…,an và một số trong những nguyên k.Ví dụ: hàng A gồm những số nguyên:2 4 5 6 9 21 22 30 31 33.Và k = 21 (k = 25)Output : vị trí i nhưng ai = k hoặc thông báo không kiếm thấy k trong dãy.Vị trí của 21 trong dãy là 6(không search thấy 25)

2. Ý tưởng

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

Xem thêm: Bà Bầu Ăn Được Rau Dền Không Và Cần Lưu Ý Điều Gì? Mới Có Thai Ăn Rau Dền Được Không

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

a) giải pháp liệt kê

Bước 1: Nhập N, các số hạnga1, a2,…, aN và cực hiếm khoá k;Bước 2: Đầu (leftarrow)1; Cuối (leftarrow)N;Bước 3: thân <(Đầ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: trường hợp aGiữa > k thì đặt Cuối = thân - 1rồi chuyển sang bước 7;Bước 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 trên dãy, rồi kết thúc;Bước 8: quay trở về bước 3.

b) Sơ vật khối