Последовательность подготовки и решения задачи на ЭВМ

End.

Приведем перевод ключевых слов для понимания алгоритма.

var – переменные; integer [интедже]– целый;

readln [риидлн]– ввод данных с клавиатуры;

writeln [райтелн]– вывод данных на экран;

begin – начало текста программы или ее блока;

end – конец текста программы или ее блока; until [антил]– пока;

halt – конец вычислений; then [зен]– тогда;

if – если (проверка условия); else [элз]– иначе;

repeat [репиит]– повторять; false [фолс] – ложно.

Если подставить вместо английских слов их русский перевод, то получим описание алгоритма, близкое к описанию на естественном языке.

2.3. Базовые алгоритмические структуры

<TBODY>Логическая структура любого алгоритма может быть представлена комбинацией трех базовых (основных) структур: следование, ветвление, цикл.

1. Базовая структура “следование”. Образуется из последовательности действий, следующих строго одно за другим.

Например, требуется вычислить величину y по формуле y = ax² + bx при произвольных a, b, x. Блок-схема соответствующего алгоритма имеет вид, приведенный на рис 2.2. В данном случае алгоритм состоит из простой последовательности действий (блоков). Значит, </TBODY>он соответствует структуре “следование”.

	Рис. 2.2. Алгоритм вычисления по формуле y = ax^2 + bx

2. Базовая структура “ветвление” обеспечивает в зависимости от результата проверки выполнения некоторого условия (да или нет) выбор одного из альтернативных путей работы алгоритма.

Структура “ветвление” существует в двух основных вариантах:

если – то:

если – то – иначе.

В алгоритме примера 2.1 присутствуют оба варианта этой структуры. После блока “m = n?” в случае положительного ответа выполняется действие “Вывести n”, а в случае отрицательного – работа алгоритма продолжается далее. Таким образом, реализована структура “если – то”. После блока “m > n?” в случае положительного ответа выполняется действие “m = m – n”, а в случае отрицательного (т.е. иначе) – действие “n = n – m”,. Таким образом реализована структура “если – то – иначе”.</TBODY>

3. Базовая структура “цикл”. Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.

Пример 2.2. Рассмотрим следующую задачу. Двум бойцам, посланным в разведку, надо перебраться через широкую реку. У берега в маленькой лодке удят рыбу два мальчика. Как бойцам с помощью этих детей перебраться на другой берег, если лодка выдерживает либо одного взрослого, либо двоих детей?

Пусть, для определенности, бойцам надо перебраться с правого берега на левый. Предлагается следующий алгоритм решения задачи.

1. Оба мальчика переправляются на левый берег.

2. Один мальчик возвращается на правый берег, второй – остается на левом.

3. Первый боец переправляется на левый берег, а первый мальчик остается на правом.

4. Второй мальчик переправляется на правый берег.

5. Оба мальчика переправляются на левый берег.

6. Один мальчик возвращается на правый берег, второй – остается на левом.

7. Второй боец переправляется на левый берег.

8. Второй мальчик переправляется на правый берег.

Заметим, что шаги 1 – 4 почти совпадают с шагами 5 – 8, разница только в номере переправляемого бойца. Очевидно, что с помощью подобного алгоритма можно переправить любое количество N бойцов, а не только двоих. Для этого надо выполнить следующий алгоритм.

1. Повторять шаги со 2 по 6, увеличивая каждый раз на 1 значение k от 1 до N.

2. Оба мальчика переправляются на левый берег.

3. Один мальчик возвращается на правый берег, второй – остается на левом.

4. k-й боец переправляется на левый берег, а первый мальчик остается на правом.

5. Второй мальчик переправляется на правый берег.

6. Если k = N, то стоп.

Это будет циклический алгоритм, тело которого составляют шаги 2 – 6. Другой вариант циклической структуры дан в примере 2.1. В нем телом цикла являются шаги 2 – 4.

