Bạn đang xem: Tin học 10 Bài 4: Bài toán và thuật toán Tại DongnaiArt

a. khái niệm

• vấn đề là điều con người muốn máy tính thực hiện
• các yếu tố của vấn đề:
  • input: thông tin đã biết , thông tin được nhập vào máy tính
  • đầu ra: thông tin cần tìm, thông tin được truy xuất từ ​​máy tính

  b. ví dụ

  • tìm bằng cách sử dụng 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)
  • …

  a. khái niệm

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

  • một chuỗi hữu hạn các hoạt động (cố định)
  • các hoạt động được thực hiện trong một chuỗi cụ thể (xác định)
  • sau khi thực hiện chuỗi hoạt động đó, chúng tôi nhận được kết quả của sự cố (sửa chữa)

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

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

  • cách sử dụng phương pháp liệt kê: chỉ định trình tự các thao tác thực hiện
    • ví dụ: cho lời giải của bài toán tìm kiếm phương trình 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: các số thực x thỏa mãn ax2 + bx + c = 0 (a ≠ 0)
      • bước 1: nhập a, b, c (a ≠ 0)
      • bước 2: tính Δ = b2 – 4ac
      • bước 3: nếu Δ & gt; 0 thì phương trình có 2 nghiệm như
      • (x_ {1} = frac {-b + sqrt { tam giác}} {2a} ); (x_ {2} = frac {-b- sqrt { tam giác}} {2a} ) và 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} ) và 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 rằng phương trình vô nghiệm và kết thúc
      • hình thoi : thực hiện các thao tác so sánh;
      • 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 hoạt động đầu vào và đầu ra;
      • mũi tên : chỉ định trình tự thực hiện của các hoạt động.

      vấn đề 1: kiểm tra tính nguyên thủy

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

      • đầ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ố

        li>

        • nếu n = 1 thì n không phải là số nguyên tố
        • nếu 1 & lt; n & lt; 4 nên n là số nguyên tố

        2. ý tưởng

        • n & lt; 4: coi bài toán đã giải xong
        • n & gt; = 4: tìm ước số đầu tiên i & gt; 1 trong số n
          • nếu tô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 nguyên tố

          Xem Thêm : Bản tự kiểm điểm cá nhân cuối năm mới nhất (Cập nhật 2022)

          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ì thông báo “n không phải là số nguyên tố”, kết thúc;
          • bước 3 : if n & lt; 4 then message “n is prime”, end;
          • bước 4: (i leftarrow2; )
          • bước 5: nếu tôi là ước của n thì 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: if 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ố”, end;

          b) sơ đồ khối

          

          hình 1. sơ đồ khối của thuật toán để kiểm tra tính nguyên dương 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 : Hội chứng khuỷu tay Tennis (tennis elbow)

          vấn đề 2: đặt hàng qua sàn giao dịch

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

          • input: dãy a gồm n số nguyên a1, a2,…, ví dụ
            • : dãy a gồm các số nguyên: 2 4 8 7 1 5

            >

            • mảng a sau 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ố đứng trước & gt; các số sau chúng ta trao đổi với nhau. (các số lớn sẽ được chuyển đế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 thực hiện nhiều phép so sánh cho đến khi không còn hoán đổi nữa

            Xem Thêm : Bản tự kiểm điểm cá nhân cuối năm mới nhất (Cập nhật 2022)

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

            • bước 1. nhập n, số hạng a1, a2,…, an;
            • bước 2. đầu tiên, đặt m là số hạng cần so sánh, do đó m sẽ chứa giá trị của n: (m leftarrow n );
            • bước 3. nếu số thuật ngữ cần so sánh & lt; 2, sau đó trình tự được sắp xếp. end;
            • bước 4. m chứa giá trị mới của số phép so sánh cần thực hiện lần lượt: (m leftarrow m-1 ). đặt 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, tăng thêm 1 (phép so sánh thứ)
            • bước 6. nếu bản thân & gt ; number of so sánh m: hoàn thành m số so sánh cho lượt này. lặp lại bước 3 , bắt đầu với bước tiếp theo (với số thuật ngữ mới để so sánh là m đã giảm đi 1 trong 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 đó & gt; ai + 1 hoán đổi 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 được liệt kê

            • bước 1: nhập n, số hạng a1, a2,…, an;
            • bước 2: (m leftarrow n; )
            • bước 3: nếu m & lt; 2 sau đó xuất ra chuỗi có thứ tự a và 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 tôi & gt; m rồi 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

            

            hình 2. sơ đồ khối của thuật toán phân loại trao đổi

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

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

            • input: dãy a gồm n số nguyên phân biệt 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)

              2. ý tưởng

              tìm kiếm tuần tự được thực hiện một cách tự nhiên: 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 chúng tôi tìm thấy một cụm từ bằng khóa hoặc dãy đã được xem xét mà không tìm thấy giá trị của khóa trong phạm vi.

              Xem Thêm : Bản tự kiểm điểm cá nhân cuối năm mới nhất (Cập nhật 2022)

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

              a) cách liệt kê

              • bước 1: nhập n, số hạng a1, a2, …, an và giá trị khóa k;
              • bước 2: (i leftarrow 1; )
              • bước 3: nếu ai = k, sau đó thông 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; n thì lưu ý rằng dãy a không có số hạng nào bằng k và 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ự

              vấn đề 4: tìm kiếm nhị phân

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

              • input: Dãy a là một 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 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

                • bằng cách sử dụng thuộc tính mảng được sắp xếp a, chúng tôi tìm cách nhanh chóng thu hẹp vùng tìm kiếm bằng cách so sánh k với thuật ngữ ở giữa phạm vi tìm kiếm (giữa), khi đó chỉ một trong ba trường hợp:
                  • if a between = k thì tìm chỉ mục, kết thúc;
                  • if a between & gt; k thì tìm kiếm chỉ được giảm xuống đầu (phạm vi) ( rightarrow ) giữa – 1;
                  • nếu a giữa & lt; k tìm kiếm bị thu hẹp chỉ còn từ giữa + 1 ( rightarrow ) aend (range).

                  Xem Thêm : Bản tự kiểm điểm cá nhân cuối năm mới nhất (Cập nhật 2022)

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

                  a) cách liệt kê

                  • bước 1: nhập n, số hạng a1, a2, …, an và giá trị khóa k;
                  • bước 2: head ( leftarrow ) 1; the end ( leftarrow ) n;
                  • bước 3: middle [(start + end) / 2];
                  • bước 4: if middle = k thì thông báo chỉ số giữa , rồi kết thúc;
                  • bước 5: nếu bạn nhập & gt; k rồi đặt end = middle – 1 rồi chuyển đến bước 7 ;
                  • bước 6: bắt đầu ( leftarrow ) giữa + 1;
                  • bước 7: nếu đầu & gt; cuối cùng, thông báo k không được tìm thấy trong chuỗi và sau đó kết thúc;
                  • bước 8: quay lại 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ự