Задача посчитать сумму первых n натуральных чисел.
Тема 4. Алгоритмы
Понятие алгоритма
Любая программа является реализацией некоторого алгоритма. Понятие алгоритма является одними из фундаментальных понятий информатики, появившимся задолго до появления ЭВМ. В древнем мире алгоритмом называлось правило выполнения арифметических действий. До 50-х годов 20 века под алгоритмом понималась совокупность математических операций, выполняемых в определенном порядке. Дадим интуитивное понятие алгоритма. Алгоритм - понятное и точное сформулированное на определенном языке предписание исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи. Алгоритм формируется в расчете на конкретного исполнителя (человека или ЭВМ). Каждый алгоритм имеет некоторое множество входных и выходных величин. Причем размерность входного множества может быть равна нулю.
Свойства алгоритма:
- Массовость. Для алгоритма можно брать различные наборы входных данных, то есть в общем случае можно применять один и тот же алгоритм для решения целого класса задач. Хотя существуют алгоритмы, применяемые только к единственному набору входных данных (без входа).
- Дискретность - алгоритм может быть представлен в качестве последовательности шагов, поэтому его исполнение расчленяется на выполнение этих отдельных шагов.
- Конечность - выполнение алгоритма заканчивается после выполнения конечного числа шагов.
|
|
|
- Определенность - алгоритм рассчитан на чисто механическое исполнение, то есть действия, которые необходимо произвести должны быть строго и недвусмысленно определены в каждом возможном случае. Это означает, что один алгоритм будут выполнять разные исполнители, то они прейдут к одному результату.
- Эффективность- алгоритм должен быть выполнен не просто за конечное, а за разумное конечное время.
Существуют более формальные описания алгоритма, предложенные Постом, Тьюрингом, Марковым. На практике они друг другу эквивалентны друг другу и этому интуитивному понятию.
Способы описания алгоритма
1. Словесно- формульный – алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий;
2. Структурный или блок-схемный. При блок-схемном описании алгоритм изображается геометрическими фигурами (блоками), связанными линиями со стрелками (отражающими последовательность действий). В блоках записывается описания действий. Процесс, что есть выполнение операции или группы операций, в результате которых меняется значение, форма представления или расположение данных обозначается на блок-схеме алгоритма прямоугольником. Ввод - вывод данных, то есть преобразование данных в форму пригодную для обработки или отображения результатов обработки изображается параллелограммом. Решение, то есть выбор направления алгоритма в зависимости от некоторых переменных условий изображается ромбом. Пункт-останов, то есть начало конец, прерывание процесса обработки обозначаются овалом.
|
|
|
С помощью языка программирования.
Тема 5. Управляющие структуры и основные конструкции языков программирования
Размещенная в памяти компьютера программа в момент выполнения занимает определенную область памяти. В каждый момент времени состояние программы характеризуется двумя типами сведений:
- состоянием некоторых ячеек памяти, понимаемых нами как переменные;
- активной точкой программы, то есть той командой программы, которая выполняется данный момент.
Следовательно, можно выделить и два основных класса действий, которые может выполнять вычислительная система:
- действия, выделяющие область памяти под переменные программы (описания).
- действия, меняющие точку выполнения программы (операторы, инструкции, конструкции).
Различные совокупности действий второго класса также называют управляющими структурами.
|
|
|
В теории программирования доказано, что программу для решения задачи любой сложности можно составить их трех структур, называемых следованием (цепочкой), ветвлением и циклом. Этот результат установлен Бойном и Якопини в 1966 г. путем доказательства того, что любую программу можно преобразовать в эквивалентную, состоящую только из этих структур и их комбинаций. Каждая из этих управляющих структур реализована в языке программирования набором соответствующих конструкций.
Структура следования (естественная фундаментальная структура) реализует линейный вычислительный процесс, то есть процесс, в котором действия выполняются последовательно, в порядке их записи. Каждое действие является самостоятельным, независимым от каких-либо условий. В языках программирования цепочки реализуются так называемым составной конструкцией следующим образом.
{
оператор 1;
оператор 2;
….
оператор n;
}
На блок-схеме блоки, отображающие эти операции, располагаются в линейной последовательности.
 |
