Этапы решения задач на компьютере

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 11Следующая ⇒

▷ Похожие статьи

Процесс решения задачи на компьютере включает в себя следующие ос- новные этапы:

1) содержательная постановка задачи;

2) математическая постановка задачи (формализация задачи);

3) разработка алгоритма (алгоритмизация);

4) кодирование;

5) реализация программы на компьютере;

6) тестирование и отладка программы.

Цель постановки задачи (этапы 1–2) – сформулировать задачу предельно четко, наметить сначала общий подход к ее решению, а затем и строгий мате- матический метод. Ни одну серьезную задачу нельзя решить без ее правильной постановки. Этот процесс составляют три этапа решения задачи на ЭВМ.

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

Математическая постановка задачи – это формулировка задачи, как некото- рого раздела математики. На этом этапе рассматриваются те же вопросы, что и в содержательной постановке задачи, однако сформулированы они на языке мате- матики. И поскольку при этом используются только математические термины, имеющие каждый точное определение, то ответы на них получаются строго одно- значные. Переход к математической задаче дает возможность подобрать и приме- нить для ее решения математические методы.

ЭВМ может работать с данными только в том случае, если они организо- ваны строго определенным образом. Так, во многих языках программирования (ЯП) данные должны быть представлены в виде значений отдельных перемен- ных, либо сгруппированы в массивы, над которыми можно выполнять в основ- ном лишь ограниченный набор операций: арифметические; вычисления эле- ментарных функций; сравнения величин (логические операции).

Преобразование задачи, полученной на этапе математической постановки в формализованный вид, называется формализацией задачи. Этот процесс вы- полняется в два шага.

Шаг 1. Выбор структуры данных, т. е. представление данных и результа- тов задачи в виде, допустимом для обработки на ЭВМ (как правило, в виде со- вокупности переменных, массивов, файлов и т. д.).

Шаг 2. Выбор способа (порядка) решения задачи, который включал бы только те операции над элементами данных, которые допустимы в ЯП.

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

Формализация задачи заключается в подборе адекватного математическо- го объекта, соответствующего изучаемому предмету или явлению, определении типов и структур данных, необходимых для его описания. На этом этапе осуще- ствляется выбор идентификаторов¹ данных и описание математических соотно- шений (метода решения), позволяющих получить требуемый результат. Этап формализации выполняет человек, способный разработать математическое опи- сание задачи. От степени сложности задачи зависит, кто из специалистов должен выполнять этот этап. Если задача простая и не требует специальных математиче- ских знаний, то достаточно квалификации постановщика задачи.

Вернемся к нашему примеру. Для определения площади поверхности письменного стола, если он имеет прямоугольную форму, то измеряют его дли- ну и ширину, а затем перемножают полученные числа. В этом случае в качестве модели стола выбирают математический объект – прямоугольник. При более высоких требованиях к точности решения задачи прямоугольник придется за- менить другой моделью и учесть, например, закругления углов стола. Заметим, что модель не определяется объектом однозначно, но главное – надо быть уве- ренным, что она соответствует реальному объекту и отражает все его свойства, которые необходимы для решения поставленной задачи. Модель всегда осно- вана на некотором упрощении, однако, благодаря замене реального объекта со- ответствующей ему моделью появляется возможность сформулировать задачу его изучения как математическую и воспользоваться для ее решения средства- ми математики. Для повышения точности результатов модель приходится ус- ложнять, учитывая все новые и новые особенности изучаемого объекта.

Для нашего примера модель выглядит следующим образом: Исходные данные: a – ширина стола (см), b – длина стола (см). Выходные данные: S – площадь поверхности.

Математические соотношения: S = a · b.

¹ Идентификатор – символьное обозначение единицы данных.

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

Фактически, построение модели задачи начинается уже на предыдущем этапе, когда определяются исходные и выходные данные. На этапе моделиро- вания важным является выбор удобных и адекватных математических обозна- чений исходных данных и результатов, а также построение формул, уравнений, неравенств, используемых для решения поставленной задачи. Итак, создавая модель объекта, нужно:

1) выделить предположения, на которых будет основываться модель;

2) обозначить исходные и выходные данные, определить их структуру, тип и область допустимых значений;

3) выбрать метод решения задачи;

4) записать математические соотношения в соответствии с выбранным методом, связывающие результаты с исходными данными.

