Основные алгоритмы. Алгоритмы и программы. Принципы разработки алгоритмов и программ

Чтобы писать приложения разного уровня сложности, сначала необходимо получить знания по том, как это делается. И начинать желательно с самой основы алгоритмизации и программирования. Вот о них мы и поговорим в рамках статьи.

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

Чем она занимается?

Перед информатикой стоят такие задачи:

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

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

Представление алгоритмов

Они могут быть записаны значительным количеством способов. Наиболее популярными являются следующие:

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

Псевдокод. Набросок костяка программы.

Запись алгоритма

Как начать создавать свой прообраз программы, функции или процедуры? Для этого достаточно пользоваться такими общими рекомендациями:

У каждого алгоритма должно быть своё имя, которое объясняет его смысл.
Обязательно следует позаботиться о присутствии начала и конца.
Должны описываться входные и выходные данные.
Следует указать команды, с помощью которых будут выполняться определённые действия над конкретной информацией.

Способы записи

Представлений алгоритма может быть целых пять. Но вот способов записи всего лишь два:

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

Разрабатываем программную структуру

Можно выделить три основных вида:

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

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

Программирование

Важным является на котором будут создаваться программы. Следует учесть, что многие из них «заточены» под конкретные условия работы (например, в браузере). В целом языки программирования делят на две группы:

Функциональные.
Операторные:

Не процедурные;

Процедурные.

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

процедурные;
проблемные;
объектные.

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

Заключение

При работе с алгоритмами (а в последующем и с программами) следует стремиться продумать все детали до самой мелкой. В последующем выявление каждого непроработанного участка кода приведёт только к дополнительным работам, увеличению затрат на разработку и сроков выполнения задачи. Тщательное планирование и проработка всех нюансов позволит значительно сэкономить время, усилия и деньги. Что ж, сейчас могут сказать, что после прочтения данной статьи у вас есть понятие про основы алгоритмизации и программирования. Осталось только применить эти знания. Если есть желание изучить тему более детально, могу посоветовать книгу «Основы алгоритмизации и программирования» (Семакин, Шестаков) 2012 года.

Аннотация: Предмет науки программирования. Пример и свойства алгоритма. Парадигмы программирования (директивное, объектно-ориентированное и функционально-логическое программирование).

Эта глава, с которой начинается изучение курса, служит двум основным целям:

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

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

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

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

Предмет науки программирования

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

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

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

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

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

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

Пример и свойства алгоритма

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

Задача 1.1 . Придумайте алгоритм, вводящий натуральное число, большее единицы,который находит наименьший простой делитель этого числа.

Алгоритм решения задачи .

Алгоритм П :

П1 : Положить целое число равным двум и перейти на шаг П2.

П2 : Если делится нацело на , то завершить работу алгоритма, выдав в качестве результата ; иначе перейти на шаг П3.

П3 : Увеличить значение на единицу и перейти на шаг П2.

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

k = 3	k = 4	k = 2
П1: i = 2	П1: i = 2	П1: i = 2
П2: i = 2	П2: i = 2	П2: i = 2
П3: i = 3
П2: i = 3

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

Основные свойства любого алгоритма - это конечность, определенность, вход (ввод), выход (вывод) и эффективность. Рассмотрим их последовательно более подробно.

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

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

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

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

Выход (output) . Алгоритм всегда обязан иметь одну или несколько выходных величин. В случае алгоритма П такой величиной является число . Алгоритмы, не имеющие выходных данных, бесполезны на практике, и мы не будем их изучать.

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

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

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

Тема 1.3: Системное программное обеспечение

Тема 1.4: Сервисное программное обеспечение и основы алгоритмизации

Введение в экономическую информатику

1.4. Сервисное программное обеспечение ПК и основы алгоритмизации

1.4.2. Основы алгоритмизации и языки программирования

Алгоритм и его свойства

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

Алгоритм означает точное описание некоторого процесса, инструкцию по его выполнению. Разработка алгоритма является сложным и трудоемким процессом. Алгоритмизация – это техника разработки (составления) алгоритма для решения задач на ЭВМ.

Изобразительные средства для описания (представление) алгоритма

Для записи алгоритма решения задачи применяются следующие изобразительные способы их представления:

Словесно- формульное описание.
Блок-схема (схема графических символов).
Алгоритмические языки.
Операторные схемы.
Псевдокод.

Для записи алгоритма существует общая методика:

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

Общий вид алгоритма:

название алгоритма;
описание данных;
начало;
команды;
конец.

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

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

Каждый этап вычислительного процесса представляется геометрическими фигурами (блоками). Они делятся на арифметические или вычислительные (прямоугольник), логические (ромб) и блоки ввода-вывода данных (параллелограмм).

Рис. 1.

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

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

Операторные схемы алгоритмов. Суть этого способа описания алгоритма заключается в том, что каждый оператор обозначается буквой (например, А – арифметический оператор, Р – логический оператор и т.д.).

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

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

Принципы разработки алгоритмов и программ

Типы алгоритмических процессов

По структуре выполнения алгоритмы и программы делятся на три вида:

линейные;
ветвящиеся;
циклические;

Линейные вычислительные процессы

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

Алгоритмы разветвляющейся структуры

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

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

Рис. 2.

Циклические вычислительные процессы

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

Существуют две схемы циклических вычислительных процессов.

Рис. 3.

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

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

Существуют циклы с известным числом повторений и итерационные циклы. При итерационном цикле выход из тела цикла, как правило, происходит при достижении заданной точности вычисления.

Языки программирования

Языки программирования – это искусственные языки записи алгоритмов для исполнения их на ЭВМ. Программирование (кодирование) - составление программы по заданному алгоритму.

Классификация языков программирования. В общем, языки программирования делятся на две группы: операторные и функциональные. К функциональным относятся ЛИСП, ПРОЛОГ и т.д.

Операторные языки делятся на процедурные и непроцедурные (Smalltalk, QBE). Процедурные делятся на машино - ориентированные и машино – независимые.

К машино – ориентированным языкам относятся: машинные языки, автокоды, языки символического кодирования, ассемблеры.

К машино – независимым языкам относятся:

Процедурно – ориентированные (Паскаль, Фортран и др.).
Проблемно – ориентированные (ЛИСП и др.).
Объектно-ориентированные (Си++, Visual Basic, Java и др.).

Бураков П.В., Косовцева Т.Р. Информатика. Алгоритмы и программирование. Учебное пособие.-СПб НИУ ИТМО, 2013. – 83с.

Учебное пособие предназначено для студентов экономических специальностей специальности 080100 «Экономика» гуманитарного факультета, изучающих дисциплину «Информатика». Пособие представляет собой вводный курс по построению алгоритмов и по программированию на языке Турбо Паскаль. Пособие содержит много примеров. Подробно излагаются теоретические аспекты построения алгоритмов и основ программирования. Во второй части учебного пособия приводтся лабораторный практикум.

В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет информационных технологий, механики и оптики» на 2009– 2018 годы.


Постановка задачи.........................................................................................................................
Разработка математической модели............................................................................................
Выбор метода численного решения.............................................................................................
Разработка алгоритма и структуры данных................................................................................
Реализация алгоритма в виде программы...................................................................................
Отладка и тестирование программы............................................................................................
Решение задачи на компьютере...................................................................................................
ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ.............................................................................
Описание алгоритма......................................................................................................................
Схема алгоритма..........................................................................................................................
Структурированные схемы алгоритмов....................................................................................
СРЕДСТВА РЕАЛИЗАЦИИ АЛГОРИТМА..........................................................................................
Критерии выбора языка программирования.............................................................................
СТРУКТУРА ПРОГРАММЫ И ЕЕ ЭЛЕМЕНТЫ.................................................................................
Основные элементы программирования...................................................................................
Алфавит и словарь языка TurboPascal (TPascal).......................................................................
Структура программы.................................................................................................................
ТИПЫ ДАННЫХ......................................................................................................................................
Скалярные типы данных.............................................................................................................
Структурированные типы данных.............................................................................................
ВВОД-ВЫВОД ДАННЫХ.......................................................................................................................

Процедуры ввода-вывода...........................................................................................................
ОПЕРАТОРЫ............................................................................................................................................
Общие сведения...........................................................................................................................
Простые операторы.....................................................................................................................
Структурные операторы.............................................................................................................
Условные операторы...................................................................................................................
Операторы цикла.........................................................................................................................
МАССИВЫ................................................................................................................................................
Действия над массивами.............................................................................................................
Действия над элементами массива............................................................................................
Операции с матрицами................................................................................................................
ПРОЦЕДУРЫ И ФУНКЦИИ...................................................................................................................
Необходимость структуризации в программировании............................................................
Подпрограммы в языке ТPascal..................................................................................................
Процедуры....................................................................................................................................
Функции.......................................................................................................................................
Механизм передачи параметров................................................................................................
ФАЙЛЫ.....................................................................................................................................................
Общие сведения...........................................................................................................................
Описания файлового типа..........................................................................................................
Средства обработки файлов.......................................................................................................
Текстовые файлы.........................................................................................................................

ЛАБОРАТОРНЫЙ ПРАКТИКУМ..........................................................................................................
Лабораторная работа 1.		Программирование линейных и	разветвляющихся
вычислительных процессов.............................................................................................................
Лабораторная работа № 2.	Циклические вычислительные процессы...................................
Лабораторная работа № 3.		Операции с массивами.................................................................
Лабораторная работа № 4.	Операции с файлами.....................................................................
Лабораторная работа 5. Процедуры и функции......................................................................
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.....................................................................................................

ЭЛЕМЕНТЫ ТЕХНОЛОГИИ РЕШЕНИЯ ПРАКТИЧЕСКИХ ЗАДАЧ НА КОМПЬЮТЕРЕ

Решение задач с применением персонального компьютера включает следующие основные этапы.

1. Постановка задачи.

2. Разработка математической модели.

3. Выбор метода численного решения для расчетных задач.

4. Разработка алгоритма решения и структуры данных.

5. Реализация алгоритма в виде программы.

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

7. Решение задачи на компьютере, численные эксперименты и анализ результатов.

Постановка задачи

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

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

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

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

Разработка математической модели

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

Математической моделью задачи, сформулированной в примере 1 является формула: S = 0,5 a t 2 , где в качестве основной переменной выступает время t , параметром движения является ускорение а . Формула показывает зависимость между длиной пути и временем в соответствии с законом механики.

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

S = ∫ V (t) dt ,

при этом закон изменения скорости V(t) в зависимости от времени может быть достаточно сложным и определить значение интеграла аналитически не удается. Поэтому в большинстве случаев практически целесообразно использовать приближенные методы решения.

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

Выбор метода численного решения

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

∫ f (x ) dx ≈ ∆ x ∑ f (x i ) , где ∆х - шаг интегрирования (const), ∆х=(b-a)/n,

x i+1 =xi +∆ х, x1 =a , xn+1 =b

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

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

Разработка алгоритма и структуры данных

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

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

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

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

Реализация алгоритма в виде программы

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

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

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

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

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

При программировании и вводе данных с клавиатуры могут быть допущены ошибки. Их обнаружение, локализацию и устранение выполняют на этапе отладки и испытания (тестирования) программы.

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

По данным разных авторов, этап отладки и тестирования программы занимает от 50 до 70 % времени, затрачиваемого на все этапы создания программы и получения решения. В связи с важностью и трудоемкостью этапа отладки все современные системы программирования имеют специальные средства, помогающие в обнаружении и устранении ошибок. Уже на этапе разработки алгоритма полезно предусмотреть простейшие средства контроля, встраиваемые в разрабатываемую программу: печать введенных данных непосредственно после их считывания в память машины (эхо-печать), печать промежуточных результатов в узловых точках. Но главное - надо максимально упрощать структуру программы за счет расчленения ее на модули, реализуемые в виде подпрограмм или процедур, и использования конструкций языка, наиболее простых и освоенных программистом.

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

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

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

Контрольные вопросы

1. Какие факторы влияют на эффективность решения задач на компьютере?

2. Перечислите этапы решения задач на компьютере.

3. Каковы основные требования к математической модели задачи?

4. Назовите главные характеристики алгоритмов.

5. Какие особенности следует учитывать при разработке программ на компьютере?

6. Чем завершается разработка алгоритма?

ПОСТРОЕНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

Описание алгоритма

Под алгоритмом понимается конечная последовательность точно сформулированных правил решения некоторого касса задач. Алгоритм обладает следующими свойствами:

Определенность. Все действия, которые необходимо произвести должны быть строго определены.

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

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

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

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

Правильность . Способность алгоритма давать правильные результаты решения поставленных задач.

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

Рассмотрим алгоритмы решения нескольких задач. Задача 1 . Составить алгоритм вычисления x по формуле

x = a (r − q ) 2 , где p ≠ -12.

p + 12

1. Начало;

2. Вычислить b:= p + 12;

3. Вычислить c:= r – q;

4. Вычислить d:= c c;

5. Вычислить e:= a d;

6. Вычислить x:= e / b;

7. Записать результат: x;

В записи алгоритма решения задачи 1 введены буквенные обозначения

– переменные. Так, через b обозначено p + 12 , через c – разность r – q. Запись

b:= p+12 означает, что вначале должна быть найдена сумма p + 12 при определенных значениях p, а затем это значение присваивается переменной b.

Придавая a, p, q, r разные значения, будем получать различные задания на вычисление x . Поэтому алгоритм обычно позволяет решать не одну, а целый класс задач. Такую особенность алгоритма называют массовостью алгоритма. Возможны алгоритмы, решающие только единственную задачу.

Величины a, p, q, r, 12 составляют исходные данные для алгоритма, 12

– постоянную составляющую, a, p, q, r – переменную составляющую информации. Величины b, c, d, e являются вспомогательными переменными, x – результат исполнения алгоритма.

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

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

Задача 2 . По формуле

x = − b ± b 2 − 4 ac составить алгоритм решения квадратного уравнения

ax2 + bx + c = 0 (a ≠ 0).

1. Начало;

2. p:= 2a;

3. D:= b 2 – 4ac;

4. Если D ≥ 0, то перейти к п. 5, иначе к п. 10;

5. d:= D ;

6. x 1 : = − b − d ; p

7. x 2 : = − b + d ; p

8. Записать результат: x 1 , x2 ;

9. Перейти к п. 11;

10. Записать результат: уравнение действительных корней не имеет;

11. Конец.

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

Команды, определяющие порядок исполнения операций, подразделяются на два типа: команды условного перехода и команды безусловного перехода . К командам условного перехода относится, например, правило 4 алгоритма решения задачи 2 . Правило 9 содержит безусловный переход.

В командах условного перехода обязательно присутствует логическое условие типа: если α ◊ β , то …(где ◊ - один из операторов > , ≥ , < , ≤ , = , ≠ ).

Схема алгоритма

Схема алгоритма представляет собой графическое изображение алгоритма с помощью определенным образом связанных между собой блоков. Каждый блок изображается определенной фигурой. Блоки в схеме соединяются дугами. Дуги указывают порядок следования блоков при исполнении алгоритма. Типы блоков представлены на рисунке 1.

Рис.1 . Типы блоков

Прямоугольник вместе с заключенным в нем этапом вычисления S называют функциональным блоком , или процессом (рис.1, а). Ромб с заключенным в нем условием P называют блоком проверки условия , или решением (рис.1, б). Он используется для управления порядком исполнения блоков в схеме алгоритма. Из функционального блока выходит одна стрелка, а из блока проверки условия – две. Последнее объясняется тем, что в результате исполнения команды проверки условия получаем либо выполнение (да), либо невыполнение (нет) заданного условия P. Информационный блок (рис.1, в) используется для ввода и вывода А. Блоки (рис.1, г) и (рис.1, д) называют соответственно начальным и конечным . Блок-схема решения задачи начинается в начальном блоке и заканчивается в конечном.

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

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

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

На рисунках 2 и 3 изображены схемы алгоритмов решения задачи нахождения суммы n - чисел: a1 , a2 , a3 , a4 ,.., an .

2.4.1. Понятие базовых алгоритмов

2.4.2. Алгоритмы линейной структуры

2.4.3. Базовые алгоритмы разветвляющихся структур и примеры их программирования

2.4.4. Базовые алгоритмы регулярных циклических структур и примеры их программирования

2.4.5. Базовые алгоритмы итеративных циклических структур и примеры их программирования

2.4.6. Базовые алгоритмы обработки одномерных массивов

2.4.7. Базовые алгоритмы обработки двумерных массивов

2.4.8. Контрольные вопросы по теме «Базовые алгоритмы и примеры их реализации»

2.4.9. Тестовые задания по теме «Базовые алгоритмы и примеры их реализации»

2.4.1. Понятие базовых алгоритмов

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

К базовым алгоритмам императивного программирования можно отнести:

Простейшие алгоритмы, реализующие базовые алгоритмические структуры.

Алгоритмы работы со структурами данных . Они определяют базовые принципы и методологию, используемые для реализации, анализа и сравнения алгоритмов. Позволяют получить представление о методах представления данных. К таким структурам относятся связные списки и строки, деревья, абстрактные типы данных, такие как стеки и очереди.

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

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

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

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

2.4.2. Алгоритмы линейной структуры

Пример 2.4.2-1.

где x = -1,4; y = 0,8;переменныеkиm– целого типа, остальные переменные - вещественного типа;[n]- целая часть числаn.

Схема алгоритма и программы на языках QBasic, Pascal, C++ , представлены на рис. 2.4.2-1.

Следует обратить внимание на то, что целая переменная k получила округленное значениеn , а целая переменнаяm - усеченное с помощью функцииFIX() до целой части значенияn.

Пример 2.4.2-2 . Вычислить и вывести на экран значения следующих величин:

где x = 2.9512; y = 0.098633;переменныеiиj– целого типа; остальные переменные – вещественного типа.

Схема алгоритма и коды программ представлены на рис. 3.2.1-2.

Рис. 2.4.2-2.

Результаты выполнения программы при указанных выше значениях исходных данных имеют следующий вид:

Пример 2.4.2-3. Вычислить и вывести на экран значение первой космической скорости.

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

где – гравитационная постоянная; M – масса Земли;
– расстояние от центра Земли до космического аппарата.

Схема алгоритма и коды программ представлены на рис. 3.2.1-3.

Рис. 2.4.2-3.

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