Каждый оператор будет выполняться только тогда, когда закончит выполняться предыдущий. Оператор ; - называют оператором следования. Составные операторы заключены в инструктивные скобки. В языке С++ инструктивные скобки записываются как { }. В Паскале –begin end. Составные операторы также называют блоком кода, инструктивным блоком, блоком. Тело любой функции в С++ является блоком.
|
|
|
Пример структуры следования (цепочки)
{
int a=10,b,c;
scanf(“%d”,&b);
c=a+b;
printf(”a+b =%d”,c);
}
Структура ветвления реализует ветвящийся вычислительный процесс, то есть процесс, для реализации которого предусмотрено несколько направлений (ветвей). Ветвление в программе – это выбор одной из нескольких последовательностей операторов при выполнении программы. Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным данным или конечным результатам. Хотя на схеме алгоритма должны быть показаны все возможные направления вычислений в зависимости от выполнения определенного условия (или условий), при однократном прохождении программы процесс реализуется только по одной ветви, а остальные исключаются. Любая ветвь, по которой осуществляется вычисления, должна приводить к завершению вычислительного процесса.
В языках программирования структура ветвления реализуется условными и селективными констркуциями. Условные конструкции в общем случае имеют форму
если выражение то действие1 иначе действие2;
и следующей смысл: если выражение верно то выполняется действие1, иначе выполняется действие2.
Кроме того, используется и усеченная форма условной конструкции
если выражение то действие1;
На блок-схеме ветвление и усеченное ветвление изображаются следующим образом:
 |
