Tin học 10 Bài 4: Bài toán và thuật toán – HOC247


Đánh giá bài viết này

Thông qua bài viết này, chúng tôi hy vọng sẽ giúp bạn hiểu thêm về thuật toán tin 10 là gì Hay nhất và đầy đủ nhất do thcs thai van lung biên soạn

một. Ý tưởng

  • Vấn đề là điều mà con người muốn máy tính làm
  • Các yếu tố của một vấn đề:
    • Đầu vào: Thông tin đã biết, thông tin nhập vào máy tính
    • Đầu ra: Thông tin cần tìm, thông tin lấy từ máy tính

b. Ví dụ

  • Tìm USCLN của 2 số nguyên dương
  • Tìm số lớn nhất trong 3 số nguyên dương a,b,c
  • Tìm nghiệm của phương trình bậc hai: ax + b = 0 (a≠0)

một. Ý tưởng

thuật toán để giải quyết một vấn đề là:

  • Một chuỗi hữu hạn các hoạt động (dừng đếm)
  • Các thao tác được thực hiện theo trình tự xác định (quyết định)
  • Sau khi thực hiện dãy thao tác ta được Đầu ra của bài toán (sự đúng đắn)

b. Cách biểu diễn thuật toán

Có hai cách để biểu diễn thuật toán:

  • Cách sử dụng phương pháp liệt kê: Nêu trình tự các thao tác thực hiện
    • Ví dụ: Cho bài toán Tìm nghiệm của phương trình bậc hai: ax2 + bx + c = 0 (a≠0)?
    • Xác định vấn đề
      • Dữ liệu vào: Các số thực a, b, c
      • Output: Các số thực x thỏa mãn 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 – 4ac
      • Bước 3: Nếu > 0 thì phương trình có 2 nghiệm là
      • (x_{1}=frac{-b+sqrt{triangle}}{2a}) ; (x_{2}=frac{-b-sqrt{triangle}}{2a}) rồi kết thúc
      • Bước 4: Nếu Δ = 0 thì phương trình có nghiệm kép (x_{1,2}=frac{-b}{2b}) rồi thuật toán kết thúc. Nếu không chuyển sang bước tiếp theo
      • Bước 5: Kết luận phương trình vô nghiệm rồi kết thúc
  • Cách sử dụng sơ đồ khối
    • hình thoi : thể hiện thao tác so sánh;
    • Hình hộp chữ nhật : hiển thị phép tính;
    • hình bầu dục : thể hiện thao tác nhập xuất dữ liệu;
    • mũi tên : Chỉ định trình tự của các hoạt động.

Vấn đề 1: Kiểm tra tính nguyên tố

1. Xác định vấn đề

  • Dữ liệu vào: N là số nguyên dương
  • Đầu ra:
    • N là số nguyên tố hoặc
    • N không phải là số nguyên tố
  • Định nghĩa: “Số nguyên dương N là số nguyên tố nếu nó có đúng hai ước là 1 và N”
  • Tự nhiên:
    • Nếu N = 1 thì N không nguyên tố
    • Nếu 1 < N < 4 thì N là số nguyên tố

2. Ý tưởng

  • N<4: Coi như vấn đề đã được giải quyết
  • N>=4: Tìm ước đầu tiên i > 1 của N
    • Nếu i < N thì N không 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ố

3. 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ông báo “N không phải là số nguyên tố”, kết thúc;
  • Bước 3: Nếu N < 4, thông báo "N là số nguyên tố", kết thúc;
  • Bước 4: (i leftarrow2
  • Bước 5: Nếu i là ước của N, chuyển sang bước 7
  • Bước 6: (i mũi tên trái i +1) sau đó 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ông báo “N không phải số nguyên tố”, kết thúc;

b) Sơ đồ khối

Xem thêm: Giải Toán 10 trang 68 Tập 1 Kết nối tri thức – VietJack.com

Hình 1. Sơ đồ khối thuật toán kiểm tra tính nguyên tố của số nguyên dương N

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

Vấn đề 2: Sắp xếp theo hoán đổi

1. Xác định vấn đề

  • Dữ liệu vào: Dãy A gồm N số nguyên a1, a2,…,an
    • Ví dụ: Dãy A gồm các số nguyên: 2 4 8 7 1 5
  • Dữ liệu ra: Dãy A được sắp xếp thành dãy không giảm
    • Dãy A sau khi sắp xếp: 1 2 4 5 7 8

