практика. Теория._Основные_понятия_алгоритмизации_и_программирования. 1. Основные понятия алгоритмизации и программировани Этапы решения задач на эвм
 Скачать 433.18 Kb.
|
|
1. Основные понятия алгоритмизации и программирования 1.1. Этапы решения задач на ЭВМ Задачи, решаемые с помощью ЭВМ, можно классифицировать по различ- ным критериям: по типу информации и информационным технологиям, по спосо- бу поиска решения (простые и переборные), по характеру целей (задачи оптими- зации, управления, обучения, информационного поиска), по функциональному назначению, а также по уровню достижения цели и уровню их решения, в т. ч. по уровню автоматизации этапов их решения. Задача становится разрешимой, если найдено правило, способ получения результата. В информатике такое правило называют алгоритмом. Решение задачи на ЭВМ состоит из нескольких этапов, среди которых основными являются следующие: 1. Постановка задачи: - сбор информации о задаче; - формулировка условия задачи; - определение конечных целей решения задачи; - определение формы выдачи результатов; - описание данных (их типов, диапазонов величин, структуры и т. п.). 2. Формализация (анализ и исследование задачи, модели, представление ее в виде уравнений, соотношений, ограничений и т.п.): - анализ существующих аналогов задачи; - анализ технических и программных средств; - разработка математической модели; - разработка структур данных. Понятие моделирования При решении задачи обычно исследуют не реальный объект, а его модель. Модель– искусственно созданный объект, обладающий всеми существен- ными признаками реального объекта, явления или процесса. Моделирование – это метод познания, состоящий в создании и исследова- нии моделей. Цели моделирования: 1) понять сущность изучаемого объекта; 2) научиться управлять объектом и определять наилучшие способы управле- ния; 3) прогнозировать прямые или косвенные последствия; 4) решать прикладные задачи. Математическая модель – это система математических соотношений (данных) – формул, уравнений, неравенств и т.д. и отношений между ними, опи- сывающих поведение объекта с некоторой степенью точности и отражающих су- щественные свойства моделируемого процесса (объекта или явления). 7 Порядок составления математической модели: - выделить реальный объект, на котором будет основываться математиче- ская модель, и из множества его свойств, закономерностей, внутренних связей, отдельных характеристик явления и параметров выделяем те, ко- торые являются существенными для решаемой задачи, и отбросить несу- щественные; - определить, что считать исходными данными и результатами; - подобрать математический объект с тем же числом подобных параметров, отражающий суть реального объекта; записать математические соотноше- ния, связывающие результаты с исходными данными. 3. Выбор метода решения. 4. Разработка алгоритма: - выбор метода проектирования алгоритма; - выбор формы записи алгоритма (блок-схемы, псевдокод и др.); - выбор тестов и метода тестирования; - проектирование алгоритма. 5. Программирование: - выбор языка программирования; - уточнение способов организации данных; - запись алгоритма на выбранном языке программирования. 6. Тестирование, отладка и исправление обнаруженных ошибок: - синтаксическая отладка; - отладка семантики и логической структуры; - тестовые расчёты и анализ результатов тестирования; - совершенствование программы. Отладка программы Отладка программы – это процесс поиска и устранения ошибок в про- грамме, производимый по результатам ее прогона на компьютере. В современных программных системах отладка осуществляется с использо- ванием специальных программных средств, называемых отладчиками. Эти сред- ства позволяют исследовать внутреннее поведение программы. Программа-отладчик обычно обеспечивает следующие возможности: пошаговое исполнение программы с остановкой после каждой команды (оператора); просмотр текущего значения любой переменной или нахождение зна- чения любого выражения, в том числе, с использованием стандартных функций; при необходимости можно установить новое значение перемен- ной; установку в программе "контрольных точек", т.е. точек, в которых про- грамма временно прекращает свое выполнение, так что можно оценить промежуточные результаты, и др. При отладке программ важно помнить следующее: - в начале процесса отладки надо использовать простые тестовые дан- ные; - возникающие затруднения следует четко разделять и устранять строго поочередно; - не нужно считать причиной ошибок машину, так как современные машины и трансляторы обладают чрезвычайно высокой надежностью. Тест и тестирование программы Тестирование – это испытание, проверка правильности работы программы в целом либо ее составных частей. При отладке происходит локализация и устранение синтаксических ошибок и явных ошибок кодирования, в процессе же тестирования проверяется работо- способность программы, не содержащей явных ошибок. Тестирование устанавли- вает факт наличия ошибок, а отладка выясняет причину неправильной работы программы. Как бы ни была тщательно отлажена программа, решающим этапом, уста- навливающим ее пригодность для работы, является контроль программы по ре- зультатам ее выполнения на системе тестов. Программу условно можно считать правильной, если её запуск для выбран- ной системы тестовых исходных данных во всех случаях дает правильные резуль- таты. Но, как справедливо указывал известный теоретик программирования Э. Дейкстра, тестирование может показать лишь наличие ошибок, но не их отсут- ствие. Нередки случаи, когда новые входные данные вызывают "отказ" или полу- чение неверных результатов работы программы, которая считалась полностью от- лаженной. Для реализации метода тестов должны быть изготовлены или заранее из- вестны эталонные результаты. Вычислять эталонные результаты нужно обяза- тельно до, а не после получения машинных результатов. В противном случае име- ется опасность невольной подгонки вычисляемых значений под желаемые, полу- ченные ранее на машине. 7. Анализ результатов решения задачи и уточнение математической моде- ли с повторным выполнением этапов 2 - 6 (при необходимости). 8. Сопровождение программы: это работы, связанные с обслуживанием про- грамм в процессе их эксплуатации: - доработка программы для решения конкретных задач; - составление документации к решённой задаче, к математической модели, к алгоритму, к программе, к набору тестов, к использованию программы. 1.2. Основы алгоритмизации Алгоритм – это метод (способ) решения задачи, записанный по определён- ным правилам, в виде конечной последовательности однозначных предписаний, исполнение которых позволяет с помощью конечного числа шагов получить ре- шение задачи, однозначно определяемое исходными данными из некоторого множества значений. Свойства алгоритма 1. Дискретность (прерывность, раздельность). Алгоритм должен представлять процесс решения задачи как последовательное выполнение конечного числа простых (или ранее определенных) законченных действий шагов. 2. Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять. 3. Определенность (точность, детерминированность). Каждое правило алгорит- ма должно быть четким и однозначным, содержать действия над известными данными. Каждое действие должно быть понятно исполнителю (для каждого алгоритма предполагается конкретный исполнитель). Замечание. Часто под свойством детерминированности алгоритма понимается од- новременное выполнение свойств точности и понятности. 4. Результативность (или конечность). Алгоритм должен приводить к решению задачи, получение определенного результата за конечное число шагов. 5. Правильность. Способность алгоритма обеспечить получение именно того результата, который требуется. Неправильность может объясняться неполно- той наших представлений о свойствах объекта или упущением в решении. Для доказательства правильности алгоритма задача часто делится на блоки и пра- вильность доказывается для каждого блока, хотя такая проверка не является полной. 6. Массовость. Алгоритм решения задачи pазpабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь ис- ходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма. 7. Универсальность. Алгоритм должен быть составлен так, чтобы им мог вос- пользоваться любой исполнитель для решения аналогичной задачи. (Например, правила сложения и умножения чисел годятся для любых чисел, а не для ка- ких-то конкретных.) 8. Эффективность. Выбор алгоритмы, который будет выполнен за минимальное время, с минимальными затратами ресурсов. Таким образом, исполнитель действует формально, т.е. отвлекается от содержа- ния поставленной задачи, а только строго выполняет некоторые правила, инст- рукции и вместе с тем получать нужный результат. Критерии качества алгоритма 1. Связанность. Определяется количеством промежуточных результатов. Чем выше количество промежуточных результатов, тем ниже связанность. 2. Объем алгоритма. Это количество операций или шагов, которые необхо- димо выполнить, а также сложность этих шагов. 3. Логическая сложность. Определяется количеством ветвлений и циклов. Порядок выполнения алгоритма 1. Действия в алгоритме выполняются в порядке их записи. 2. Нельзя менять местами никакие два действия алгоритма. 3. Нельзя не закончив одного действия переходить к следующему. Способы описания алгоритмов 1. Словесно-формульный. Описание алгоритма с помощью слов и формул на естественном языке. Словесный способ не имеет широкого распространения по следующим при- чинам: - такие описания строго не формализуемы; - страдают многословностью записей; - допускают неоднозначность толкования отдельных предписаний. «Он встретил ее на поле с цветами». Пример. Составить алгоритм начисления зарплаты согласно следующему правилу: если стаж работы сотрудника менее 5 лет, то зарплата130 руб., при ста- же работы от 5 до 15 лет – 180 руб., при стаже свыше15 лет зарплата повышается с каждым годом на10 руб. Словесно-формульное описание алгоритма решения задачи: 1. Ввести ST, перейти к п. 2. 2. Если ST<5, то ZP:.=l30, перейти к п. 4, иначе — перейти к п. 3. 3. Если ST<15, то ZP:=180, перейти к п.4, иначе ZP:=180+(ST-15)10, перейти к п. 4. 4. Вывести (отпечатать) значение ZP, перейти к п. 5. 5. Вычисления прекратить. 2. Табличный. Алгоритм представляется в форме таблицы и расчётных фор- мул (физика, химия и т. д.). 3. Структурограмма 4. Синтаксическая диаграмма (формулы Бэкуса-Наура) 5. Псевдокоды. Полуформализованные описания алгоритмов на условном ал- горитмическом языке, включающие в себя как элементы языка программи- рования, так и фразы естественного языка, общепринятые математические обозначения и др. Псевдокод занимает промежуточное место между естественным и формаль- ным языками. С одной стороны, он близок к обычному естественному языку, по- этому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. В псевдокоде не приняты строгие синтаксические правила для записи ко- манд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор ко- манд. Однако в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и ос- новных (базовых) конструкций. Примером псевдокода является школьный алгоритмический язык. Алгоритмический язык – это средство для записи алгоритмов в аналитиче- ском виде, промежуточном между записью алгоритма на естественном (чело- веческом) языке и записью на языке ЭВМ (языке программирования). Запись алгоритма решения задачи примера 1 на алгоритмическом языке: алг зарплата(цел. ST, вещ ZP) арг ST рез ZP нач если ST<5 то ZP:=150 иначе если ST<=15 то ZP:=180 иначе ZP:=180+(ST-15)*10 все все кон 6. Программный. Описание алгоритма с помощью языков программирования. 7. Графический. Алгоритм изображается в виде последовательности связан- ных между собой функциональных блоков, каждый из которых соответст- вует выполнению одного или нескольких действий.Такое графическое представление называется схемой алгоритма или блок-схемой. Блок-схема алгоритма представляет собой систему связанных геометрических фигур. Правила построения блок-схем 1. В блок-схеме каждому типу действий (вводу исходных данных, вычисле- нию значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представлен- ная в виде блочного символа. Для наглядности операции разного вида изобра- жаются в схеме различными геометрическими фигурами. 2. Блочные символы соединяются линиями переходов, определяющими оче- редность выполнения действий. Порядок выполнения действий указывается стрелками, соединяющими блоки. 3. В схеме блоки стараются размещать сверху вниз, в порядке их выполнения. 4. Все повороты соединительных линий выполняются под углом 90 градусов. В таблице приведены наиболее часто употребляемые символы. Название Обозначение и пример заполне- ния Выполняемая функция (пояснение) Начало/конец (вход/выход) Начало или конец программы, вход или выход в подпрограмму Блоки ввода/вывода Ввод-вывод данных Вывод данных на печатающее устройство Блок вычислений Арифметический блок определяет вычислительное действие или последовательность действий Логический блок Логический блок проверяет истинность или лож- ность условия и выбирает направления выполнения алгоритма в зависимости от условия. В блоке долж- ны быть указаны вопрос, условие или сравнение, которые он определяет. Предопределенный процесс Вычисления по стандартной или пользовательской подпрограмме Блок модификации Выполнение действий, изменяющих пункты алго- ритма, начало цикла. Внутри блока записывается параметр цикла, для ко- торого указываются его начальное значение, гра- ничное условие и шаг изменения значения парамет- ра для каждого повторения. Межстраничный со- единитель Указание связи между частями схемы, расположен- ной на разных страницах Общие правила построения схемы алгоритма задачи 1. Выявить исходные данные, результаты, назначить им имена. 2. Выбрать метод (порядок) решения задачи. 3. Разбить метод решения задачи на этапы (с учетом возможностей ЭВМ). 4. Изобразить каждый этап в виде соответствующего блока схемы алгоритма и указать стрелками порядок их выполнения. 5. В полученной схеме при любом варианте вычислений: а) предусмотреть выдачу результатов или сообщений об их отсутствии; б) обеспечить возможность после выполнения любой операции, так или иначе, перейти к блоку Останов (к выходу схемы). Эти правила и есть «Основные принципы алгоритмизации». Будем счи- тать, что знание и применение настоящих «принципов» обязательно при состав- лении алгоритма любой задачи. Типы алгоритмов - структурированные; - неструктурированные (т.е. с нарушением структуры – с операторами безус- ловного перехода); - вспомогательные (используемые в составе других алгоритмов). Виды алгоритмов - линейный алгоритм; - алгоритм ветвления; - циклический алгоритм; - алгоритм с подпрограммами; - смешанные (т.е. содержащие и циклы, и ветвление, и функции). - рекурсивный алгоритм обращается к самому себе, пока не выполнится оп- ределенное условие. Базовые алгоритмические конструкции – методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархи- ческой структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разра- ботана и дополнена Н. Виртом. Основывается на теореме о структуре. Согласно теореме о структуре (теорема Бёма – Якопини, 1966 г) логиче- ская структура любого алгоритма может быть представлена комбинацией трех ба- зовых структур: следование, ветвление, цикл. Характерной особенностью базовых структур является наличие в них одно- го входа и одного выхода. 1. Базовая структура следование (линейный алгоритм). Образуется из по- следовательности действий, следующих одно за другим: 2. Базовая структура ветвление (алгоритм ветвления) обеспечивает в зави- симости от результата проверки условия выбор одного из альтернативных путей работы алгоритма. Условие – вопрос, имеющий два варианта ответа: да или нет. Каждый из путей ведет к общему выходу, так что работа алгоритма будет про- должаться независимо от того, какой путь будет выбран. Запись ветвления вы- полняется в двух формах: полной и неполной. Структура ветвление существует в четырех основных вариантах: Неполная форма записи Полная форма записи 1. если- то 2. если-то- иначе 3. выбор 4. выбор- иначе Примеры команды если Пример: найти наименьшее из трех чисел. 1 вариант решения: 2 вариант решения: 3. Базовая структура цикл обеспечивает многократное выполнение неко- торой совокупности действий, которая называется телом цикла, над новыми дан- ными. Цикл типа «пока» Выполнение цикла «пока» начинается с проверки условия, по- этому такую разновидность циклов называют циклами с пре- дусловием. Переход к выполнению действия осуществляется только в том случае, если условие выполняется, в противном случае происходит выход из цикла. Тело цикла выполняется до тех пор, пока выполняется условие. Условие цикла необхо- димо подобрать так, чтобы действия, выполняемые в цикле, привели к нарушению его истинности, иначе произойдет за- цикливание. Зацикливание - бесконечное повторение выполняемых действий. Тело цикла Условие + _ ЦИКЛЫ с неизвестным числом повторов с предусловием (цикл «пока») с известным числом повторов (цикл «для») с постусловием (цикл «до») Цикл типа «до» Исполнение цикла начинается с выполнения действия. Таким об- разом, тело цикла будет реализовано хотя бы один раз. После этого происходит проверка условия. Поэтому цикл "до" называ- ют циклом с постусловием. Если условие выполняется, то про- исходит возврат к выполнению действий, иначе осуществляется выход из цикла. Для предотвращения зацикливания необходимо предусмотреть действия, приводящие к ложности условия. Цикл типа «для» Цикл с параметром, или цикл со счетчиком, или арифметический цикл - это цикл с заранее извест- ным числом повторов. Предписывает выполнять те- ло цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. х 0 – начальное значение параметра; h – шаг; х n – последнее значение параметра. Для создания циклов с параметром необходимо использовать правила: 1. Параметр цикла, его начальное и конечное значения и шаг должны быть од- ного типа. 2. Запрещено изменять в теле цикла начальное, текущее и конечное значения для параметра. 3. Запрещено входить в цикл, минуя блок модификации. 4. После выхода из цикла значение переменной параметра неопределенно и не может использоваться в дальнейших вычислениях. 5. Из цикла можно выйти, не закончив его, тогда переменная параметр сохра- няет свое последнее значение. 1.3. Теоретические основы программирования Программирование – это раздел информатики, изучающий методы и приемы составления программ для компьютеров. Кроме того, программирование – это подготовка задачи к решению ее на компьютере. Программа – последовательность действий, которые должен выполнить компьютер в строго указанной очерёдности для достижения конкретного резуль- тата. Языки программирования – это совокупность средств и правил представ- ления алгоритма в виде, приемлемом для компьютера. Системы программирования – это набор средств ввода, редактирования, трансляции и выполнения программ на ЭВМ. Транслятор – это устройство или комплекс программ, обеспечивающий перевод программы, написанной на символическом языке, в совокупность ма- шинных команд, либо передающие/преобразующие данные или другую програм- му. Тело цикла Условие – + – x = x 0 ..x n , h тело цикла Например, транслятор воспринимает операторы одного языка и вырабаты- вает соответствующие операторы другого языка. Компилятор – это транслятор, обеспечивающий перевод программы, напи- санной на алгоритмическом языке, в совокупность машинных команд без ее вы- полнения в компьютере. Компилятор оценивает исходный текст в соответствии с синтаксической конструкцией языка и переводит на машинный язык. Например, компилятор берет программу, написанную на языке C, и преоб- разует ее в программу на языке ассемблера. Интерпретатор – это транслятор, обеспечивающий перевод каждой конст- рукции алгоритмического языка в машинные команды и одновременное выполне- ние этой конструкции в компьютере. При исполнении программных операторов, интерпретатор должен сначала сканировать каждый оператор с целью прочтения его содержимого, а затем вы- полнить запрошенную операцию. 1.4. Правила записи в С++ арифметических выражений Арифметические выражения Выражение состоит из операторов и операндов. Операндами могут быть, в свою очередь, выражения или одни из его частных случаев – числа (константы) или переменные, операторы обозначают выполняемые над ними действия (+ сложение, - вычитание, * умножение, / деление (для целых операндов – целая часть от деления), % остаток от деления (только для целых ), …). Все основные операции языка С++ можно разбить на следующие группы: - арифметические операции; - логические операции; - операции отношения; - операции с битами информации; - операции со строками; - операции присваивания; - операция sizeof; - условная операция (?:). Примеры выражений: (a + 0.12)/6 x && || !z (t * sin(x)-1.05e4)/((2 * k + 2) * (2 * k + 3)) В выражение могут входить операнды различных типов, чего, строго говоря, не следует допускать. Если операнды имеют одинаковый тип, то результат операции будет иметь тот же тип. Если операнды различного типа, перед вычислениями выполняются преобразования типов по определенным правилам, обеспечивающим преобразование более коротких типов в более длинные для сохранения значимости и точности. Порядок вычисления выражений определяется рангом (приоритетом) входящих в него операций (табл. 3). Принятый в С++ ранг операций наиболее близок к математическому, также как и принятый порядок их вычисления. Так, умножение и деление (мультипликативные операции) старше сложения и вычитания (аддитивные операции). Унарные операции + и – старше бинарных, т.е., знак операнда вычисляется в первую очередь. Операции типа присваивания младше прочих, что позволяет выполнить их только после того, как значение выражения вычислено полностью. Операции отношения младше арифметических операций, что позволяет использовать естественную запись логических выражений, например, x>0 && y>0 . Здесь в первую очередь вычисляются значения отношений, которые затем являются операндами конъюнкции. Таблица 1 – Порядок вычисления выражений Группа Тип действий Операции или элементы 1 Вычисления в круглых скобках ( ) 2 Вычисления значений функции Функции 3 Унарные операции ++, --, , !, унарные - и +, &, * (разадресация), … 4 Операции типа умножения *, /, % 5 Операции типа сложения +, – 6 Операции отношения <, <=, >, >=, ==, != Арифметические выражения строятся из операндов, арифметических операций и круглых скобок. Круглые скобки используются для заключения в них части выражения, значения которой необходимо выполнить в первую очередь. В выражении может быть любое количество круглых скобок, причем количество открывающих круглых скобок должно быть равно количеству закрывающих. Части выражений, заключенные в круглые скобки, должны быть либо не пересекающимися, либо вложенными друг в друга. Арифметические выражения записываются по следующим правилам: Запись ведётся в строчку. Нельзя опускать знак умножения между сомножителями. Для обозначения переменных используются буквы латинского алфавита. Операции выполняются в соответствии с приоритетами: сначала вычисление функций, затем умножение и деление , потом сложение и вычитание. Если в одном выражении записано несколько операций одинакового приори- тета, унарные операции, условная операция и операции присваивания выпол- няются справа налево, остальные – слева направо. Например, a = b = c означа- ет a = (b = c), а a + b + с означает (a + b) + c. Для изменения порядка действий используются круглые скобки. При использовании стандартных функций аргумент обязательно заключается в круглые скобки. В языке С++ предусмотрены базовые математические операции (см. прил. 2). Примеры записи выражений: Математическое выражение Запись на C++ 1. x x cos 3 10 1. 10 * x + 3 * sqrtf(cos(x)) 2. 1 1 2 sin 2 x x 2. (sin(2*x) - 1) / (pow(x, 2) - 1) 3. ctgx x 2 3. abs(x) + 2 * cos(x) / sin(x) |