В С++ синтаксис условной конструкции
if (выражение) опрератор1; else оператор2;
if (выражение) опрератор1;
Выражение должно быть скалярным и иметь арифметический тип или тип указателя. В операторе if оператор1 выполняется в том случае, если выражение ненулевое, иначе выполняется оператор2 или не выполняются никакие действия, если оператор2 не задан, то есть отсутствует else. В частности, если a целое, то if (a) эквивалентно if (a!= 0).
Оператор1 и оператор2 могут представлять собой один оператор или блок операторов, но не могут быть описаниями.
if (a==b) printf(”Введенные значения равны”); else printf(”Введенные значения не равны”);
В соответствии неписаными правилами хорошего стиля программирования в условных инструкциях логическое выражение необходимо составлять таким образом, чтобы чаще всего оно было истинным.
scanf(“%d%d”,&a, &b);
if (a) {c=b/a; printf(“%d”,c);
else printf (”Ошибка ввода”);
Часто используются в условиях логические операции &&, ||, !. Операции && и || не будут вычислять второй аргумент, если это не нужно. Например, if (p && r) … вначале проверяет, является ли p не нулем, и только, если это так, то проверяет r.
Еслинекоторое действие выполняется при выполнении двух условий желательно записывать их в виде одного выражения.
Можно записать
if (a>0)
if (b>0) c=a*b;
но лучше if (a>0 && b>0) c=a*b;
Селективные инструкции используются для реализации мультиветвления и в общем случае имеют вид:
если (выражение)
{имеет значение1 то действие1,
имеет значение2 то действие2
….
имеет значениеn то действиеn
иначе действиеN+1
}
 |
На блок-схеме мультиветление изображается следующим образом:
В С++ существует конструкция мультиветвления (переключатель). Синтаксис переключателя:
switch (переключающее_выражение)
{case константное_выражение1: оператор1;
case константное_выражение2: оператор2;
. . .
case константное_выражениеn: операторn;
default:оператор;
}
Если не предусмотрены переходы и выходы из переключателя, то в нем последовательно выполняются все операторы, начиная с той метки, на которую передано управление. Для выхода из переключателя обычно используют оператор break.
Примеры смотри в пособии.
Структура цикла реализует циклический вычислительный процесс, то есть процесс, включающий в себя повторяемую последовательность действий - цикл. В организации цикла можно выделить следующие этапы:
- подготовка (инициализация параметров цикла);
- выполнение вычислений цикла (тело цикла);
- модификация параметров (которая фактически является частью тела цикла);
- проверка условия окончания (или условия продолжения) цикла.
Порядок выполнения этих этапов может и меняться. Если условие проверяется до выполнения тела цикл, то говорят о цикле с предусловием. Если – после, то о цикле с постусловием. Главное отличие- цикл с постусловием обязательно выполнится хотя бы один раз.
На блок схеме циклы изображаются следующим образом
Цикл называется детерминированным, если число повторений цикла заранее определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значения параметров, участвующих в вычислениях.
В С++ существует три конструкции цикла.
· цикл с предусловием
while (выражение_условие)
тело_цикла;
· цикл с постусловием
do
тело_цикла
while (выражение_условие)
· цикл for
for (инициализация_цикла; выражение_условие; список_выражений)
тело_цикла
Тело_цикла не может быть описанием, это либо один (может быть и пустой) оператор, который всегда завершается точкой с запятой, либо блок операторов, заключенных в скобки {}. Выражение_условие – это выражение, определяющее условие продолжения итераций. Операторы тела цикла выполняются, пока условие истинно (не равно нулю). Инициализация_цикла в цикле for - это последовательность определений и выражений, разделяемых запятыми. Даже если она пустая, точка с запятой должна присутствовать. Чаще всего здесь устанавливается начальные значения счетчиков и параметров цикла. Выражения из списка_выражений выполняются после выполнения операторов тела цикла и до следующей проверки выражения_условия.
Конструкцию for чаще применяют для организации детерминированных циклов. А конструкции do и while чаще применяют для итерационных циклов. Хотя такое функциональное разделение довольно условно.
Два примера использования конструкции цикла для построения индуктивной последовательности, то есть последовательности, где каждый следующий член получается путем вычисления определенной формулы над предыдущими челнами.
Примером индуктивной последовательности являются числа Фибоначчи, которые вычисляются по следующей формуле:
A1=A2=1, An=An-1+An-2, где n=3,4…
То есть последовательность чисел Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, ….
Пример детерминированного цикла
// Вычисление k-го числа Фибоначчи
# include <iostream.h>
# include <conio.h>
void main ()
{
int k,a1=1,a2=1,a3;
printf ("Enter k>2 ");
scanf(“%d”,&k);
for (int i=1; i<=(k-2);i++)
{
a3=a1+a2;
a1=a2;
a2=a3;
}
printf ("\n%d",a3);
getch();
}
Итерационный цикл
// Определить сумма скольки чисел Фибоначчи не превосходит m(m>1)
# include <iostream.h>
# include <conio.h>
void main ()
{
int k=1,a1=1,a2=1,a3,m;
int sum=a1+a3;
printf("Enter m ");
scanf(“%d”, &m);
while (sum<m)
{
k++;
a3=a1+a2;
sum+=a3;
a1=a2;
a2=a3;
}
printf("\nk=%d",k);
getch();
}
Основная проблема при организации циклов – возможность зацикливания – бесконечное повторение тела цикла.
Зацикливание может возникнуть по двум основным причинам:
1. Неверно задано условие цикла
2. Неверно в теле цикла меняются параметры, участвующие в условии цикла.
Например,
Задача посчитать сумму первых n натуральных чисел.
int i=1,sum=0,n;
while (i>n) {sum+=i; i++;}
printf (“%d”,sum);
Вероятнее всего цикл будет бесконечным, так как n – не инициализировано, и может принимать значение 0. Правильное условие (i<n), причем надо инициализировать n;
Задача посчитать сумму целых числе в диапозаоне [ n, m] ( n< m)
int n,m;
scanf(“%d%d”, &n, &m);
int i=n, sum=0;
while (i<=m) {sum+=i; i--;}
printf (“%d”,sum);
Цикл будет бесконечным, так как i все время уменьшается, а следовательно условие всегда будет верным. Правильно i++;
Рассмотрим еще примеры циклов.
Дата добавления: 2021-01-20; просмотров: 68; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!