Выполнив «перевод» постановки задачи на язык математики, получают то, что называют математической постановкой задачи. Такая постановка задачи содержит описание исходных и выходных данных; математических выражений, по которым вычисляются выходные данные из исходных, возможно с исполь- зованием промежуточных вычислений, результаты которых должны заноситься в так называемые рабочие переменные.

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

Рассмотрим еще один пример математической модели задачи. Допустим, нужно вычислить среднюю скорость движения автомобиля, если известно рас- стояние и время, за которое автомобиль его проехал. Заметьте, что при поста- новке задачи точно указывается, что нужно вычислить – именно среднюю ско- рость, так как фактически ясно, что скорость автомобиля на всем участке не- равномерная. Далее указывается скорость чего – автомобиля. Эта информация нужна для того, чтобы определить, какие исходные данные нам необходимы для решения задачи. В данном случае нас не интересует такая исходная инфор- мация, как цвет, марка, номер автомобиля, т. е. эти несущественные черты ис- следуемого объекта для этой задачи отбрасываются (хотя для другой задачи они могут пригодиться). Во внимание принимается только то, что для вычисле- ния скорости автомобиля на участке нужно знать длину участка и время в пути. Из чего делаем вывод, что постановка задачи сформулирована корректно. Да- лее реальный объект – автомобиль заменяется абстрактной моделью – движу- щимся телом. В качестве удобных обозначений исходных данных и результатов выбираем общепринятые обозначения: скорость – V, расстояние – S, время – t. Таким образом, теперь мы можем записать математическую модель задачи:

Исходные данные: S – расстояние (км), t – время (ч).

Выходные данные: V – скорость (км/ч).

Математические соотношения: V = S/t.

Рассмотрим пример уточнения постановки задачи и ее формализацию.

Задача 1.

Известна следующая информация. В комнате имеются одна дверь и два окна одинакового размера, пол, потолок, стены. Все объекты имеют прямоугольную форму с известными сторонами. Требуется рассчитать:

а) количество краски в килограммах, необходимое для покраски пола и двери одинаковой краской;

в) количество обоев в погонных метрах, необходимое для оклейки стен. Какие данные еще необходимы для решения задачи? Описать формализо-

ванную постановку задачи.

Очевидно, что для решения задачи нужно вычислить площадь обрабаты- ваемых поверхностей. Для проведения расчетов по условию задачи имеются необходимые данные. Для определения количества краски в килограммах необ- ходимо знать норму ее расхода. Для определения количества обоев, например, в погонных метрах, необходимо знать ширину погонного метра.

Опишем формализованную постановку задачи, т. е. определим обозначе- ния переменных для исходных, выходных данных, а также для промежуточных расчетов.

Исходные данные: a – ширина комнаты (м), b – длина комнаты (м),   h – высота стен (м), da – ширина двери (м), dh – высота двери (м), fa – ширина окна (м), fh – высота окна (м), nrk – норма расхода краски, (кг/м²), bo – ширина погонного метра обоев (м).

Выходные данные: kk – количество краски (кг), ko – количество обоев

(пог. м).

Рабочие переменные: sp – площадь пола, sd – площадь двери,

sf – площадь одного окна, ss – площадь стен.

Кроме этого, математическая модель задачи включает описание расчет- ных формул: sp = a · b; sd = da · dh; sf = fa · fh; ss = 2(a · h) + 2(b · h) – 2sf – sd; kk = (sp + sd)·nrk; ko = ss / bo.

Третий, не менее важный, этап решения задачи на компьютере – алгорит- мизация. Алгоритмизация – процесс разработки и описания алгоритма решения какой-либо задачи. После того, как описана математическая модель задачи, не- обходимо, взяв ее за основу, разработать и записать алгоритм решения задачи. Алгоритм – это инструкция о том, в какой последовательности нужно выполнить действия при переработке исходного материала в требуемый результат.

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

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

1) достать ключ;

2) вставить ключ в замочную скважину;

3) повернуть ключ два раза против часовой стрелки;

4) вынуть ключ;

5) толкнуть дверь.

Или, например, Вы собрались в гости. Тогда Вам потребуется алгоритм того, как добраться до нужного дома. Он может состоять из следующих шагов:

1) выйти из дома;

2) повернуть налево;