2. Ý tưởng

  • Đối với mỗi cặp số hạng liền kề trong dãy, nếu số hạng trước > số hạng sau, ta đổi chỗ chúng. (Các số lớn sẽ được đẩy về vị trí xác định ở cuối dãy)
  • Điều này được lặp đi lặp lại nhiều lần, thực hiện nhiều so sánh mỗi lượt cho đến khi không xảy ra hoán đổi nữa

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

  • Bước 1. Nhập N, các số hạng a1, a2,…,an;
  • Bước 2. Đầu tiên gọi M là số hạng cần so sánh nên M sẽ chứa giá trị của N: (M leftarrow N);
  • Bước 3. Nếu số hạng cần so sánh < 2 thì dãy được sắp xếp. Kết thúc;
  • Bước 4. M lần lượt chứa giá trị mới của số phép so sánh cần thực hiện: (M mũi tên trái M-1). Gọi i là số thứ tự của mỗi lần so sánh, đầu i 0;
  • Bước 5. Để thực hiện phép so sánh mới, i tăng thêm 1 (so sánh thứ i)
  • Bước 6. Nếu so lần thứ i > số lần so M: hoàn thành M số lần so của lượt này. Nói lại Bước 3bắt đầu lượt tiếp theo (với số hạng mới cần so sánh là M đã giảm đi 1 tại Bước 4);
  • Bước 7. So sánh 2 phần tử ở lần thứ i là ai và ai+1. Nếu ai > ai+1 thì đổi chỗ 2 phần tử này;
  • Bước 8. Quay lại bước 5

a) So sánh và hình thành các bước liệt kê

  • Bước 1: Nhập N, các số hạng a1, a2,…,an;
  • Bước 2: (M mũi tên trái N
  • Bước 3: Nếu M < 2, xuất ra dãy A đã sắp xếp, rồi kết thúc;
  • Bước 4: (M mũi tên trái M-1 ; i mũi tên trái 0 😉
  • Bước 5: ( i mũi tên trái i – 1
  • Bước 6: Nếu i > M thì quay lại Bước 3;
  • Bước 7: Nếu ai > ai+1, đổi chỗ ai và ai+1 cho nhau;
  • Bước 8: Quay lại bước 5;

b) Sơ đồ khối

6(59)

Xem thêm: Soạn Truyện Kiều – đoạn trao duyên | Soạn Văn Ngắn Nhất 10

Hình 2. Sơ đồ khối của thuật toán sắp xếp bằng cách đổi chỗ

Vấn đề 3: Tìm kiếm tuần tự

1. Xác định vấn đề

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

2. Ý tưởng

Việc tìm kiếm tuần tự được thực hiện một cách tự nhiên: Lần lượt đi từ thuật ngữ đầu tiên, ta so sánh giá trị của thuật ngữ đang xét với khóa cho đến khi gặp thuật ngữ bằng khóa hoặc dãy đã xét mà không tìm được. xem giá trị của khóa trên mảng.

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

a) Cách liệt kê

  • Bước 1: Nhập N, các số hạng a1, a2,…, aN và khóa k;
  • Bước 2: (i tráimũi tên 1;)
  • Bước 3: Nếu ai = k thì công bố chỉ số i rồi kết thúc;
  • Bước 4: (i mũi tên trái i + 1;)
  • Bước 5: Nếu i > N thì nhận thấy dãy A không có số hạng nào bằng k rồi chấm hết;
  • Bước 6: Quay lại bước 3;

b) Sơ đồ khối

10(30)

Xem thêm: Giải bài 1, 2, 3, 4, 5, 6, 7 trang 106 SGK Hóa học 10

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

Vấn đề 4: Tìm kiếm nhị phân

1. Xác định vấn đề

  • Dữ liệu vào: Dãy A là một dãy tăng gồm N số nguyên khác nhau a1, a2,…,an và một số nguyên k.
    • Ví dụ: Dãy A gồm các số nguyên: 2 4 5 6 9 21 22 30 31 33. Và k = 21 (k = 25)
  • Dữ liệu ra: Vị trí i mà ai = k hoặc thông báo k không tìm thấy trong dãy. Vị trí của 21 trong dãy số là 6 (không tìm thấy 25).

2. Ý tưởng

  • Sử dụng tính chất của dãy A sắp xếp tăng dần, ta tìm được cách thu hẹp nhanh vùng tìm bằng cách so sánh k với từ ở giữa dãy tìm (between) thì chỉ xảy ra một trong ba trường hợp sau:
    • Nếu amid= k thì tìm chỉ số, kết thúc;
    • Nếu amid > k, tìm kiếm sẽ thu hẹp xuống chỉ phần đầu (mũi tên phải) giữa – 1;
    • Nếu giữa < k, tìm kiếm sẽ thu hẹp xuống chỉ giữa + 1 (mũi tên phải) đến cuối (phạm vi).
  • Quá trình trên được lặp lại 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.

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

a) Cách liệt kê

  • Bước 1: Nhập N, các số hạng a1, a2,…, aN và khóa k;
  • Bước 2: Đầu (mũi tên trái) 1; Kết thúc (mũi tên trái) N;
  • Bước 3: Giữa [(Đầu+Cuối)/2];
  • Bước 4: Nếu aMiddle = k thì công bố chỉ số Mid rồi kết thúc;
  • Bước 5: Nếu aMiddle > k thì đặt End = Middle – 1 rồi chuyển sang bước 7;
  • Bước 6: Đầu (mũi tên trái) Giữa + 1;
  • Bước 7: Nếu Start > End thì báo k không tìm thấy trên dãy số rồi kết thúc;
  • Bước 8: Quay lại Bước 3.

b) Sơ đồ khối

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



KHAITRI.EDU.VN

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *