Thực đơn
trang chủSự cố

Xây dựng bài học khoa học máy tính chủ đề “Các thuật toán phụ trợ. Phương pháp chi tiết tuần tự và phương pháp lắp ráp”. Phân nhánh và sàng lọc tuần tự của thuật toán

Phương pháp chi tiết tuần tự.

Khoa học máy tính lớp 11

Cơ sở giáo dục thành phố "Trường học-lyceum số 1"

Alushta

Giáo viên: Litvinovich V.P.


Phương pháp chi tiết tuần tự là một trong những phương pháp chính của lập trình có cấu trúc.

Bản chất của phương pháp này là phát triển các thuật toán phức tạp bằng cách xây dựng hệ thống phân cấp

nhiệm vụ phụ


Bản chất của phương pháp:

  • Đã phân tích vấn đề ban đầu.
  • Nhiệm vụ phụ được đánh dấu.
  • Một hệ thống phân cấp các nhiệm vụ con đang được xây dựng
  • Một thuật toán (chương trình) cho tác vụ chính được biên dịch
  • Một thuật toán phụ trợ (chương trình con) được biên soạn với mức độ tăng dần theo trình tự.


ví dụ 1 Tính diện tích của N-giác lồi cho bởi tọa độ các đỉnh của nó.

Tìm diện tích của đa giác lồi:

Diện tích của một đa giác

được định nghĩa là số tiền

khu vực N-2 Hình tam giác.

S- tam giác được xác định:

theo công thức Heron