3) пройти до автобусной остановки;

4) дождаться автобус № 20, идущий к центру города;

5) сесть в автобус № 20;

6) проехать три остановки;

7) выйти из автобуса;

8) перейти улицу;

9) пройти влево три квартала.

Несмотря на различие этих алгоритмов, изучив их, можно выявить общие свойства. Прежде всего, это строгий порядок выполнения действий. Давайте переставим в первом алгоритме второе и третье действие. Вы, конечно, сможе- те выполнить этот алгоритм, но дверь вряд ли откроется. А что произойдет, ес- ли поменять местами пятое и шестое действие во втором алгоритме? Он станет невыполнимым! Итак, для алгоритма важен не только набор действий, но и то, в каком порядке они выполняются. Так же важным является то, что каждое по- следующее действие выполняется только после завершения предыдущего. На- пример, если нужно прийти в гости вовремя, то лучше не пытаться во втором алгоритме выполнить седьмое действие, не закончив шестое.

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

Для больших задач алгоритмизация – весьма трудоемкий процесс, тре- бующий четкого представления процесса решения задачи, приводящего от ис- ходных данных к конечному результату. Сущность алгоритмизации проявляет- ся в выполнении ряда действий:

- разделение всего процесса решения задачи на локально-законченные части;

- определение последовательности выполнения каждой выделенной час- ти процесса;

- описание всех частей и правил перехода от одной части к другой;

- проверка правильности алгоритма.

Этап алгоритмизации выполняет человек, имеющий представление о про- граммировании. Уровень его квалификации определяет эффективность разра- ботанного алгоритма.

Кодирование (программирование) – описание алгоритма на каком-либо языке программирования, т. е. составление программы по разработанному на предыдущем этапе алгоритму. Программа – это представление алгоритма с по- мощью специальных символов, образующих последовательность команд, вос- принимаемых компьютером. Для составления программ существуют различные языки программирования. Язык программирования – это формальный язык, с помощью которого составляется набор команд для управления вычислительной машиной и процессом решения задачи. Результатом кодирования является ис- ходный текст программы, зафиксированный на каком-либо материальном носи- теле. Если текст программы набирается на компьютере, то это – обычный тек- стовый файл. Этап кодирования выполняет программист – человек, умеющий программировать на выбранном языке программирования.

Реализация программы на компьютере. Написанную программистом про- грамму необходимо записать в виде текстового файла. Но этого еще недостаточно для того, чтобы программа могла выполняться компьютером. Для получения ис- полняемого файла нужно выполнить еще несколько шагов. Весь процесс разра- ботки и выполнения программы на компьютере осуществляется в соответствую- щей языку системе программирования. Этот этап состоит из четырех шагов:

- ввод исходного текста программы;

- компиляция (трансляция);

- построение;

- выполнение.

На шаге компиляции осуществляется поиск и исправление синтаксиче- ских ошибок, допущенных на этапе составления программы, или при вводе ис- ходного текста. Если ошибок в исходном тексте нет, то программа транслиру- ется (переводится) в машинные коды. После успешной компиляции создается объектный модуль программы. На следующем шаге, называемом построение, подсоединяются библиотеки программ, данной системы программирования. После него создается загрузочный модуль (исполняемый файл), который затем и запускается на выполнение.

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

рых заранее определяются значения выходных данных. Если результаты рабо- ты программы на заданных исходных данных не совпадают с ожидаемыми ре- зультатами, это означает, что была допущена логическая ошибка на этапе со- ставления программы, а чаще всего на этапе алгоритмизации. В этом случае следует исправить алгоритм, затем выполнить 4, 5, 6 этапы.

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

Свойства алгоритмов

Согласно Государственному стандарту под алгоритмом понимается «точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату» (ГОСТ 19.781-74). Алгоритм включает систему правил, определяющих содержание и конечную последовательность дей- ствий (шагов и операций), выполняемых над некоторыми объектами с целью пе- реработки исходных и промежуточных данных в искомый результат. Это предпи- сание конкретному исполнителю о том, какие действия, над какими объектами и в каком порядке следует выполнять для решения поставленной задачи.

Дадим еще одно определение алгоритма, включающее описание его свойств: алгоритм – это система точных и простых предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения поставленной задачи при любых значениях исходных данных.