Подготовка и решение инженерной задачи на ЭВМ (электронной вычислительной машине) включает в себя ряд последовательно выполняемых этапов.

1) постановка задачи;

2) составление математического описания задачи;

3) разработка алгоритма решения;

4) составление текста программы;

5) ввод программы в ЭВМ, ее трансляция и отладка;

6) ввод исходных данных и выполнение программы (счет);

7) анализ результатов.

Постановка задачи должна включать в себя

- цель решения;

- словесную формулировку самой задачи в терминах той области знаний, для которой она решается;

- перечень исходных данных, необходимых для решения задачи;

- перечень искомых величин и форму их представления;

- сведения о требуемой точности счета.

Во многих случаях в постановку задачи включают ее экономическое обоснование.

Математическое описание (математическая модель) задачи представляет собой формализованную запись содержания поставленной задачи в виде совокупности математических соотношений, которые связывают между собой исходные данные и результаты счета. Математическая модель технической или научной задачи формулируется, как правило, с использованием понятий таких математических дисциплин, как дифференциальное и интегральное исчисление, линейная алгебра и т.д.

Вспомним пример 1.1.Митя и Алеша вместе собрали 40 грибов. Митя собрал на 10 грибов больше, чем Алеша. Сколько грибов собрал каждый мальчик?

В постановке задачи сформулирована цель – узнать количество грибов, собранное каждым мальчиком. Записав условия задачи в формализованном виде, мы получим математическую модель. Обозначим х и у – количество грибов, собранное Митей и Алешей, соответственно. Составим систему уравнений

,

которая и является математической моделью процесса собирания грибов. Чтобы решить задачу, надо составить алгоритм, например, на основе правила Крамера.

Трансляция программы – перевод текста программы с алгоритмического языка (например, PASCAL) на язык машинных команд. Для этого используется специальная программа – транслятор, которая просматривает текст программы и осуществляет автоматический перевод.

Отладка программы – анализ работы программы и исправление ошибок. Существует два вида ошибок: синтаксические и семантические (см. далее определения синтаксиса и семантики языка программирования). Синтаксические ошибки обусловлены неправильным синтаксисом текста программы, т.е. если текст написан с нарушением правил выбранного языка программирования. Поскольку в транслятор заложены синтаксические правила языка, то при трансляции синтаксические ошибки обнаруживаются самим компьютером и выдаются соответствующие сообщения.

Семантические ошибки (смысловые) возникают при неправильно составленном алгоритме. В этом случае программа, даже составленная по всем правилам, выдает неправильный результат. Такие ошибки не могут быть исправлены автоматически, а требует активного вмешательства программиста. Наиболее универсальный способ обнаружения семантических ошибок – тестирование. Тестирование программы – пробное решение примеров с заранее известными ответами. Если ответ, полученный программой не совпадает с известным, это означает, что программа содержит ошибки. Правильно составленный тест позволяет достаточно точно определить ошибочный участок текста программы (локализовать ошибку), найти ее и исправить. Составление хороших тестов – весьма сложное занятие, требующее большого мастерства и опыта.

Пример 2.3. Пусть необходимо составить программу решения системы уравнений, полученной в примере 1.1. Воспользуемся для этого правилом Крамера. Представим данную систему в общем виде

Тогда, согласно правилу Крамера, решение будет иметь следующий вид:

; , где D = А11×А22 – А21×А12, Dx = b1×A22 – b2×A12,

Dy = A11×b2 – A21×b1.

Соответствующая программа будет иметь вид:

var x,y,A11,A12,A21,A22,b1,b2,Dx,Dy,D: real;

begin readln(A11,A12,b1);

readln(A21,A22,b2);

D:=A11*A22-A21*A12;

Dx:=b1*A22-b2*A12; Dy:=A11*b2-A21*b1;

x:=Dx/D; y:=Dy/D;

writeln(x:10:2,y:10:2);

readln;

Дата добавления: 2014-01-04