1й курс / Konspekt_lektsiy_Informatika_3

ÓЕфименко К.Н.

Тема №4. АЛГОРИТМИЗАЦИЯ И С++

Решение любой задачи на ЭВМ включает следующие этапы:

·разработка алгоритма решения задачи;

·составление программы на языке программирования;

·ввод и отладка программы;

·тестирование программы и анализ результатов.

4.1. Основы алгоритмизации

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

Способы представления алгоритмов:

·словесно-формульный – алгоритм записывается в виде текста с формулами по пунктам, которые определяют последовательность действий;

·графический – алгоритм изображается специальными геометрическими фигурами

(блоками), связанными направляющими стрелками.

4.1.1. Изображение алгоритма в виде блок-схемы

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

Наиболее часто используемые блоки:

Наименование

Обозначение

блока

Начало/конец алгоритма

Ввод/вывод

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

1

ÓЕфименко К.Н.

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

В общем случае любой алгоритм может состоять из трех частей:

–ввод исходных данных,

–вычисление требуемых величин,

–вывод полученных результатов.

Существует три основных типовых структуры алгоритма:

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

2.Разветвляющийся вычислительный процесс.

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

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

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

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

Влинейном алгоритме существует только одинпуть, по которому можно пройти из

Вывод S, 2×r

КОНЕЦ

4.2.1. Составной оператор

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

{

оператор_1;

...

оператор_n

}

Компилятор воспринимает составной оператор как один оператор.

4.3. Разветвляющийся вычислительный процесс

Разветвляющийся вычислительный процесс позволяет выбрать один из нескольких вари-

антов решения поставленной задачи в зависимости от выполнения некоторых условий. Таким

2

ÓЕфименко К.Н.

образом, существует несколько различных путей, по которым можно пройти из блока «Начало»

ского неравенства). Если результат проверки условия «Истина», т.е. условие выполняется, то происходит переход к выполнению блоков, стоящих по ветви «+». В противном случае, т.е. когда проверяемое условие не выполняется, происходит переход к выполнению блоков, стоящих по ветви «–».

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

4.3.1. Условный оператор

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

Условный оператор С++, соответствующий приведенной блок-схеме, имеет вид:

if (выражение) оператор_1; else оператор_2;

Принцип работы оператора if:

Вычисляется условие, заданное в виде выражения. Если оно имеет значение true (или не равно нулю), выполняется оператор_1, в противном случае (выражение имеет значение false, т.е. равно нулю) – оператор_2.

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

Оператор Оператор

В этом случае условный оператор будет иметь вид:

if (выражение) оператор;

Здесь оператор либо выполняется, либо пропускается, в зависимости от значениявыраже-

ния.

Если в какой-либо ветви условного процесса требуется выполнить несколько операто-

3

Условные операторы могут быть вложенными друг в друга. Н пример, следующий

может быть реализован таким фрагментом программы на С++: if (условие1)

{

оператор1;

if (условие2) оператор2;

}

else

if (условие3)

{

оператор3; оператор4

}

else оператор5;

Распространенные ошибки при записи условных операторов:

1. Использование вместо проверки равенства (==) оператора присваивания (=).

Например,

if (a=1) b=0; //НЕ ВЕРНО

Синтаксической ошибки нет. Операция присваивания a=1 формирует результат, который и оценивается на равенство или неравенство нулю. В данном примере присваиваниеb=0 будет выполнено независимо от значения переменной a.

if (a==1) b=0; //ВЕРНО

2. Неверная запись проверки на принадлежность диапазону. Например, if (0<x<1)… //НЕ ВЕРНО

if (0<x && x<1)… //ВЕРНО

4

ÓЕфименко К.Н.

Пример 4.2 (лабораторная работа 3.1). Дано вещественное числоx. Для функции, график которой приведен ниже, вычислить y=f(x).

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

1

2

3

4

1-я часть представляет собой прямую с диапазоном значений аргументаx равным ]-¥; -2] или x£-2.

2-я часть представляет собой экспоненту с диапазоном значений аргумента x равным ]-2; 2[ или -2<x<2.

3-я часть представляет собой прямую с диапазоном значений аргументаx равным [2; 4] или 2£x£4.

4-я часть представляет собой прямую с диапазоном значений аргументаx равным ]4; +¥[ или x>4.

Для получения уравнения прямой, проходящей через две точки с координатами (x1, y1) и (x2, y2) можно воспользоваться следующим соотношением:

5

ÓЕфименко К.Н.

x - x1 = y - y1 x2 - x1 y2 - y1

Таким образом, будет получена аналитическая запись заданной функции:

float x,y;

cout<<"Input x="; cin>>x; if (x<=-2) y=-1.5*x-2;

else if (x>-2 && x<2) y=exp(0.5*x); else if (x>=2 && x<=4) y=-2.5*x+7;

else y=-3;

cout<<"\n For x="<<x<<"\t y="<<y<<endl; system("PAUSE");

}