Правильно составленный алгоритм должен удовлетворять ряду свойств, некоторые из которых уже заложены в определении алгоритма. К свойствам ал- горитма относятся.

1. Дискретность. Заключается в том, что весь описываемый процесс должен быть разбит на последовательность отдельных шагов. Возникающая в результате такого разбиения запись представляет собой упорядоченную сово- купность четко разделенных друг от друга предписаний (директив, команд), образующих прерывную (или, как говорят, дискретную) структуру алгоритма: только выполнив требования одного предписания, можно приступить к выпол- нению следующего. Каждое последующее действие выполняется лишь после завершения предыдущего, т. е. алгоритм выполняется пошагово.

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

3. Результативность (конечность). Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма, процесс должен прекратиться за конечное число шагов и при этом должен быть получен какой-

либо определенный ответ. К результату, цели приходим за конечное число действий. Встречаются случаи, когда алгоритм не может быть выполнен, на- пример, возникает ошибка деления на 0. В этом случае результатом работы ал- горитма должно быть соответствующее сообщение.

4. Понятность. Алгоритм всегда формируется в расчете на конкретного исполнителя, понимающего его команды и выполняющего их чисто механиче- ски без каких-либо отклонений от предписаний. Исполнителем может быть че- ловек, робот, автоматическое устройство, ПЭВМ или любой другой объект, способный воспринять предписания и выполнить указанные в них действия. Используемые на практике записи алгоритмов составляются с ориентацией на определенного исполнителя¹. У исполнителя имеется перечень предписаний, которые он может исполнять. Такой перечень называется системой команд. Та- ким образом, алгоритм должен быть записан в рамках данной системы ко- манд, с тем, чтобы он был понятен исполнителю.

5. Детерминированность (определенность, однозначность). Это свойст- во означает, что запись алгоритма должна быть настолько четкой и понятной, чтобы у исполнителя не возникло затруднений в осмыслении и выполнении каждой команды. То есть, будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно, например,

«Умножить число х на одно из двух чисел а или b». Кроме этого, в алгоритмах недопустимы ситуации, когда после выполнения очередного действия исполни- телю неясно, какое действие должно выполняться на следующем шаге. Говоря иначе, алгоритм не должен давать исполнителю возможности выбора, а должен четко указывать на каком шаге, при каких условиях какие действия выполнять. Важен не только набор действий, но и то, в каком порядке они выполняются. Если порядок действий нарушается, то алгоритм либо может стать невы- полнимым, либо приведет к неправильным результатам.

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

6. Инвариантность по отношению к исполнителю. Означает, что алгоритм должен оставаться неизменным при выполнении его разными исполнителями.

7. Эффективность. Алгоритм должен быть составлен так, чтобы резуль- тат получался при использовании наименьшего количества наиболее простых операций.

Свойства дискретности, результативности, детерминированности и по- нятности являются обязательными для любого алгоритма. Разработчик алго- ритма должен следить за тем, чтобы алгоритм удовлетворял этим свойствам.

¹ Исполнитель алгоритма – это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом [10].

Способы записи алгоритма

В зависимости от сложности решаемой задачи и того, для кого и чего описывается алгоритм, используются разные способы записи алгоритма:

- вербальный (словесный, записанный на естественном языке);

- структурно-стилизованный;

- графический;

- программный.

Вербальный способ записи алгоритмов представляет собой словесное описание последовательности шагов для решения поставленной задачи. Необ- ходимые действия формулируются на языке, понятном человеку. Но для техни- ческой системы такое описание алгоритма является неприемлемым, оно не формализуемо, страдает многословностью. Этот способ удобен, например, для описания так называемых «бытовых» алгоритмов: как позвонить по междуго- родному телефону-автомату, как пользоваться стиральной машиной и т. п. При описании алгоритма с целью его дальнейшего кодирования для выполнения на вычислительной машине данный способ не имеет широкого распространения, но используется в учебной литературе для объяснения сути алгоритма. При этом способе отсутствует наглядность вычислительного процесса, так как нет достаточной формализации.

Для вычислительных задач используется словесно-формульное описание алгоритма, т. е. описание алгоритма с помощью слов и формул. Это наиболее простой способ. Для его понимания рассмотрим пример.

Задача 2.

Составить алгоритм начисления стипендии согласно следующему пра- вилу: если количество пятерок по результатам сессии составляет 100 %, то стипендия – 900 р., при количестве пятерок от 50 до 100 % – 600 р., при количестве пятерок менее 50 % стипендия составит 400 р.

Сформулируем задачу в математическом виде: вычислить

900, если Кп = 100 %

ST = 600, если 50% ≤ Кп < 100 %,

400, если Кп < 50 %

где ST – размер стипендии; Кп – количество пятерок по результатам сессии.

Словесно-формульное описание алгоритма решения задачи:

1. Ввести Кп, перейти к п. 2.

2. Если Кп = 100 %,то ST = 900, перейти к п. 4, иначе – перейти к п. 3.

3. Если 50 % ≤ Кп < 100 %, то ST = 600, перейти к п. 4, иначе ST = 400,

перейти к п. 4.

4. Вывести (отпечатать) значение ST, перейти к п. 5.

5. Вычисления прекратить.

На примере видно, что словесно-формульное описание алгоритма – это задание инструкций с использованием математических символов и выражений в сочетании со словесными пояснениями. При использовании этого способа может быть достигнута любая степень детализации, нагляднее, чем в словесном способе, но не строго формально.

Структурно-стилизованный способ записи алгоритмов основан на фор- мализованном представлении предписаний, задаваемых путем использования ограниченного набора типовых синтаксических конструкций. Разновидностями структурно-стилизованного способа являются псевдокод, построчная алгорит- мическая нотация, структурные диаграммы. Структурные диаграммы могут ис- пользоваться в качестве структурных блок-схем, для показа межмодульных связей, для отображения структур данных, программ и систем обработки дан- ных. Существуют различные структурные диаграммы: диаграммы Насси- Шнейдермана, диаграммы Варнье, Джексона, МЭСИД и др. Псевдокод позво- ляет формально изображать логику программы, не заботясь при этом о синтак- сических особенностях конкретного языка программирования. Обычно пред- ставляет собой смесь операторов языка программирования и естественного языка. Является средством представления логики программы, которое можно применять вместо блок-схемы.

Примером такого способа является предложенный академиком А. П. Ер- шовым алгоритмический язык в русской нотации (АЯРН), описание которого дано в приложении.

Алгоритм решения этой задачи на АЯРН выглядит следующим образом: НАЧАЛО

ВЕЩЕСТВЕННОЕ Кп, ST

ВВОД Кп

ЕСЛИ Кп = 100 ТО ST:= 900

ИНАЧЕ ЕСЛИ Кп > 50.И. Кп < 100 ТО ST:= 600

ИНАЧЕ ST:= 400

КОНЕЦ развилки; КОНЕЦ развилки;

ВЫВОД ST

КОНЕЦ.

Графический способ описания алгоритма представляет собой схему, по- строенную с использованием взаимосвязанных графических блоков, называе- мую блок-схемой. Каждый блок обозначает определенный тип инструкции. Блок-схемы используются для компактного и наглядного изображения алго- ритма. Кроме этого, блок-схемы позволяют разрабатывать структурированные алгоритмы, что упрощает процесс написания программы и ее отладку. Графи- ческий способ описания алгоритмов в виде блок-схем используется в данном пособии как основной, поскольку блок-схемы не устаревают и их удобно «пе- реводить» на любой язык программирования.

Программный способ записи алгоритмов – написание алгоритма на языке программирования, т. е. составление программы.

Структура программы на любом языке программирования в общем слу- чае выглядит следующим образом

<Заголовок> – начало программы.

<Операторы описания> – невыполняемые операторы, предназначенные для объявления используемых в программе данных.

<Ввод исходных данных> – операторы или функции ввода исходных данных.

<Выполняемые операторы> – последовательность операторов непосред- ственно, реализующих алгоритм

<Вывод результатов> – операторы или функции вывода на экран, печать или в файл выходной информации.

<Конец> – завершение программы.

Программа на языке программирования – последовательность операторов языка. Оператор – это основной объект программы, который указывает, какие действия должны быть реализованы на определенном этапе работы. Операторы описания необходимы для задания характеристик данных, а выполняемые опе- раторы – для описания процесса их обработки. Операторы строятся с помощью служебных слов и выражений.

Основные понятия, используемые при разработке алгоритма

К основным понятиям, используемым при разработке алгоритма решения задачи на компьютере, относятся термины: данные, константы, переменные, выражения, инструкции (операции, операторы, действия). При составлении ал- горитма важным является выбор структур и типов данных. Данные, с которыми работает алгоритм, обозначаются, чаще всего с помощью переменных, т. е. бу- квенного обозначения данных. Любая переменная имеет имя (обычно начина- ется с буквы) и значение, соответствующего типа.

Данные, с которыми работает алгоритм и программа, различаются по ти- пу и назначению и структуре. Наиболее часто используются четыре основных типа данных: целые (integer), вещественные (real), логические (logical), сим- вольные (character). Переменная целого типа может принимать только целочис- ленные значения (положительные, отрицательные, ноль). Переменная вещест- венного типа принимает любые числовые значения (целые, дробные). Перемен- ная логического типа может принимать одно из двух значений: «истина» или

«ложь». Переменная символьного типа в качестве значения может содержать любой символ; в алгоритмах символьное значение записывается в апострофах.

По назначению данные могут быть константами и переменными. Кон- станта – это такой объект, значение которого остается неизменным при вы- полнении алгоритма. Константы могут использоваться в виде конкретных зна- чений, либо с помощью именованных констант. Для именованных констант имя и значение определяется в начале алгоритма. В форме переменных пред-

ставляют поименованные данные, характеризующиеся постоянным типом и изменяющимся в процессе выполнения операций значением Переменная – это такой объект, значение которого в ходе выполнения алгоритма может неодно- кратно меняться (а может и не изменяться). Значения переменных могут вво- диться, либо вычисляться в ходе выполнения алгоритма. Таким образом, каж- дая переменная имеет имя (идентификатор) и значение.

По структуре различают простые данные (переменные) – одно значение, и составные данные (переменные) – множество значений (массивы).

Для того чтобы ясно представить как «работает» алгоритм с данными, опишем простейший автомат, который предназначен для выполнения операций, предписанных этим алгоритмом

В состав такого автомата входят:

- память, состоящая из отдельных ячеек;

- считывающая/записывающая головка;

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

Головка, получив указание от процессора, может записывать в ячейку или считывать из нее одну константу.

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

Переменные имеют буквенно-символьное обозначение. Например, 1, n, a, a1, b, H2 – переменные. Одновременно обозначение переменной является ин- дексом ячейки, в которую будут записываться константы. Любая из таких кон- стант называется значением переменной. Например, Z является переменной и адресом ячейки Z одновременно. С алгоритмической точки зрения понятия “переменнаяˮ и “адрес ячейкиˮ памяти являются идентичными.

Запись вида Y:= 5.5 следует понимать так: записать константу 5.5 в ячей- ку с адресом Y (если до этой операции в ячейку была записана константа, то она будет затерта, а на ее место будет помещена константа 5.5). Произносить эту запись следует так: “переменной Y присвоить значение 5.5ˮ.

Запись вида L:= M следует понимать так: прочитать константу, располо- женную по адресу M и скопировать эту константу в ячейку с адресом L (при этом константа из ячейки M не удаляется, а остается такой, какой она была до чтения). Произносить эту запись нужно так: «переменной L присвоить значение переменной M (или просто: L присвоить M)».

Большинство действий в алгоритмах используют выражения. Выражение

определяет, какие операции, в какой последовательности и со значением каких

переменных и констант требуется выполнить для получения нового значения. Выражения состоят из операндов (переменных, констант) и знаков операций (+, -, *, /, **, >, <, =, <>)¹. Выражения показывают, какие операции следует вы- полнять над операндами. Выражения, в зависимости от входящих в него опера- ций и типов данных, бывают арифметические, логические, строковые. Пример арифметических выражений: 5 + 8; 2 * (a - b); x**2 / (c + d). Пример логических выражений: 5 < 7; a = b; 2 > 200; (a > b).И.(d < c). Значения второго и четвертого логических выражений зависят от значений входящих в него переменных. Зна- чение первого выражения – ИСТИНА, значение третьего выражения – ЛОЖЬ.

Действия, которые выполняются над данными, записываются в виде ин- струкций. Для конкретного исполнителя набор инструкций ограничен. Для языков программирования – это набор операторов языка. Для алгоритмов, за- писанных в виде блок-схем, это набор блоков. Каждый блок определяет опре- деленный тип инструкции.

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров