Лекция 1. Основы алгоритмизации и программирования на Си (1153708), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

Слово "алгоритм" произошло от латинского перевода имени выдающегося ученого-энциклопедиста Мухаммеда Аль Хорезми7 (780850), которые впервые описал правила (т. е. алгоритмы) десятичнойарифметики.7Аль Хорезми означает "из Хорезма".22Строгое определение алгоритма дается в теории алгоритмов.Здесь лишь стоит отметить, что алгоритм должен обладать следующими свойствами: Универсальность (массовость) - это возможность решения с помощью алгоритма класса задач (не одной задачи). Класс задачопределяется областью возможных значений исходных данных. Конечность (результативность) - обязательное получение результата за конечное число действий. Определенность означает, что при многократном выполненииалгоритма с одними и теми же исходными данными мы получимодинаковые результаты; другими словами, определенность - этоотсутствие случайности.Известны различные способы записи алгоритма. До сих пор широко применяется словесное описание алгоритма "по шагам".

Программа в кодах ЭВМ или на любом алгоритмическом языке - другойпример записи алгоритма. Блок-схемы представляют собой еще одинспособ записи алгоритма, более точный, чем словесное описание, именее формальный, чем программа на алгоритмическом языке. Блоксхемы не зависят от алгоритмического языка и компьютера, с помощью которых будет выполняться алгоритм, и очень легко воспринимаются.Разработчик программы перед записью ее на алгоритмическомязыке обычно обдумывает ее "по шагам".

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

Если стрелка идет вниз, то ее можноне рисовать (оставить линию без стрелки). В соответствии с принци-23пом программного функционирования ЭВМ8 необходимо иметь следующие виды блоков.1. Вычислительный блок. Необходим для изображения любых вычислений (арифметических, логических и др.). Внутри блока записывается действие. Это либо оператор присваивания, либо обобщенноедействие (например, "вычисление среднего").

Изображается прямоугольником (см. рис.2, а). Имеет один вход и один выход2. Блок ввода или вывода. Изображается как параллелограмм (см.рис.2,б). Внутри записывается пояснение, например, "ввод а,b" или"вывод суммы". Имеет один вход и один выход, также как и вычислительный блок.3. Условный блок. Изображается ромбом (рис.2,в), внутри которогозаписывается некоторое условие (соотношение или более сложноелогическое условие). Имеет один вход и два выхода.

Один из выходов (его обозначают "да", или "истина", или "+") соответствует путиалгоритма, где условие выполняется. Другой выход ("нет", "ложь","-") соответствует невыполнению условия.4. Блок начала алгоритма (рис 2, г). Имеет только выход, входа нет.5. Блок конца алгоритма (рис. 2, д). Имеет только вход.а)б)данетусловиеначалоконецг)в)д)Рис. 2.

Основные блоки8Предполагается, что с этим принципом читатели знакомы,например, из курса "Информатика".241.4.4. Базовые структуры алгоритмов и их кодирование на Си.Современная технология программирования предполагает, что алгоритм долженстроиться из базовых структур. Таких струкОператор 1тур три: следование, развилка, цикл.1. СледованиеЭта структура, изображенная на рис. 3,Оператор 2предполагает последовательное выполнениевходящих в нее инструкций, которых можетдве и больше. Последовательно выполняеРис. 3. Следованиемые операторы в программе на Си записываются друг за другом и разделяются точкой с запятой.2. Разветвление (развилка)Разветвление, блок-схема которого приведена на рис. 4, применяется в том случае, когда выполнение алгоритма должно развиваться по двум альтернативным ветвям.НетУсловие?ДаОператор 1Оператор 2Рис.

4. РазветвлениеВетви развилки обязательно должны соединяться в одной точке,т. е. дальнейшее выполнение алгоритма должно происходить по одному пути; кроме того, ветви алгоритма не должны пересекаться, т. е.не должны иметь общих блоков.Разветвление предполагает проверку некоторого условия. Еслина момент проверки условие истинно, то будет выполнен оператор 1,25иначе оператор 2. В языке Си ветвление кодируется с помощьюусловного оператора:if (условие)оператор 1;elseоператор 2;В принципе можно было бы записать оператор в одну строку илирасположить его по строкам каким-либо другим способом, но практикапоказывает, что в приведенном виде фрагмент программы легче читается, и такая запись считается хорошим стилем программирования.Возможна ситуация, когда ветвь “Нет ” не содержит операторов(т. е.

либо выполняются операторы ветви “Да”, либо сразу переходим кточке соединения ветвей блок-схемы). В этом случае в условном операторе Си слово else и оператор 2 отсутствуют.Если операторы 1 или 2 состоят из нескольких операторов (являются составными), то входящие в них операторы окаймляются фигурными скобками:if (условие){оператор 1;оператор 2;…оператор N;}else{оператор 1;оператор 2;…оператор M;}Таким образом, фигурные скобки позволяют объединить несколько операторов в один составной.263. ЦиклЦиклические структуры (или циклы) служат для организации повторения некоторых операторов.

Две базовые циклические структурыприведены на рис. 5. Цикл, кроме стрелок идущих вниз обязательносодержит стрелки, указывающие вверх, – иначе не будет повторения.Следовательно, блок-схема циклического алгоритма обязательно содержит замкнутый путь (петлю). Цикл состоит из тела цикла, т. е.Цикл-покаУсловие?Цикл-доНетТело циклаДа.НетУсловие?Тело циклаДаРис.5. Базовые циклические структурыгруппы подлежащих повторению операторов, и условного оператора,осуществляющего анализ на продолжение цикла.

При отсутствии такого анализа возникает зацикливание (бесконечное повторение телацикла). Зацикливание может также возникнуть из-за неправильногоформулирования условия продолжения цикла. В зависимости от порядка выполнения тела цикла и анализа на продолжение цикла различают два вида базовых циклических структур: цикл с предусловиемили цикл-пока (сначала анализ на продолжение цикла, а затем телоцикла) и цикл с постусловием или цикл-до (сначала выполнение тела,а затем анализ).27На Си циклы кодируются следующим образом:цикл-покаwhile (условие)тело цикла;цикл-доDoтело цикла;while (условие)Тело цикла должно представлять собой один оператор – простойили составной.Замечания1.

Каждая из трех рассмотренных базовых структур имеет один вход иодин выход. Это очень важно, так как любой прямоугольник на рисунках 3 – 5, может быть базовой структурой. Значит, цикл может включать в свой состав базовые структуры: следование, разветвление,цикл. Это утверждение также относится и к двум другим базовымструктурам – следование и разветвление.2. В теории алгоритмов доказано, что для построения любого алгоритма достаточно иметь три базовых структуры: следование, ветвление, цикл.

Это положение называется принципом Дейкстры. Причембезразлично, какую циклическую структуру – доили пока – выбрать в каi = нач_значчестве базовой. Практикапрограммирования, однако, сложилась так, чторавноправно используютНетН обе эти структуры.сяi<=кон_значетКроме того, в программировании широкоДаиспользуется еще однабазовая структура (избыТело циклаточная), которая являетсячастным случаем циклаi =i+шагпока и называется параметрическим цикломРис.6.

Блок-схема параметрического(см. рис.6). Этот циклциклауправляется переменной28(так называемым параметром, на блок-схеме для него выбрано имя i),которая меняется от начального значения до конечного с заданнымшагом.Для кодирования параметрического цикла в Си используетсяоператор:for(i=нач_знач;i<=кон_знач; i=i+шаг)тело цикла;Как и для предыдущих операторов, тело цикла – один оператор,простой или составной.

Заметим, что возможности оператора for в Сине ограничиваются параметрическим циклом, но их рассмотрение выходит за рамки этого пособия.1.4.5. Примеры разработки программПример 1. Программа решения квадратного уравненияax2 + bx + c=0Исходные данные: a, b, c - коэффициенты уравнения, вещественные переменные.Выходные данные: х1, х2 - значения двух корней уравнения, еслидискриминант неотрицателен, и значения вещественной и мнимойчастей комплексно-сопряженных корней, если дискриминант отрицателен; это также вещественные переменные.Промежуточные данные: d - дискриминант уравнения, вещественная переменная.Блок-схема алгоритма представлена на рис.7. Алгоритм долженразделяться на две ветви в зависимости от знака дискриминанта, поэтому он использует базовую структуру ветвление.

Ввод исходныхданных,вычисление и анализ d соединены последовательно (используется базовая структура следование).По этой блок-схеме написана программа:#include <stdio.h>#include <math.h>#include <conio.h>void main(){float a, b, c, d, x1, x2;29printf("введите коэффициенты a,b,c уравнения\n");scanf("%f%f%f", &a, &b, &c);d=b*b-4*a*c;if (d>=0){x1=-b/2/a+sqrt(d); x2=-b/2/a-sqrt(d);printf("уравнение имеeт два действительных корня\n x1=%f x2=%f\n",x1,x2);} else{x1=-b/2/a; x2=sqrt(-d)/2/a;printf("уpавнение имеет комплексно-сопpяженные коpни\n");printf("действ. часть =%f , мнимая часть =%f\n", x1,x2);}_getch();}Замечания. 1.

Характеристики

Список файлов лекций