6

ÓЕфименко К.Н.

4.3.2. Проверка ограничений

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

– операция деления (на 0 делить нельзя), 1/x ® x ¹ 0;

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

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

îx +1

Выбор формулы для вычисления у выполняется с помощью условий отбора, которые являются взаимно исключаемыми. Если при проверке любые два условия будут Ложь, то третье проверять не надо, оно будет автоматически Истина. Таким образом, если заданы 3 условия отбора, то для их проверки достаточно использовать 2 вложенных блока проверки условий.

Проанализируем имеющиеся в формулах ограничения. Вторая формула для вычисления y имеет ограничение– подкоренное выражение должно быть ≥0. Однако, проверять его не надо, так как при любом значениих, попадающем в интервал[2; 4[, подкоренное выражение всегда >0. Третья формула для вычисления y также имеет ограничение – возможно деление на 0, поэтому необходимо проверить знаменатель дроби на неравенство нулю.

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

Вывод y

К

КОНЕЦ

7

ÓЕфименко К.Н.

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

Для реализации в программе переходаК потребуется оператор безусловного перехода goto, имеющий следующий формат:

goto имя_метки;

…

имя_метки: оператор;

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

5. Текст программы на С++:

#include <iostream> #include <math.h> using namespace std;

int main(int argc, char *argv[])

{

float x,y; cout<<"Input x="; cin>>x;

if (x>=4) y=x*x-4*x; else if (x<2)

{

if (x+1!=0) y=3*x/(x+1); else

{

cout<<"No result \n"; goto m1;

}

}

else y=sqrt(x-1.5); cout<<"y="<<y<<endl;

m1: system("PAUSE"); return EXIT_SUCCESS;

}

Пример 4.4 (лабораторная работа 3.2). Для произвольного значений исходных данных вычислить соответствующие значенияx (по одной из двух формул) и y (по одной из трех формул) в зависимости от заданных условий отбора:

î

Проанализируем имеющиеся в формулах ограничения.

Первая формула для вычисления y имеет ограничение – подкоренное выражение должно быть ≥ 0 (a2+1≥ 0). Однако, проверять его не надо, так как при любом значении a подкоренное выражение всегда >0.

Вторая формула для вычисления y не имеет ограничений.

Третья формула для вычисления y имеет ограничение – подкоренное выражение должно быть ≥ 0 (x–a ≥ 0) и проверять его надо.

8

ÓЕфименко К.Н.

Первая формула для вычисления x имеет ограничение – выражение под знаком логарифма должно быть > 0 (ab>0). Однако, проверять его не надо, так как эта формула для вычисления х используется только если ab > 1.

Вторая формула для вычисления x имеет ограничение – возможно деление на 0, поэтому необходимо проверить знаменатель дроби на неравенство нулю (a¹0).

A

КОНЕЦ

9

ÓЕфименко К.Н.

5. Программа решения задачи на С++, реализованная с помощью компилятора Dev-C++.

//Директивы процессора

#include <cstdlib> #include <iostream> #include <math.h> #include <stdio.h> using namespace std;

//Начало главной функции программы int main(int argc, char *argv[])

{//Описание константы p и переменных const float Pi=3.14159;

float a,b,x,y;

//Ввод исходных данных a и b printf("Input a="); scanf("%f",&a); printf("Input b="); scanf("%f",&b);

//Вычисление значения x if (a*b>1) x=log(a*b)-1; else

if (a!=0) x=(b-1)/a; else

{//Вывод сообщения о невыполнении ограничения г) printf("Error!\n"); goto m1; }

//Вывод результата х printf("x=%6.2f \n",x);

//Вычисление значения y

if (x<1.5) y=sqrt(a*a+1)+sin(Pi/2*x); else

if ((x>=1.5)&&(x<=3.5)) y=fabs(a+x); else

if (x-a>=0) x=sqrt(x-a); else

{ //Вывод сообщения о невыполнении ограничения б) printf("Error!\n"); goto m1; }

//Вывод результата у printf("y=%6.2f \n",y); m1:

system("PAUSE"); return EXIT_SUCCESS;

}

Результаты работы программы:

10