Алгоритмом называется точная инструкция исполнителю в понятной для него форме, определяющая процесс достижения поставленной цели на основе имеющихся исходных данных за конечное число шагов.
Основными свойствами алгоритмов являются:
1. Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.
2. Дискретность — процесс решения задачи по алгоритму разбит на отдельные действия.
3. Однозначность — правила и порядок выполнения действий алгоритма имеют единственное толкование.
4. Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.
5. Результативность — по завершении выполнения алгоритма обязательно получается конечный результат.
6. Выполнимость — результата алгоритма достигается за конечное число шагов.
Алгоритм считается правильным, если его выполнение дает правильный результат. Соответственно алгоритм содержит ошибки, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершится вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.
Алгоритм и программа приближенного вычисления дифференциальных уравнений
Выделяют три крупных класса алгоритмов:
· вычислительные алгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
· информационные алгоритмы, представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
· управляющие алгоритмы, генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
Есть А и N- целые числа(параметры задачи)
1.Присвоить I значение 0
2.Присвоить Р значение 0
3.Проверка. Если А или N=0, то перейти к шагу 7
4.Присвоить Р значение Р+А
5.Присвоить значение I+1
6.Если I меньше N, то перейти к шагу 4
7.Присвоить М значение Р
Языки программирования.
Язык программирования – система обозначений для описания программ.
Обычный разговорный язык состоит из четырех основных элементов: символов, слов, словосочетаний и предложений. Алгоритмический язык содержит подобные элементы, только слова называют элементарными конструкциями, словосочетания — выражениями, предложения — операторами. Алгоритмический язык (как и любой другой язык), образуют три его составляющие: алфавит, синтаксис и семантика.
Алфавит – фиксированный для данного языка набор символов (букв, цифр, специальных знаков и т.д.), которые могут быть использованы при написании программы.
Синтаксис — правила построения из символов алфавита специальных конструкций, с помощью которых составляется алгоритм.
Семантика — система правил толкования конструкций языка. Таким образом, программа составляется с помощью соединения символов алфавита в соответствии с синтаксическими правилами и с учетом правил семантики.
Алгоритм и программа приближенного вычисления определенного интеграла
Существуют различные классификации языков программирования. Все языки программирования делят на языки низкого, высокого и сверхвысокого уровня.
В группу языков низкого уровня входят машинные языки и языки символического кодирования: (Автокод, Ассемблер). Операторы этого языка – это те же машинные команды, но записанные мнемоническими кодами, а в качестве операндов используются не конкретные адреса, а символические имена. Все языки низкого уровня ориентированы на определенный тип компьютера, т. е. являются машинно-зависимыми. Машинно-ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.).
Следующую, существенно более многочисленную группу составляют языки программирования высокого уровня. Это Фортран, Алгол, Кобол, Паскаль, Бейсик, Си, Пролог и т.д. Эти языки машинно-независимы, т.к. они ориентированы не на систему команд той или иной ЭВМ, а на систему операндов, характерных для записи определенного класса алгоритмов. Однако программы, написанные на языках высокого уровня, занимают больше памяти и медленнее выполняются, чем программы на машинных языках.
К языкам сверхвысокого уровня можно отнести лишь Алгол-68 и APL. Повышение уровня этих языков произошло за счет введения сверхмощных операций и операторов.
Разветвляющиеся алгоритмы. Алгоритм вычисления арксинуса — агсsin х.
В таких алгоритмах делается выбор: выполнять или не выполнять какую-нибудь группу команд в зависимости от условия, т.е. выбирается один из нескольких возможных путей (вариантов) вычислительного процесса. Каждый подобный путь называется ветвью алгоритма.
Признаком разветвляющегося алгоритма является наличие операций условного перехода, когда происходит проверка истинности некоторого логического выражения (проверяемое условие) и в зависимости от истинности или ложности проверяемого условия для выполнения выбирается та или иная ветвь алгоритма.
В логических выражениях используется операция сравнения: < (меньше), >(больше), = (больше или равно), = (равно), <> (не равно). Часто встречаются задачи, в которых используются не отдельные условия, а совокупность связанных между собой условий (отношений). Для связи используются AND и (или) OR.
Б)Если |x|=1, то арксин(х)=sign(x)
В)Если |x|>1, то вывести сообщение об ошибке.
Программа вычисления арксинуса — Агcsin.
if x=1 then ypribl:=pi*0.5;
then y contr:=ypribl
5. Программа расчета машинного «эпсилона» — Ерsilon.
while epsilon/2 + 1 > 1 do
WriteLn(‘Машинное эпсилон = ‘,epsilon);
6. Циклические алгоритмы. Программа вычисления конечного произведения (степени числа а).
Алгоритмы, содержащие команды повторения, называют циклическими. Команды повторения составляют цикл. Цикл — это такая форма организации действий, при которой одна последовательность действий повторяется несколько раз (или не разу), до тех пор, пока выполняются некоторые условия.
Цикл с параметром, предусловием и постусловием.
Программа вычисления конечного произведения (степени числа а).
Write(‘Введите основание и показатель степени ==>’);
Writeln(nl,nl,one,nl,’Введите число а ’,
a:6:2,’ в степени’, n:3,’ даёт: ‘);
for i:=2 to abs(n) do p:=p*a;
writeln(p:9:2,nl,one,nl,‘Нажмите клавишу «Enter»!’);
Программа вычисления гипотенуз с использованием функции Роwer.
Program Using Function;
Function Power(a:real; n:integer):real;
for i:=2 to abs(n) do res:=res*a;
if n>0 then power:=res else power:=1/res;
Write(‘Введите катет а ==>’);
writeln(i:2, a:7:2, b:7:2, hyp:9:2);
Процедура РrintLine и ее использование в программах.
| Procedure PrintLine(first,lost:byte); Var count:byte; Begin for count:=1 to first-1 do write(‘ ‘); for count:=first to lost do write(‘ ‘); writeln; End; | Program Use Pro; Uses сrt; Var start:byte; Procedure PrintLine(first,lost:byte); Var count:byte; Begin for count:=1 to first-1 do write(‘ ‘); for count:=first to lost do write(‘ ‘); writeln; End; Begin Clrscr; for start:=1 to 5 do PrintLine(start,2*start); Writeln(‘Fin. ’:30); PrintLine(6,30); readln; End. |
Метод хорд
Допустим, что на [a,b] функция f(x) меняется почти линейно. Тогда ее можно заменить стягивающей хордой y(x):
= 
.
Точку пересечения хорды с осью абсцисс, где y(x1)=0 примем за первое приближение к корню исходного уравнения
x1=a- .
Аналогично x2=x1- .
Обобщая, получим расчетную формулу xn+1=xn- ,
где X―неподвижный конец интервала. Для сходимости метода должны быть выполнены все условия теоремы о сходимости метода Ньютона, только условие f(X)•f»(X)>0 определяет выбор неподвижного конца; противоположный конец берется за начальное приближение: f(x0)•f «(x0)
Геометрическая интерпретация метода хорд показана на рис.4.
Пусть
b+δb= 
, т.е. δb= 
Для оценок возьмем норму-максимум.
x+δx= Þ ||δx||/||x||=2/1=2
Таким образом
В данном примере полученное значение совпадает с коэффициентом обусловленности.
Алгоритм метода Гаусса.
Алгоритм метода прогонки.
Алгоритм метода Зейделя.
А – квадратная матрица коэффициентов порядка n,
b – столбец свободных членов,
х (0) — столбец начальных значений,
n – порядок системы,
kmax- предельное число итераций (страховка от зацикливания),
e — требуемая точность.
х – вектор решений,
kend – фактическое количество итераций (если достигнута точность e), если точность не достигнута за. kmax итераций, то kend= 0.
t – переменная суммирования для накопления очередной компоненты,
xnew – переменная для временного хранения очередной компоненты решения в новом приближении.
Тело алгоритма состоит из двух последовательных циклов: первый играет вспомогательную роль (назначает начальные значения элементам столбца из неизвестных, вычисляет обратные величины диагональных элементов), второй – он троекратный, реализует процесс Зейделя. Во внешнем цикле (цикл «по ε») меняется значение счётчика k от единицы с шагом, равным единице, до заданного предельного числа итераций kmax.
В конце его при истинном неравенстве |xi ( k +1) -x ( k ) i|≤ε (тогда kend=0) выполняется возврат к точке вызова данного алгоритма. В цикле «по строкам» (цикл «по i») вычисляются компоненты очередного приближения xi ( k +1) (которые предварительно записываются в переменной xnew) и анализируется условие |xi ( k +1) -xi ( k ) |≤. Если хотя бы для одной компоненты оно не выполняется, то переменной kend присваивается нуль. Самый внутренний цикл (цикл «по j») служит для для реализации вычислений по формуле (15); в нем из правых частей уравнений системы (16) вычитаются левые части, содержащие все неизвестные кроме i- го.
Алгоритм и его свойства (рассмотреть алгоритм умножения).
Алгоритмом называется точная инструкция исполнителю в понятной для него форме, определяющая процесс достижения поставленной цели на основе имеющихся исходных данных за конечное число шагов.
Основными свойствами алгоритмов являются:
1. Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.
2. Дискретность — процесс решения задачи по алгоритму разбит на отдельные действия.
3. Однозначность — правила и порядок выполнения действий алгоритма имеют единственное толкование.
4. Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.
5. Результативность — по завершении выполнения алгоритма обязательно получается конечный результат.
6. Выполнимость — результата алгоритма достигается за конечное число шагов.
Алгоритм считается правильным, если его выполнение дает правильный результат. Соответственно алгоритм содержит ошибки, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершится вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.
Выделяют три крупных класса алгоритмов:
· вычислительные алгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
· информационные алгоритмы, представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
· управляющие алгоритмы, генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
Есть А и N- целые числа(параметры задачи)
1.Присвоить I значение 0
2.Присвоить Р значение 0
3.Проверка. Если А или N=0, то перейти к шагу 7
4.Присвоить Р значение Р+А
5.Присвоить значение I+1
6.Если I меньше N, то перейти к шагу 4
7.Присвоить М значение Р
Языки программирования.
Язык программирования – система обозначений для описания программ.
Обычный разговорный язык состоит из четырех основных элементов: символов, слов, словосочетаний и предложений. Алгоритмический язык содержит подобные элементы, только слова называют элементарными конструкциями, словосочетания — выражениями, предложения — операторами. Алгоритмический язык (как и любой другой язык), образуют три его составляющие: алфавит, синтаксис и семантика.
Алфавит – фиксированный для данного языка набор символов (букв, цифр, специальных знаков и т.д.), которые могут быть использованы при написании программы.
Синтаксис — правила построения из символов алфавита специальных конструкций, с помощью которых составляется алгоритм.
Семантика — система правил толкования конструкций языка. Таким образом, программа составляется с помощью соединения символов алфавита в соответствии с синтаксическими правилами и с учетом правил семантики.
Существуют различные классификации языков программирования. Все языки программирования делят на языки низкого, высокого и сверхвысокого уровня.
В группу языков низкого уровня входят машинные языки и языки символического кодирования: (Автокод, Ассемблер). Операторы этого языка – это те же машинные команды, но записанные мнемоническими кодами, а в качестве операндов используются не конкретные адреса, а символические имена. Все языки низкого уровня ориентированы на определенный тип компьютера, т. е. являются машинно-зависимыми. Машинно-ориентированные языки – это языки, наборы операторов и изобразительные средства которых существенно зависят от особенностей ЭВМ (внутреннего языка, структуры памяти и т.д.).
Следующую, существенно более многочисленную группу составляют языки программирования высокого уровня. Это Фортран, Алгол, Кобол, Паскаль, Бейсик, Си, Пролог и т.д. Эти языки машинно-независимы, т.к. они ориентированы не на систему команд той или иной ЭВМ, а на систему операндов, характерных для записи определенного класса алгоритмов. Однако программы, написанные на языках высокого уровня, занимают больше памяти и медленнее выполняются, чем программы на машинных языках.
К языкам сверхвысокого уровня можно отнести лишь Алгол-68 и APL. Повышение уровня этих языков произошло за счет введения сверхмощных операций и операторов.
Источник: infopedia.su
1. Задачи по разработке алгоритмов и программ
Задача 1.1.Разработать схему алгоритма и программу для вычисления площади треугольникаSпо заданным с клавиатуры значениям стороныaи высотыh, проведенной к этой стороне. Значение площади вывести на экран.
Алгоритм решения задачи состоит в вычислении площади треугольника по введенным значениям стороны и высоты. Логика алгоритма сводится к построению алгоритма с линейной структурой, в котором каждая последующая процедура выполняется после предыдущей. Вычисление площади треугольника производится по формуле .
Разработанная схема алгоритма представлена на рис. 1.1. Изображенные на рисунке символы пронумерованы.
Обозначения схемы алгоритма:
S – значение площади треугольника.
Program Prog1_1;
Write(‘Введите значение стороны а ‘);
Write(‘Введите значение высоты h ‘);
Writeln(‘Площадь треугольника S = ‘, S:7:2);
Результат работы программы
Введите значение стороны а 1.5
Введите значение высоты h 7.2
Площадь треугольника S = 5.40
1.2. Циклические вычислительные процессы
Задача 1.2.Разработать схему алгоритма и программу вычисления и вывода на экран значений площадей треугольников с различными основаниямиаи постоянной высотой h, проведенной к основанию. Величинаапринимает значенияа = 1; 7 (1). Значение высотыhвводится с клавиатуры.
Алгоритм решения задачи состоит в последовательном переборе значений аот 1 до 7 с шагом 1 при вычислении площади по формуле. Алгоритм решения задачи состоит из одного цикла и представлен на рис. 1.2 в двух вариантах:
1) с использованием парного символа «Граница цикла» (рис. 1.2, а);
2) с использованием символа «Подготовка» (рис. 1.2, б).
Обозначения схем алгоритма:
S – значение площади треугольника.
Program Prog1_2;
Write(‘Введите значение высоты h ‘);
for a:=1 to 7 do
Writeln(‘При a = ‘, a, ‘ S = ‘, S:7:2);
Результат работы программы
Введите значение высоты h 7.2
При а = 1 S = 3.60
При а = 2 S = 7.20
При а = 3 S = 10.80
При а = 4 S = 14.40
При а = 5 S = 18.00
При а = 6 S = 21.60
При а = 7 S = 25.20
Задача 1.3. Разработать схему алгоритма и программу вычисления и вывода на экран значений площадей треугольников по изменяющимся значениям сторон и высот. Значение стороны а изменяется по закону а = 1; 3 (1), высота h, проведена к стороне a и изменяется по закону 1; 5 (0,8).
В алгоритме этой задачи необходимо использовать два цикла. Для последовательного перебора значений аиспользуем цикл от 1 до 3 с шагом 1, а для перебора значенийhиспользуем цикл от 1 до 5 с шагом 0,8 с предусловиемh≤ 5. На рис. 1.3 представлена схема алгоритма решения задачи с использованием различных символов цикла, а именно: цикл для перебора переменнойhорганизован в виде разветвляющейся структуры, а для перебора переменнойa– в виде циклической структуры с использованием парного символа «Граница цикла».
Обозначения схем алгоритма:
S – значение площади треугольника.
Источник: studfile.net
Алгоритмы подпрограмм
Алгоритмы можно разделить на два класса: алгоритмы программ и алгоритмы подпрограмм. В настоящее время предполагается, что всякая достаточно сложная программа состоит из главной программы и набора подпрограмм. Использование подпрограмм позволяет значительно повысить производительность труда при программировании и упростить процесс разработки программы.
Подпрограмма – это специальным образом оформленный функционально законченный фрагмент алгоритма, который может вызываться из различных частей программы, выполнять определенные действия и возвращать управление в точку вызова.
Принцип действия подпрограмм поясняет рис.3.7.1. Когда вычислительный процесс достигнет блока обращения к процедуре PR1, управление передается в процедуру, формальные параметры W,B и Z получат значения фактических параметров A,B и Y и выполняется алгоритм процедуры. После завершения алгоритма процедуры управление возвращается в точку вызова процедуры в главной программе. Аналогично, когда в главной программе встретится обращение к подпрограмме функции FY (блок, в котором вычисляется значение Z) управление будет передано в подпрограмму функцию FY, формальные параметры P и Q получат значения фактических параметров P и T и будет выполнен алгоритм функции FY. При этом имя должно получить значение и это значение будет использоваться в выражении, из которого осуществлялось обращение к подпрограмме.
Замечание. Не только главная программа может использовать какую-либо подпрограмма, но и любая подпрограмма может использовать другие подпрограммы.
Различают два типа подпрограмм: процедуры и функции. Главное отличие – процедура может возвращать много значений данных, а функция возвращает только одно значение. Обычно подпрограммы используются для оформления функционально законченных фрагментов алгоритмов: вычисления
значений функций, вычисления сумм рядов, решение уравнений, обработки матриц и т.п.
3.5.1. Подпрограмма процедура.
Если при решении конкретной задачи предполагается использовать процедуры или функции, то составляют отдельно схемы алгоритмов для главной программы, процедур и функций. Заметим, что к подпрограммам можно обращаться не только из главной программы, но также и из самих процедур и функций. Для обращения к процедуре в соответствующем месте схемы алгоритма программы (или подпрограммы, использующей данную процедуру) указывается блок обращения к процедуре (рис.3.7.2), в котором записывается имя процедуры и список фактических параметров. Фактическими параметрами называются идентификаторы, которые используются в алгоритме главной программы.
При составлении схемы алгоритма процедуры в подрисуночной подписи необходимо указать имя процедуры и список формальных параметров. Формальными называются параметры, которые используются в алгоритме самой процедуры, через них осуществляется обмен данными между программой
Соответствие списков фактических и формальных параметров устанавливается только по порядку следования параметров в списках. Имена соответствующих Схема алгоритма процедуры строится по общим правилам.
Пример 1. Пусть необходимо вычислять функцию
Для упрощения главной программы вычисление функции У вынесем в процедуру, а в главной программе оставим только ввод исходных данных и вывод результатов.
Схема алгоритма главной программы приведена на рис.3.7.3, а схема алгоритма процедуры РВХ представлена на рис.3.7.4.
Формальные и фактические параметры делятся на входные и выходные. Входные – это параметры, через которые в подпрограмму передаются значения данных из вызывающей программы (переменные А и Х на рис3.7.3).
Выходные – это параметры, через которые из процедуры возвращаются значения результатов (переменная У).
Имена формальных и фактических параметров могут быть различными, либо совпадать но всегда они понимаются как различные. Напрамер, если в предыдущем примере в главной программе понадобится вычислять функцию
то обращение к подпрограмме запишется в виде
3.5.2. Подпрограмма функция.
Как отмечалось выше подпрограмма функция возвращает только одно значение. Принципы использования подпрограмм функций такие же как и процедур, но есть три отличия.
1. Результат возвращается из функции через имя функции, поэтому имя функции должно хотя бы один раз встретиться слева от оператора присваивания.
2. Смысл фактических и формальных параметров для функции тот же, что и в случае процедуры, но все параметры функции являются входными.
3. Обращение к подпрограмме типа «Функция» в главной программе осуществляется по имени из выражения. После имени записывается список фактических параметров.
Пример 2. Оформим алгоритм предыдущего примера в виде главной программы и подпрограммы функции с именем PFY. В данном случае списки формальных и фактических параметров будут содержать только две переменные – А и Х, так как результат из подпрограммы функции возвращается через имя функции. Схема алгоритма главной программы приведена на рис.3.7.5, а схема алгоритма подпрограммы функции представлена на рис.3.7.6.
Правила и рекомендации.
1. Списки формальных и фактических параметров должны быть согласованы по физическому смыслу переменных, порядку следования, количеству и типу.
2. Значения входных фактических параметров должны быть определены к моменту обращения к подпрограмме.
3. Не рекомендуется в подпрограммах использовать ввод и вывод данных (если это не подпрограммы ввода, вывода). Это затрудняет работу с подпрограммами и ограничивает область их применения.
4. В случае необходимости в подпрограммах целесообразно предусматривать средства контроля данных с целью обеспечения нормального завершения алгоритма (например, проверка подкоренного выражения) при этом подпрограмма должна возвращать признак ошибки для анализа его в главной программе.
Пример.. Пусть необходимо составить схему алгоритма вычисления значения функции
Схемы алгоритмов главной программы и процедуры вычисления функции приведены на рис.3.7.7.
Источник: studopedia.su