S =√(p(p-a)(p-b)(p-c)


Bước đầu tiên của chi tiết Các cạnh của một tam giác được xác định theo định lý Pythagore: Dữ liệu ban đầu, tọa độ các đỉnh của tam giác, có thể được xác định bằng cách sử dụng một mảng:

Tổ chức dữ liệu


Bước chi tiết thứ hai: Hãy lập trình thủ tục Treugolnik. Trong phần chương trình con của thủ tục này chúng ta sẽ chỉ viết giao diện của chương trình con Dòng, tạo một hàm.


Bước thứ ba của chi tiết Hãy lập trình hàm Đường kẻ. Tọa độ các đầu của đoạn được xác định bởi các tham số sau: x Một, Y Một - điểm đầu tiên, x b, bạn b – giây.

Chúng tôi thu thập tất cả các bước đã thực hiện và tạo một chương trình:

………………………………………………………………………………………… ..



Ứng dụng phương pháp chi tiết tuần tự

  • Một số chuyên gia đang làm việc trên một dự án phần mềm lớn.
  • Trưởng nhóm thiết kế cấu trúc đa cấp của thuật toán và soạn chương trình chính, đồng thời phân công viết chương trình con cho các lập trình viên khác.
  • Người lập trình cần phải thống nhất về giao diện của các chương trình con: tên, tham số.
  • Cấu trúc bên trong của chương trình con là công việc của người lập trình
  • Các dự án chương trình con lớn được kết hợp thành MODULES.

Bài tập về nhà. § 2.2.11 đọc. Nhớ …


Công việc thực tế № 6. Kiểm tra hoạt động của chương trình N ugolnik

Đặt N = 4

Tính diện tích hình vuông có độ dài các cạnh bằng nhau 2 và tọa độ đỉnh:

Nhận kết quả.

Bản chất của phương pháp đã được mô tả ở trên. Đầu tiên, vấn đề ban đầu được phân tích. Nó xác định các nhiệm vụ phụ. Một hệ thống phân cấp các nhiệm vụ phụ như vậy được xây dựng (Hình 48).
Sau đó, các thuật toán (hoặc chương trình) được biên dịch, bắt đầu bằng thuật toán chính (chương trình chính), sau đó là các thuật toán phụ (chương trình con) với mức độ đi sâu liên tiếp cho đến khi thu được các thuật toán gồm lệnh đơn giản.Hãy quay lại nhiệm vụ “Thông dịch viên”, đã được xem xét trong phần. 3.16. Chúng ta hãy nhớ lại điều kiện: cho chuỗi ký tự gốc có lượt xem tiếp theo:MỘT
b=A và b được thay thế bằng chữ số thập phân; biểu tượng
một trong các dấu hiệu hoạt động được chỉ định: +, -, *. Chúng ta cần máy đánh giá biểu thức này và sau dấu =, hiển thị kết quả. Phép chia không được xem xét chỉ để xử lý các số nguyên. Chúng ta hãy xây dựng các yêu cầu đối với chương trình Phiên dịch để làm cho nó trở nên phổ biến hơn tùy chọn được thảo luận trong Phần. 3,16:1. Toán hạng a và b có thể là số nguyên dương có nhiều giá trị trong MaxInt.2. Có thể có khoảng cách giữa các phần tử dòng, cũng như ở đầu và cuối.3. Chương trình thực hiện kiểm soát cú pháp của văn bản. Hãy giới hạn bản thân ở tùy chọn điều khiển đơn giản nhất: dòng chỉ được bao gồm các số, dấu hiệu phép toán, dấu = và dấu cách.4. Kiểm soát ngữ nghĩa được thực hiện: dòng phải được xây dựng theo sơ đồ a
b =. Lỗi nếu thiếu một số phần tử hoặc thứ tự của chúng không đúng thứ tự.5. Phạm vi của các giá trị toán hạng và kết quả được kiểm soát (chúng không được vượt quá MaxInt) Từ danh sách các yêu cầu, có thể thấy rõ rằng chương trình sẽ không dễ dàng. Chúng tôi sẽ soạn nó bằng phương pháp chi tiết tuần tự. Hãy bắt đầu bằng cách giới thiệu ngay trong nhìn chung Thuật toán như một chuỗi tuyến tính các giai đoạn để giải một bài toán: 1. Nhập một dòng.2. Kiểm soát cú pháp (có ký tự nào không hợp lệ không?).3. Kiểm soát ngữ nghĩa (biểu thức có được xây dựng chính xác không?).4. Lựa chọn toán hạng. Kiểm tra toán hạng để tìm phạm vi giá trị hợp lệ. Chuyển đổi thành số nguyên.5. Thực hiện một hoạt động. Kiểm tra kết quả trong phạm vi chấp nhận được.6. Đầu ra của kết quả Chúng ta sẽ coi các giai đoạn 2, 3, 4, 5 là các nhiệm vụ con của cấp độ đầu tiên, đặt tên chúng (và các chương trình con sau này) là Sintax, Semantika, Operand, Calc cho phù hợp

“Thực thi thuật toán trên máy tính” - Người thực thi hình thức Thuật toán và chương trình Đặc điểm thực thi chương trình. Các tính năng của việc thực thi một chương trình trong NML trên máy tính là gì? Các câu hỏi cơ bản: Trượt tuyết. Đặc điểm của việc thực thi chương trình máy tính viết bằng LPW? phát sóng từ YAPVU đến YAMK. Các giai đoạn thực hiện chương trình. Thiết bị đầu ra. Máy tính.

“Thuật toán trong Khoa học Máy tính” - Action N. Chúc các bạn học KHOA HỌC MÁY TÍNH thành công. Thuật toán phân nhánh. Đầu ra của kết quả. Nhập dữ liệu ban đầu Hiểu rõ chủ đề và làm tốt bài học. Thuật toán nào được gọi là tuyến tính? Chỉ định sự bắt đầu và kết thúc của thuật toán. Các loại thuật toán. Các loại thuật toán. Rất nhiều công việc cần phải được thực hiện về chủ đề này.

“Thuộc tính và loại thuật toán” - Một thiết kế thuật toán tuần hoàn trong đó điều kiện được đặt ở đầu chu kỳ. Sự bắt đầu, sự kết thúc của thuật toán. Các loại thuật toán. Phương pháp đồ họa mô tả thuật toán (sơ đồ khối). Hành động đang được thực hiện. Chuỗi hành động. Thuật toán tuyến tính. Dạng thuật toán phân nhánh chưa hoàn chỉnh.

“Thuật toán hành động” - Thuật toán nên được mô tả như thế nào? Để hoàn thành một nhiệm vụ, trước tiên bạn phải suy nghĩ thông qua một chuỗi hành động. Khi dịch sang tiếng Latin, tên tác giả được viết như sau: Algorithmi [thuật toán]. Đốt gas. Các thuật toán trong cuộc sống của chúng ta. Bất kỳ thuật toán nào cũng có thể được mô tả bằng đồ họa hoặc mô tả bằng lời. Từ "thuật toán" đến từ đâu?

“Tin học “Khái niệm về một thuật toán”” - Trình tự các bước cuối cùng. Số lượng lớn nhiệm vụ có độ phức tạp khác nhau. Thuật toán. Tài liệu dành cho người tò mò. Máy tính có thể tự giải quyết vấn đề được không? Làm thế nào một máy tính có thể được sử dụng? Thuật toán là gì? Các giai đoạn của công việc. Chỉ con người mới có thể phát triển các thuật toán. Mẹ kế. Nhiệm vụ thực tế.

“Thuật toán và cách thực hiện chính thức” - Ghi thuật toán dưới dạng sơ đồ khối. Hãy lấy văn bản làm đối tượng. Phát triển các ngôn ngữ lập trình. Mã hóa. Các thuật toán bao gồm các lệnh riêng lẻ. Thuật toán phải rõ ràng. Cơ bản về thuật toán hóa. Công bố hoặc chuyển giao kết quả công việc cho khách hàng. Ghi lại thuật toán. Thiết kế từ trên xuống.

Tổng cộng có 31 bài thuyết trình

Trong quá trình chi tiết tiếp theo, thuật toán chính được xây dựng trước tiên và sau đó các lệnh gọi đến thuật toán phụ trợ ở cấp độ đầu tiên được thêm vào nó. Sau đó, các thuật toán phụ trợ cấp độ đầu tiên được hình thành, có thể chứa các lệnh gọi đến các thuật toán phụ trợ cấp độ thứ hai, v.v. Thuật toán phụ trợ mức độ thấp hơn chỉ bao gồm các lệnh đơn giản. Phương pháp chi tiết tuần tự sẽ được sử dụng trong mọi thiết kế vật thể phức tạp. Đây là hệ quả logic tự nhiên trong tư duy của một nhà thiết kế: đi sâu vào từng chi tiết. Kỹ thuật chi tiết cuối cùng cho phép bạn tổ chức công việc của một nhóm chương trình trong một dự án phức tạp. Đầu tiên, vấn đề ban đầu được phân tích. Nó xác định các nhiệm vụ phụ. Một hệ thống phân cấp của các nhiệm vụ con như vậy được xây dựng.

Sau đó các thuật toán (hoặc chương trình) được xây dựng, bắt đầu từ thuật toán chính (chương trình chính), sau đó là các thuật toán phụ (chương trình con) với độ sâu cuối cùng là Level cho đến khi chúng ta có được các thuật toán gồm các lệnh đơn giản. Nhiệm vụ. Tình trạng: có bản gốc chuỗi ký tự, có dạng sau: a Å b = Thay cho a và b là các chữ số thập phân; Ký hiệu Å biểu thị một trong các dấu hiệu hoạt động: *, -, *. Máy cần phải tính biểu thức này và sau dấu = sẽ hiển thị kết quả. Toán hạng a và b có thể là số nguyên dương nhiều giá trị trong MaxInt. Có khoảng cách giữa các phần tử của dòng, cũng như ở đầu và cuối. Chương trình thực hiện kiểm soát cú pháp của văn bản. Hãy giới hạn bản thân ở tùy chọn điều khiển đơn giản nhất: dòng chỉ được bao gồm các số, dấu hiệu phép toán, dấu = và dấu cách. Kiểm soát ngữ nghĩa được thực hiện: đường thẳng phải được xây dựng theo sơ đồ a Å b = . Lỗi nếu thiếu một phần tử nào đó hoặc thứ tự của chúng không đúng thứ tự. Phạm vi giá trị của toán hạng và kết quả được kiểm soát (chúng không được vượt quá Maxint). Từ danh sách các yêu cầu, có thể thấy rõ rằng chương trình sẽ không hề dễ dàng. Chúng tôi sẽ soạn nó bằng phương pháp chi tiết cuối cùng. Hãy bắt đầu bằng cách trình bày thuật toán ở dạng tổng quát nhất dưới dạng một chuỗi tuyến tính các giai đoạn trong quá trình giải một bài toán: Nhập một chuỗi. Kiểm soát cú pháp (có ký tự nào không hợp lệ không?). Kiểm soát ngữ nghĩa (biểu thức có được xây dựng chính xác không?). Lựa chọn toán hạng. Kiểm tra các toán hạng để tìm phạm vi giá trị hợp lệ. Chuyển đổi thành số nguyên. Số lượng hoạt động. Kiểm tra kết quả trong phạm vi chấp nhận được. Kết luận về kết quả. Chúng ta sẽ coi các giai đoạn 2, 3, 4, 5 là các nhiệm vụ con của cấp độ đầu tiên, gọi chúng (và các chương trình con trong tương lai) lần lượt là Sintax, Semantika, Operand, Calc. Đổi lại, việc triển khai chúng sẽ yêu cầu giải quyết các nhiệm vụ phụ sau: bỏ qua khoảng trắng thừa (propusk), chuyển đổi một chữ số ký tự thành số nguyên (cifra). Ngoài ra, khi cấp phát toán hạng, bạn sẽ cần nhận biết toán hạng vượt quá giá trị tối đa giá trị cho phép(Lỗi). Bước đầu tiên của chi tiết.Đầu tiên, chúng tôi phác thảo tất cả các chương trình con cần thiết, chỉ cho biết tiêu đề (thông số kỹ thuật) của chúng. Thay cho phần nội dung của chương trình con, chúng ta sẽ viết các chú thích giải thích. Hãy viết phần chính của chương trình. Và sau đó chúng ta sẽ quay trở lại chương trình chi tiết thủ tục và f. Bước thứ hai của chi tiết.Điều kiện rất kém. Cuối cùng, sau khi kết hợp nội dung của chương trình con với chương trình chính, chúng ta thu được phiên bản hoạt động của chương trình Bộ nội suy.

Các cấu trúc thuật toán cơ bản: theo sau, phân nhánh, vòng lặp; hình ảnh trên sơ đồ khối. Chia một nhiệm vụ thành các nhiệm vụ con. Các thuật toán phụ trợ.

Các loại thuật toán chính (cấu trúc thuật toán):

1. Thuật toán tuyến tính (còn gọi là thuật toán sau);

2. Thuật toán tuần hoàn;

3. Thuật toán phân nhánh;

4. Thuật toán phụ trợ.

Thuật toán tuyến tính

Thuật toán tuyến tính – mô tả các hành động được thực hiện một lần theo một thứ tự nhất định. Người thực hiện thực hiện các hành động một cách tuần tự, lần lượt theo thứ tự chúng xảy ra.

Sơ đồ khối thuật toán tuyến tính:

Thuật toán quay vòng

Chất lượng tốt nhất máy tính tự biểu hiện không phải khi chúng tính toán ý nghĩa của các biểu thức phức tạp mà khi chúng lặp lại nhiều lần các thao tác tương đối đơn giản với những thay đổi nhỏ. Ngay cả những phép tính rất đơn giản cũng có thể khiến một người bối rối nếu chúng cần được lặp lại hàng nghìn lần và một người hoàn toàn không có khả năng lặp lại các thao tác hàng triệu lần.

Các lập trình viên thường xuyên phải đối mặt với nhu cầu tính toán lặp đi lặp lại. Ví dụ: nếu bạn cần đếm số lần chữ cái “o” xuất hiện trong văn bản, bạn cần phải duyệt qua tất cả các chữ cái. Mặc dù chương trình này đơn giản nhưng một người rất khó thực hiện nó, nhưng đối với máy tính thì đó là một nhiệm vụ chỉ mất vài giây.

Thuật toán quay vòng– mô tả các hành động phải được lặp lại một số lần xác định hoặc cho đến khi đáp ứng một điều kiện xác định.

Danh sách các hành động lặp đi lặp lại được gọi là thân vòng lặp.

Có hai loại thuật toán tuần hoàn:

  • Vòng lặp với bộ đếm, trong đó một số hành động được thực hiện một số lần nhất định;
  • Vòng lặp có điều kiện trong đó phần thân của vòng lặp được thực thi tùy thuộc vào một số điều kiện. Có các chu kỳ với điều kiện trước và điều kiện sau.

Vòng lặp có bộ đếm được sử dụng khi biết trước số lần lặp lại của thân vòng lặp phải được thực hiện. Ví dụ, trong giờ học thể dục, bạn phải chạy nhiều vòng quanh sân vận động.



TRONG trường hợp chung Sơ đồ mạch của thuật toán tuần hoàn với bộ đếm sẽ như sau:

Vì truy cập từ đầu giá trị để kết thúc giá trịhành hình hoạt động.

Điều thường xảy ra là cần phải lặp lại phần thân của một vòng lặp, nhưng không biết trước việc này nên được thực hiện bao nhiêu lần. Trong những trường hợp như vậy, số lần lặp lại phụ thuộc vào một số điều kiện. Những vòng lặp như vậy được gọi là vòng lặp có điều kiện. Vòng lặp trong đó điều kiện được kiểm tra đầu tiên và sau đó có thể phần thân của vòng lặp được thực thi, được gọi là vòng lặp có điều kiện tiên quyết. Nếu điều kiện được kiểm tra sau lần thực hiện đầu tiên của thân vòng lặp thì vòng lặp đó được gọi là vòng lặp có hậu điều kiện.

Ví dụ, vào tối thứ bảy bạn xem TV. Thỉnh thoảng bạn nhìn đồng hồ và nếu chưa đến nửa đêm thì bạn tiếp tục xem TV; nếu không, bạn ngừng xem các chương trình TV.

Nói chung, sơ đồ của thuật toán tuần hoàn với một điều kiện sẽ như sau:

Tạm biệt tình trạnglặp lại hoạt động.

Khi biên dịch thuật toán tuần hoànĐiều quan trọng là phải suy nghĩ về chu kỳ là hữu hạn. Tình huống trong đó một vòng lặp không bao giờ kết thúc được gọi là vòng lặp.

Thuật toán phân nhánh

Trong nhiều trường hợp, cần phải thực hiện một chuỗi hành động trong những điều kiện nhất định và một chuỗi hành động khác trong những điều kiện khác.

Nếu trời mưa thì phải mở ô.

Nếu đồng hồ báo thức reo thì bạn cần phải thức dậy.

Phân nhánh thuật toán- một thuật toán trong đó, tùy thuộc vào điều kiện, một hoặc một chuỗi hành động khác được thực hiện.

Những câu này bắt đầu bằng việc kiểm tra một số điều kiện: trời bắt đầu mưa, đồng hồ báo thức reo, tôi gặp Sasha... Sau đó, tùy theo tình huống, chúng ta loại bỏ một số hành động hoặc không thực hiện nó (hoặc thực hiện một số hành động khác).

Máy tính cũng vậy, tùy theo điều kiện nào đó, có thể thực hiện hoặc không thực hiện một số hành động nhất định. Thuật toán trong đó điều kiện được sử dụng được gọi là phân nhánh, vì tùy thuộc vào giá trị của điều kiện mà một số hành động nhất định sẽ được chọn.

Nói chung, sơ đồ của thuật toán phân nhánh sẽ như thế này: “ Nếu như tình trạng, Cái đó hành động 1, nếu không thì hành động 2» ( Nếu tôi gặp Sasha, tôi sẽ nói với anh ấy..., nếu không tôi sẽ tự mình đến gặp anh ấy.). Bạn cũng có thể sử dụng mẫu chưa hoàn chỉnh: “ Nếu như tình trạng, Cái đó hoạt động» ( Nếu tôi gặp Sasha, tôi sẽ nói với anh ấy...). Trong trường hợp này, không có hành động nào được đưa ra trong trường hợp không đáp ứng được điều kiện.

Điều kiện là một câu lệnh có thể đúng hoặc sai.

Chúng ta hãy lưu ý một lần nữa rằng có hai dạng phân nhánh - không đầy đủ (khi chỉ có một nhánh, tức là tùy thuộc vào tính thực tế của điều kiện, hành động được thực hiện hay không) và hoàn thành (khi có hai nhánh, tức là, tùy thuộc vào mức độ thực tế của điều kiện, hành động này hoặc hành động khác sẽ được thực hiện).

Thuật toán phụ trợ

Thuật toán phụ trợ– một thuật toán có thể được sử dụng trong các thuật toán khác bằng cách chỉ định tên của nó.

Một thuật toán phụ trợ được viết bằng ngôn ngữ lập trình được gọi là chương trình con. Khi tạo các chương trình cỡ trung bình, hãy sử dụng lập trình có cấu trúc, ý tưởng của nó là cấu trúc của chương trình phải phản ánh cấu trúc của vấn đề đang được giải quyết, sao cho thuật toán giải được hiển thị rõ ràng từ văn bản nguồn. Chương trình được chia thành nhiều chương trình con, mỗi chương trình con thực hiện một số hành động được chỉ định trong tác vụ ban đầu.

Bằng cách kết hợp các chương trình con, có thể hình thành một thuật toán cuối cùng bằng cách sử dụng các khối mã (chương trình con) có ý nghĩa ngữ nghĩa nhất định. Bạn có thể tham khảo các chương trình con này bằng tên của chúng. Rất đặc điểm quan trọng chương trình con là khả năng tái sử dụng chúng.

Hãy xem một ví dụ với nghệ sĩ đồ họa GRIS. Giả sử chúng ta cần tạo một thuật toán để vẽ số có bốn chữ số 1919.

Bạn có thể tạo một thuật toán dài theo đó người biểu diễn sẽ rút ra những con số này từng bước. Nhưng số 1 và số 9 được lặp lại hai lần. Thuật toán có thể được rút ngắn bằng thuật toán phụ trợ.

Kết quả là một thuật toán ngắn hơn và dễ hiểu hơn:

Số thuật toán "1919"
Bắt đầu
làm ĐƠN VỊ
nảy
làm chín
nảy
làm ĐƠN VỊ
nảy
làm chín
kết thúc

Các thuật toán phụ trợ UNIT và NINE ở đâu:

Phương pháp chi tiết tuần tự

Cách tiếp cận chúng tôi sử dụng giúp việc lập trình trở nên dễ dàng hơn nhiệm vụ phức tạp. Nhiệm vụ được chia thành các nhiệm vụ phụ đơn giản hơn. Giải pháp cho từng vấn đề được trình bày dưới dạng thuật toán phụ trợ và thuật toán chính tổ chức kết nối giữa chúng.

Một phương pháp lập trình trong đó chương trình chính được viết đầu tiên, các lệnh gọi đến các chương trình con chưa được soạn thảo được viết trong đó và sau đó các chương trình con này được mô tả được gọi là phương pháp chi tiết tuần tự (từng bước). Hơn nữa, số bước chi tiết có thể lớn hơn nhiều so với ví dụ của chúng tôi, vì bản thân các chương trình con có thể chứa các lệnh gọi đến các chương trình con khác.

Phương pháp lắp ráp

Một cách tiếp cận khác để xây dựng là có thể chương trình phức tạp: Ban đầu, nhiều chương trình con được biên dịch có thể cần thiết để giải quyết vấn đề, sau đó chương trình chính được viết có chứa các lệnh gọi đến chúng. Các chương trình con có thể được kết hợp thành một thư viện chương trình con và được lưu trữ trong trí nhớ dài hạn máy tính. Thư viện như vậy có thể được bổ sung dần dần bằng các chương trình con mới.

Ví dụ: nếu bạn tạo một thư viện gồm các thủ tục vẽ tất cả các chữ cái và số để điều khiển một nghệ sĩ đồ họa, thì chương trình lấy bất kỳ văn bản nào sẽ bao gồm các lệnh để truy cập các thủ tục thư viện.

Phương pháp được mô tả được gọi là lập trình lắp ráp.

Thông thường trong tài liệu lập trình, thuật ngữ sau đây được sử dụng: phương pháp chi tiết tuần tự được gọi là lập trình từ trên xuống, và phương pháp lắp ráp là p lập trình từ dưới lên trên.