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

A. Khái niệm

• Vấ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 vấn đề:
  • Đầu vào: Thông tin đã biết , nhập thông tin máy tính
  • Đầu ra: Tra cứu thông tin, thông tin truy xuất từ ​​máy tính

  b. Ví dụ

  • Tìm công thức của 2 số nguyên dương
  • Tìm số lớn nhất của 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)
  • …

  A. Khái niệm

  Thuật toán giải quyết vấn đề:

  • Chuỗi hoạt động hữu hạn (tính ổn định)
  • Các hoạt động được thực hiện trong một trình tự cụ thể (xác định)

  Sau khi thực hiện một loạt các thao tác, chúng tôi nhận được kết quả của sự cố (tính đúng đắn)

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

Các thuật toán có thể được diễn đạt theo hai cách:

• Sử dụng phương pháp liệt kê: xác định thứ tự các phép toán phải thực hiện
  • Ví dụ: Giải phương trình tìm bài toán bậc hai 2 : ax2 + bx + c = 0 (a ≠ 0)?
  • Bài toán định nghĩa
    • Đầu vào: các số thực a, b, c
    • Đầu ra: số thực x thỏa mãn ax2 + bx + c = 0 (a ≠ 0)

    li>

    • 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:
    • (x_ {1} = frac {-b + sqrt { tam giác}} {2a} ); (x_ {2} = frac {- b- sqrt { tam giác}} {2a} ) và hoàn thành
    • Bước 4: Nếu Δ = 0, phương trình có nghiệm kép (x_ {1,2} = frac {- b} {2b} ) sau đó kết thúc thuật toán. Nếu không, hãy chuyển sang bước tiếp theo
    • Bước 5: kết luận phương trình vô nghiệm và kết thúc
    • Hình thoi : So sánh các phép toán;
    • Hình chữ nhật : Thực hiện các phép tính;
    • Hình bầu dục : Hiển thị các thao tác nhập và xuất;
    • Mũi tên : Chỉ định thực hiện các thao tác tuần tự.

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

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

    • Đầu vào: n là một 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ố

      li>

      ul>

      • Nếu n = 1 thì n không nguyên tố
      • Nếu 1 & lt; n <4 thì n nguyên tố

      2. Ý tưởng

      • n & lt; 4: nghĩ rằng vấn đề đã được giải quyết
      • n & gt; = 4: tìm ước số đầu tiên i> 1 của n
        • nếu tôi & lt; n thì n là không phải số 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ố

        Xem Thêm : Giáo án bài Đặc điểm loại hình của tiếng Việt – VietJack.com

        3. Thuật toán xây dựng

        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ì thông báo "n là số nguyên tố", kết thúc;
        • bước 4: (i leftarrow2; )
        • bước 5: nếu tôi là n Số chia , chuyển đến bước 7
        • bước 6: (i leftarrow 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

        

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

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

        Xem Thêm : Nội dung chính bài Sọ Dừa hay nhất – Kết nối tri thức – VietJack.com

        Câu hỏi 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
          • mảng đã sắp xếp a: 1 2 4 5 7 8

          2. Ý tưởng

          • Với mỗi cặp vật phẩm liền kề trong dãy, nếu số đứng trước>; các số sau chúng ta hoán đổi cho nhau. (các số lớn sẽ được đẩy đến vị trí đã chỉ định ở cuối dãy)
          • Việc này được lặp lại nhiều lần, mỗi lần có nhiều phép so sánh cho đến khi không còn hoán đổi nữa

          Xem Thêm : Giáo án bài Đặc điểm loại hình của tiếng Việt – VietJack.com

          3. Thuật toán xây dựng

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

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

          • Bước 1: Nhập n, các mục a1, a2,…, an;
          • Bước 2: (m leftarrow n; )
          • Bước 2 3: Nếu m <2 thì xuất chuỗi đã sắp xếp a, kết thúc;
          • 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ì 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 ;

          ul>

          b) Sơ đồ khối

          

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

          Câu hỏi 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 phân biệt a1, a2, …, an và một số nguyên k (phím)
            • 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)

            2. Ý 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 tìm thấy cụm từ hoặc chuỗi bằng với khóa đã được xem xét. Không tìm thấy giá trị nào cho phạm vi của khóa.

            Xem Thêm : Giáo án bài Đặc điểm loại hình của tiếng Việt – VietJack.com

            3. Thuật toán xây dựng

            a) Cách liệt kê

            • Bước 1: Nhập n, các mục a1, a2, …, an và phím k;
            • Bước 2: (i leftarrow 1; )
            • bước 3: nếu ai = k, khai báo chỉ mục i, sau đó kết thúc;
            • bước 4: (i leftarrow i + 1; )
            • bước 5: Nếu tôi & gt; sau đó n khai báo rằng dãy a không có mục nào bằng k, sau đó kết thúc;
            • bước 6: quay lại bước 3;

            b) Sơ đồ khối

            

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

            Câu hỏi 4: Tìm kiếm nhị phân

            1. 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à 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)

              2. Ý tưởng

              • Sử dụng tính chất của trình tự sắp xếp tăng dần a, bằng cách so sánh k và các mục ở giữa phạm vi tìm kiếm, hãy tìm cách nhanh chóng thu hẹp vùng tìm kiếm, khi đó chỉ một phần ba các trường hợp:
                • nếu abetween = k thì tìm chỉ mục, kết thúc;
                • nếu abetween> k thì thu hẹp tìm kiếm về đầu (phạm vi) ( rightarrow ) abetween – 1;
                • if abetween & lt; k thu hẹp tìm kiếm vào giữa + 1 ( rightarrow ) aend (range).

                Xem Thêm : Giáo án bài Đặc điểm loại hình của tiếng Việt – VietJack.com

                3. Thuật toán xây dựng

                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: head ( leftarrow ) 1; end ( leftarrow ) n;
                • bước 3: giữa [(bắt đầu + kết thúc) / 2];
                • bước 4: nếu amiddle = k thì khai báo chỉ mục giữa, rồi kết thúc;
                • bước 5: if abetween>; k then put end = middle – 1 rồi chuyển đến bước 7 ;
                • bước 6: start ( leftarrow ) giữa + 1;
                • Bước 7: Nếu head> Cuối cùng, không tìm thấy thông báo k nào trên chuỗi thì hãy kết thúc;
                • Bước 8: Quay lại bước Bước 3 .

                b) Sơ đồ khối

                

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