Отладка программы (поиск ошибок) и проверка правильности работы программы при помощи тестовых примеров. На одном из этапов разрабатывается алгоритм будущей программы icon

Отладка программы (поиск ошибок) и проверка правильности работы программы при помощи тестовых примеров. На одном из этапов разрабатывается алгоритм будущей программы


Смотрите также:
Техническое задание 4 Алгоритм основной программы 5 5 Алгоритмы обработчиков прерываний 6...
Техническое задание 4 Алгоритм основной программы 5 5 Алгоритмы обработчиков прерываний 6...
Содержание программы 8 Учебно-тематический план 21 Требования к уровню освоения программы 25...
Составление программы на языке программирования. Отладка и тестирование программы...
Составление программы на языке программирования. Отладка и тестирование программы...
Составление программы на языке программирования. Отладка и тестирование программы...
Проверил
Рабочей программы учебной дисциплины анатомия человека уровень основной образовательной...
Углубленный обзор программы работы по мерам стимулирования Резюме мнений, опыта и вариантов...
Углубленный обзор программы работы по мерам стимулирования сводный доклад...
Углубленный обзор программы работы по мерам стимулирования сводный доклад...
1. Основные компоненты компьютера, их функциональное назначение и принципы работы...



Загрузка...
скачать


Алгоритм. Управляющие структуры


Решение задач с помощью компьютера включает в себя следующие основные этапы:

    1. постановка задачи, её анализ;

    2. разбиение задачи на логически завершенные подзадачи (декомпозиция) и описание основного алгоритма;

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

    4. перевод алгоритма на язык программирования (этот процесс называется кодированием);

    5. отладка программы (поиск ошибок) и проверка правильности работы программы при помощи тестовых примеров.

На одном из этапов разрабатывается алгоритм будущей программы. Алгоритмом назовём последовательность действий, ведущих от начального состояния исходных данных к некоторому результату либо к пояснению, по какой причине задача не может быть решена.

Основные свойства алгоритма:

понятность – исполнитель алгоритма должен знать, как его выполнять;

дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определённых) шагов, этапов;

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

результативность – алгоритм должен приводить к решению задачи за конечное число шагов;

массовость ­­­­­– алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные должны выбираться из некоторой области, которая называется областью применимости алгоритма.

На практике будем пользоваться формами представления алгоритмов:

    • псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

    • программная (тексты на языках программирования).

Для написания алгоритма решения конкретной задачи будет достаточно знаний об организации работы трёх управляющих структур:

  1. следование – выполнение указанного набора действий в естественном порядке без пропусков и повторений;

  2. развилка – выполнение одного из двух действий в зависимости от выполнения (истинности) или невыполнения (принятия ложного значения) некоторого логического выражения;

  3. цикл – выполнение некоторое количество раз одного и того же набора действий, который может либо зависеть от некоторой величины (параметра), либо не зависеть от какой-либо величины.

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


^ Линейные вычислительные алгоритмы


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

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

Помимо операций ввода-вывода основным элементарным действием в алгоритме является операция присваивания значения переменной. Формат команды присваивания:

<имя переменной> = <выражение>

Знак «=» следует читать как «присвоить». Под командой присваивания понимается последовательность действий:

  • вычисляется выражение;

  • полученное значение записывается в переменную.

Отметим три основных свойства команды присваивания:

  1. до тех пор пока переменной не присвоено никакое значение, она остается неопределенной;

  2. значение, которое было присвоено переменной, сохраняется в ней до следующей операции присваивания другого значения этой переменной;

  3. значение, вновь присвоенное переменной, заменяет её предыдущее значение.


^ Пример построения линейного вычислительного алгоритма


Пример. Разработать алгоритм и составить по нему программу (разработать консольный проект) для вычисления значений функции z = . Область определения функции не учитывать.

Алгоритм

объявление вещ: х, у, z

ввод х , у

z=(sin3(x2)+cos(y))/(x2/3+5)

вывод х, у, z





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


Управляющая структура «развилка».

Логические операции и операции отношения

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

если <условие> то

действия1

иначе

действия2

все_если

Работа структуры организована по принципу: если <условие> истинно (выполняется), то выполняются действия1; в случае ложности (невыполнения) <условие> выполняются действия2.

Возможна вложенность структур «если–то–иначе» любой глубины, т.е. вместо действия1 и/или действия2 может быть записана еще одна структура «развилка» и т.д.

<условие>, записанное после слова если, представляет собой логическое выражение. Логические выражения применяются для определения истинности или ложности определенных ситуаций. Логическое выражение – это два операнда, соединенные либо логической операцией, либо операцией отношения. Под логической операцией понимается одна из операций, связывающих два операнда: И, ИЛИ или операция отрицания НЕ, записываемая перед операндом. Если <условие> – два условия, связанные логической операцией И, то <условие> будет истинным в случае одновременного исполнения этих двух условий. Если <условие> – два условия, связанные логической операцией ИЛИ, то <условие> будет истинным в случае, когда хотя бы одно из этих двух условий будет выполняться. Результаты выполнения логических операций приведены в табл.

Значение операнда 1 (оп1)

Значение операнда 2 (оп2)

Результат операций

НЕ(оп1)

(оп1) И (оп2)

(оп1) ИЛИ (оп2)

0

0

1

0

0

0

1

1

0

1

1

0

0

0

1

1

1

0

1

1

Под операцией отношения понимается одна из операций, связывающих два операнда: > (больше), >= (больше или равно), < (меньше), <= (меньше или равно), = (==) (равно), < > (!=) (не равно). Операция отношения позволяет сравнивать числовые выражения по их значениям.


Пример. Определить условие попадания точки с координатами (x;y) в указанную область D:

Напишем условие попадания точки с координатами (x;y) в указанную область. Очевидно, что данная область должна быть разбита на две непересекающиеся области D1 и D2, т.е. D=D1UD2. Таким образом, можно установить, что точка может попасть в D1 или в D2.

Опишем условие попадания точки (х;у) в области D1 и D2:

D1: x>=-4 И x<=4 И y>=0 И y<=2

D2: x>=0 И x<=2 И y>=-2 И y<=0

Таким образом, условие принадлежности точки с координатами (x;y) области D будет следующим:

(x>=-4 И x<=4 И y>=0 И y<=2) ИЛИ (x>=0 И x<=2 И y>=-2 И y<=0)

В Excel( x – A3 y – B3):

ИЛИ(И(A3>=-4;A3<=4;B3>=0;B3<=2);И(A3>=0;A3<=2;B3>=-2;B3<=0))



Программирование разветвляющихся вычислительных процессов


Пример 1. Разработать алгоритм и составить по нему программу для вычисления значений функции y = f(x). Необходимо учитывать область определения функции:





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

При разработке алгоритма будем рассматривать промежутки числовой оси слева направо. Обозначения в алгоритме: ФНЗ – функция не задана; ФНО – функция не определена.

Записывая основной алгоритм решения задачи, вместо вычислений каждой части функции для упрощения будем писать блок1, блок2 и блок3. Поставим в соответствие каждому блоку алгоритм вычисления конкретной функции с учетом её области определения. Последний этап разработки алгоритма решения исходной задачи – подстановка в основной алгоритм вместо блоков 1,2,3 соответствующих вычислительных алгоритмов.

Сделаем небольшое замечание относительно записи текста алгоритма. Рекомендуется записывать текст алгоритма «ступеньками», т.е. новый блок «если – иначе» нужно записывать с отступом относительно предыдущего блока «если – иначе» и т.д. Так же следует поступать и при записи текста программы, соответствующей алгоритму. Одной из причин этого является то, что структура алгоритма и программы хорошо просматривается, что может помочь при обнаружении синтаксических ошибок.

Основной алгоритм:

объявление переменных вещ: х, у

ввод х

если х<5

блок1

иначе

если x<7

«ФНЗ»

иначе

если x<12

блок2

иначе

если х<=15

«ФНЗ»

иначе

блок3

все_если

все_если

все_если

все_если


Рассмотрим вычисления в каждом из блоков 1, 2 и 3 отдельно.

Блок1. Требуется вычислить функцию . При вычислении учитываем, что подкоренное выражение должно быть больше или равно нулю и при этом знаменатель не должен равняться нулю. Таким образом, получаем:

если cos(х)>0



печать у

иначе

«ФНО»

все_если


Блок2. Требуется вычислить функцию . Здесь никаких ограничений на вычисления нет. Таким образом, получаем:



печать у

Блок3. Требуется вычислить функцию . При вычислении учитываем, что подкоренное выражение должно быть больше или равно. Таким образом, получаем:

если 25-х>=0



печать у

иначе

«ФНО»

все_если

В основной алгоритм вместо блоков 1,2,3 подставим алгоритмы вычисления соответствующих частей функции. В итоге получаем алгоритм решения исходной задачи.

Алгоритм

объявление переменных вещ: х, у

ввод х

если х<5

если cos(х)>0



печать х,у

иначе

«ФНО»

все_если

иначе

если x<7

«ФНЗ»

иначе

если x<12



печать х,у

иначе

если х<=15

«ФНЗ»

иначе

если 25-х>=0



печать х,у

иначе

«ФНО»

все_если

все_если

все_если

все_если

все_если

Примечание. В качестве тестового примера можно ввести следующие значения: х=16 и х=30.

ЕСЛИ(<условие>;<выр_ист_условия>;< выр_ложн_условия>)


Пример 2. Разработать алгоритм и составить по нему программу для вычисления значений функции z = f(x,y) в зависимости от попадания точки с координатами (х,у) в область D (область D выделена серым цветом):







В задаче требуется вычислить функцию, вид которой зависит от координат точки координатной плоскости. Если точка с координатами (х,у) попадает в область D, то вычисляется первая часть функции (в алгоритме – блок 1), в противном случае – вторая часть (блок 2). Процесс написания алгоритма разобьем на четыре этапа:

написание основного алгоритма решения задачи;

определение условия принадлежности точки области ^ D. Так как одна и та же точка не может принадлежать двум непересекающимся областям одновременно, разобьем область D на две области: D1 (треугольник) и D2 (кольцо);

написание вспомогательных алгоритмов вычисления каждой части заданной функции;

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

Обозначения в алгоритме: ФНО – функция не определена.

Рассмотрим отдельно этапы алгоритма.

  1. Запишем основной алгоритм решения задачи:

объявление вещ: x, y, z

ввод х, у

если () или ()

блок 1

иначе

блок 2

все_если


  1. Математическое определение условий:

  1. . Найдем уравнение прямой, проходящей через точки с координатами (-3;0) и (0;2). Запишем уравнение прямой в общем виде .




Таким образом, уравнение прямой .

.

  1. . Определим уравнение окружности с центром в точке (2,0) радиуса R=2: (внешняя окружность). Определим уравнение окружности с центром в точке (2,0) радиуса R=1: (внутренняя окружность). Так как область D2 находится внутри кольца, включая его границы, то условием принадлежности точки (х,у) области D2 будут неравенства: , .

.


  1. Вычислительные алгоритмы, соответствующие блокам 1,2:

Блок 1

Блок 2

если х-у ≠ 0

z=1/(x-y)

печать х, у,z

иначе

«ФНО»

все_если

если ху > 0

z=ln(xy)

печать х, у,z

иначе

«ФНО»

все_если

Написать программу, соответствующую алгоритму:


Алгоритм

объявление переменных вещ: х, у, z

ввод х, у

если (((x>=-3 и x<=0) и (y>=0 и y<=2*x/3+2)) или

((x-2)*(x-2)+y*y<=4 и (x-2)*(x-2)+y*y>=1))

если х-у ≠ 0

z=1/(x-y)

печать х, у,z

иначе

«ФНО»

все_если

иначе

если х*у > 0

z=ln(x*y)

печать х, у,z

иначе

«ФНО»

все_если

все_если

Примечание. В качестве тестового примера можно ввести значения х=1, у=1 и х=3, у=5.




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


Алгоритмические циклические структуры предназначены для решения задач, которые подразумевают выполнение одного и того же набора действий определённое количество раз. Выделяют три типа циклов: с параметром, с предусловием и с постусловием. Каждый цикл имеет заголовок и тело цикла.


^ Типы циклов


Цикл с параметром

На псевдокоде цикл записывается следующим образом:

для i=<начальное_значение> до <конечное_значение> шаг <размер_шага>

<операторы_тела_цикла>

все_для i

Параметр цикла i показывает, сколько раз должны быть выполнены операторы тела цикла; <начальное_значение> – значение, с которого начинает изменяться параметр цикла; <конечное_значение> – значение, до которого изменяется параметр цикла; <размер_шага> – значение, показывающее, на сколько изменяется параметр цикла после выполнения всех операторов тела цикла.

Среди операторов тела цикла могут быть условные операторы, циклы и другие операторы.

Работа цикла с параметром организована по схеме: параметру присваивается <начальное_значение>, затем проверяется, больше или нет значение параметра значения <конечное_значение>. Если нет, то выполняются операторы тела цикла. В противном случае цикл завершает свою работу. После очередного выполнения операторов тела цикла значение параметра цикла изменяется на <размер_шага>. Затем опять проверяется, больше или нет значение параметра значения <конечное_значение>. Если нет, то выполняется тело цикла. В противном случае цикл завершает свою работу и т.д.

^ Цикл с предусловием

На псевдокоде цикл записывается следующим образом:

пока <условие>

<операторы_тела_цикла>

все_цикл

Определение <условие> аналогично его определению в разделе «^ Разветвляющиеся вычислительные процессы». Тело цикла выполняется до тех пор, пока <условие> истинно. Когда условие станет ложным, выполняется строка, следующая за циклом.

Работа цикла с предусловием:

  1. Проверяется истинность выражения <условие>. Если <условие> истинно, то выполняются операторы тела цикла.

  2. После того как выполнился последний оператор цикла, управление передаётся заголовку цикла. Переход на пункт 1.

  3. Если условие в заголовке ложно, то цикл завершает свою работу.

Используя оператор цикла с предусловием, необходимо следить за тем, чтобы операторы тела цикла воздействовали на условие, либо за тем, чтобы оно ещё каким-то образом изменялось во время вычислений в теле цикла. Для этого часто используют унарные операции ++ или – для изменения параметров, входящих в <условие>. Только при изменении условия можно избежать зацикливания.

^ Цикл с постусловием

На псевдокоде цикл записывается следующим образом:

цикл

<операторы_тела_цикла>

пока <условие>

Правила работы цикла с постусловием:

  1. Выполняется тело цикла.

  2. Проверяется истинность <условие>: если <условие> истинно, то выполняется тело цикла. Если оно ложно, то цикл завершает свою работу.

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


Пример. Вывести на экран таблицу из n значений функции .

Алгоритм решения задачи строится следующим образом. Из условий задачи видно, что значения x изменяются от a до b. Шаг h, на который изменяются значения x, вычисляется по формуле . Формула для изменения значений x выглядит следующим образом:




Т

Такие формулы называют рекурсивными, поскольку новое значение переменной зависит от предыдущего значения и вычисляется через него.

Каждый раз при получении нового значения x будем вычислять значение y по заданной формуле. Таким образом, необходимо повторить одну и ту же последовательность действий известное (это важно) число раз (в данной задаче количество повторений равно n). Для решения такого типа задач как раз и используются циклические вычислительные процессы. В нашей задаче будет использован цикл с параметром.

Алгоритм

объявление вещ: а,b,x,y,h, цел: n,i

// ввод концов отрезка

ввод a

ввод b

// задаем количество вычисляемых значений функции

ввод n

// вычисление шага

h=(b-a)/n

// задаем начальное значение аргумента

x=a

// цикл для построения таблицы значений

для i=1 до n шаг 1

// вычисляется значение функции

y=|cos(x)|+|x-1|

печать x,y

// вычисляем новое значение аргумента

x=x+h

всё_для i


// цикл для построения таблицы значений

для x=a до b шаг h

// вычисляется значение функции

y=|cos(x)|+|x-1|

печать x,y

всё_для x


^ Вычисление последовательностей


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


^ Примеры вычисления последовательностей

    1. Пусть переменная х принимает последовательно значения х1, х2, х3, … , хn, … . Такое нумерованное множество чисел называется последовательностью. Закон образования последова-тельности задается формулой n-го члена хn.

Из данного определения видно, что для задания последовательности нужно знать закон образования n-го члена последовательности, т.е. функцию, которая ставит натуральному числу n в соответствие некоторое значение f(n): xn=f(n).

    1. Последовательность {xn} называется сходящейся к х*, если при n→ ∞ |x*-xn|→0.

    2. Последовательность {xn} называется убывающей, если при n→ ∞ |xn|→0.

    3. Последовательность {xn} называется возрастающей, если при n→ ∞ |xn|→∞.

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

    1. Пусть дана некоторая последовательность элемент-ов а12, а3, … , аn,…, причём ак+1=F1, а2,… аn, ак), ак+2=F23,...аn, ак, ак+1). Если функцию F можно определить или она задана, то последовательность а1, а2, а3, … , ак, ак+1, … называется рекуррентной последовательностью.

Формула n-го члена рекуррентной последовательности (рекуррентная формула) аn=F(an-k ,an-k+1n+2,…,аn-1), где число k называется глубиной рекурсии и определяет количество предшествующих элементов, необходимых для вычисления аn. Смысл глубины рекурсии в том, что она максимальному количеству переменных, необходимых для вычисления элементов последовательности.

^ Примеры задач с использованием

рекуррентных последовательностей

Вычислить n-й элемент последовательности.

Вычислить сумму или произведение первых n элементов последовательности.

Найти количество элементов на данном отрезке последовательности, удовлетворяющих определенному условию.

Найти номер первого элемента последовательности, удовлетворя-ющего определённому условию.

Пример 1. Вычислить n-й элемент арифметической прогрессии а1=1, а2=3, а3=5 и т.д.

Написание алгоритма решения задачи будет состоять из двух шагов.

Выведем рекуррентную формулу. Так как разность прогрессии равна 2, то рекуррентная формула будет следующей: . Читается формула так: при i=1 ai=1; при i2 ai=ai-1+2, т.е. каждый последующий элемент равен сумме предыдущего и 2.

Определим глубину рекурсии. Поскольку каждый следующий элемент вычисляется только через один предыдущий, то глубина рекурсии равна 1. Следовательно, для вычисления элементов последовательности нужны две переменные. Однако в этом случае можно обойтись одной переменной. Для определения значения последующего элемента последовательности будем использовать рекурсивную формулу


Алгоритм

объявление цел: а,n,i

ввод n

//текущий элемент последовательности и его текущий номер

а=1,i=1

//вычисляем элементы последовательности

для i=2 до n шаг 1

а=а+2

всё_для i

печать а


Пример 2. Вывести на печать первые n (n3) чисел Фибоначчи. Распечатать все элементы и подсчитать, сколько среди них четных чисел. Числа Фибоначчи образуются по закону:

а1=1, а2=1, … , аi=ai-1+ai-2, ….


Написание алгоритма решения задачи будет состоять из двух шагов.

Рекуррентная формула задается в определении чисел Фибоначчи: .

Глубина рекурсии равна 2, поэтому для вычисления чисел Фибоначчи нужны три переменные.


Алгоритм

объявление цел: i, n, a1, a2, а3, s

//ввод количества вычисляемых элементов

ввод n

//инициализация

а1=1, а2=1, s=0

печать а1

печать а2

//цикл для вычисления элементов и количества четных элементов

для i=3 до n шаг 1

a3= a2+ a1

печать а3

если (остаток от деления а3 на 2)=0 //условие четности значения переменной а3

s=s+1

все_если

а1= a2

а2 = а3

всё_для i

печать s

Примечание. В алгоритме использована рекурсивная формула


Последовательности в примерах 1 и 2 являются возрастающими, поэтому вычисление элементов ограничивается заданием их количества.


Пример 3. Для заданных действительного x и целого n вычислить сумму .


Написание алгоритма решения задачи будет состоять из двух шагов.

Формула для вычисления суммы:

.

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

Глубина рекурсии в данном случае не определяется, так как данная формула не является рекуррентной.

Алгоритм

Объявление цел: i, n; вещ: х, s, а

//ввод количества элементов

ввод n

ввод x

//начальное значение номера элемента

i=1

//начальное значение элемента

а=sin(x)/x

//начальное значение суммы элементов

s=a

//цикл для вычисления элементов и их суммы

для i=2 до n шаг 1

a= (-1)i-1sini(x)/xi

s=s+a

всё_для i

печать s

Написать программу, соответствующую алгоритму

Примечание. В алгоритме использована рекурсивная формула




Пример 4. Для заданного вещественного х и малой величины eps вычислить сумму ряда .


Написание алгоритма решения задачи будет состоять из двух шагов.

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

,

где . Значение а0 либо вычисляется по формуле ряда (записывается после знака суммы) – вместо параметра подставить его начальное значение, либо из записи самого ряда – первое слагаемое ряда. Формула для берется либо из формулы ряда , либо ее необходимо определить по изменению слагаемых ряда. Для нахождения формулы подставим в формулу i-1 вместо i: .

Для вычисления q необходимо знать, что есть факториал числа. Факториалом числа i называют произведение последовательных натуральных чисел от 1 до i включительно, т.е. i! = 1·2·3·…·(i-1)·i. Следовательно, (2i-1)! = 1·2·3·…·(2i-1), а (2i+1)! = 1·2·3·…·(2i-1)·2i·(2i+1). Вычислим . Получим рекуррентную формулу

.


При записи этой формулы наиболее частой ошибкой является следующая

запись этой формулы:

.

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

Глубина рекурсии равна 1, т.е. для вычисления элементов последовательности требуются две переменные. Как и в примере 1, обойдемся одной переменной.

Примечание. При вычислении суммы ряда решающую роль играет величина eps. Она задаётся для того, чтобы ограничивать количество вычисляемых элементов последовательности, добавляемых в сумму. При вычислении каждого элемента последовательности его модуль сравнивается с eps. Если он больше eps, то вычисления продолжаются, в противном случае вычисление элементов последовательности и добавление их в искомую сумму прекращается. Такой процесс называется вычислением суммы ряда с точностью eps. В качестве значения переменной eps можно взять 0,001 или 0,00001 и т.п.

Алгоритм

Объявление вещ: х, eps ,S, a, цел: i

ввод х, eps

//начальное значение номера элемента последовательности

i=0

//начальное значение элемента последовательности

a=1

//начальное значение суммы элементов последовательности

s=a

//цикл для вычисления элементов и суммы последовательности

покa |a|>=eps

//увеличиваем номер элемента

i=i+1

//вычисляем новый элемент

a=a*(-x)/(2*i*(2*i+1))

//добавляем его в сумму

s=s+a

все_цикл

печать s


Пример 5. Найти наименьший номер члена последовательности, для которого выполняется условие . Вывести на экран номер и все элементы , где . Последовательность задается формулой .

Написание алгоритма решения задачи будет состоять из двух шагов.

Формула для вычисления элементов последовательности:

,

где i – номер текущего элемента последовательности.

Глубина рекурсии в данном случае равна 1, т.е. для вычисления элементов последовательности нужны две переменные.

Алгоритм

Объявление цел: i; вещ: аt, ap, eps

ввод eps

//номер элемента равен 1

i=1

// текущий элемент

аt=0.01

печать at

//номер элемента увеличивается на 1

i++

// новый элемент

ap=ln2(at)+1

печать ap

// цикл для вычисления элементов последовательности

пока |at-ap|>=eps

//номер элемента увеличивается на 1

i++

//последующий элемент становится текущим

at=ap

//вычисляется последующий элемент

ap=ln2(at)+1

печать ap

всё_цикл

печать i


^ Структура алгоритмов вычисления

рекуррентных последовательностей


Как видно из решения задач, приведенные алгоритмы имеют общую структуру. Алгоритмы решения задач на нахождение элементов и/или суммы элементов последовательности можно записать в следующем виде:


задать начальное значение номера элемента i = i0

задать начальное значение элемента a = a0

задать начальное значение суммы элементов s = a0

цикл <условие_продолжения_вычислений>

i =i+1

a = f(a,a0)

печать a (если нужно)

s = s+a (если нужно)

все_цикл

печать s (если нужно)


Здесь f(a,a0) – это функция, описывающая зависимость последующего элемента последовательности от предыдущего.


Массивы


Математическим понятием, которое привело к появлению в языках программирования понятия «массив», являются матрица и ее частный случай – вектор. Таким образом, массив – совокупность элементов любого допустимого в языке программирования одного типа данных. В Excel массивом понимают совокупность ячеек, для которых определена некоторая формула. При этом совокупность ячеек представляет непрерывный диапазон. Основным отличием массива является невозможность изменения формулы для какой-либо части массива. Для того чтобы обозначить массив необходимо выполнить:

      1. Выделить непрерывный дипазон ячеек

      2. Ввести формулу для ячеек этого диапазона

      3. Нажать клавиши: Ctrl+Shift+Enter

Для объявления массива необходимо указать:

    1. тип элементов массива;

    2. имя массива;

    3. его размерность, т.е. число индексов, необходимое для обозначения конкретного элемента.

Каждый массив может разбиваться на несколько подмассивов, которые так же можно разбивать и т.д. Количество таких разбиений, или измерений, называется размерностью массива. Это понятие необходимо отличать от понятия размера массива, определяемого как количество его элементов. При объявлении массива в каждом измерении указывается количество элементов этого измерения.


^ Нахождение приближенного значения корня нелинейного уравнения


Нелинейные уравнения – это уравнения, в которые переменная входит в степени больше чем 1. Решить уравнение – значит, найти его корень. Корнем называется такое значение переменной, при подстановке которого в уравнение вместо переменной уравнение превращается в верное равенство.


1. Методы нахождения корней уравнения f(x)=0

на отрезке [a;b] с заданной точностью eps


Постановка задачи заключается в следующем. Дан отрезок [a;b], на котором находится корень уравнения f(x)=0. Найти с заданной точностью eps корень этого уравнения. Рассмотрим три метода нахождения корней нелинейных уравнений.


1.1. Метод дихотомии (половинного деления)


Данный метод основывается на утверждении, что если на отрезке [a;b] содержится корень уравнения f(x)=0, то значения f(a) и f(b) имеют разные знаки, т.е. f(a)·f(b)<0.

Схема метода

Отрезок делится пополам – середина обозначается через точку c (рис.14). Если |a-b|>=eps, то вычисления продолжаются. Эта проверка означает, что если |a-b|=eps, то опять происходит проверка f(a)·f(c)<0 или нет. Если да, то значение c присваивается переменной b, иначе значение c присваивается перемен- ной a и т.д. Графически этот метод изображен на рис.14.

Опишем алгоритм и соответствующую программу для нахождения корней уравнения ln(x-3)=0 на отрезке [3.5;5] с помощью этого метода:

Алгоритм




объявление вещ: fa, fb, fc, a, b, c, eps

ввод а

ввод b

fa=ln(a-3)

fb=ln(b-3)

если fa*fb<0

ввод eps

c=(a+b)/2

fc=log(c-3)

пока (|a-b|>=eps )

если (fa*fc<0)

b=c

иначе

a=c;

всё если

c=(a+b)/2

fa=ln(a-3)

fb=ln(b-3)

fc=ln(c-3)

всё пока

печать c

печать fc

иначе

печать “на отрезке нет корня”

все_если





Метод хорд


Метод основывается на утверждении, что если на отрезке [a;b] содержится корень уравнения, то значения f(a) и f(b) имеют разные знаки, т.е. f(a)·f(b)<0.

Схема метода аналогична предыдущему. Разница заключается в поиске значения точки c. Для этого в методе хорд используется уравнение хорды – прямой, проходящей через две точки некоторой кривой. Возьмём т.А(a;f(a)) и т.B(b;f(b)) на кривой y=f(x). Уравнение прямой проходящей через эти точки . Пусть первая координата т.С(с;0) – принадлежит [a;b] и лежащая на оси Ох. Подставим координаты точки C в полученное уравнение. В итоге получаем уравнение для получения значений точек сi при вычислении корня исходного уравнения:

.

Вычисляется точка c. Если |a-b|>=eps, то вычисления продолжаются. Эта проверка означает, что если |a-b|=eps, то опять происход-ит проверка f(a)·f(c)<0 или нет. Если да, то значение c присваивается переменной b, иначе значение c присваивается переменной a и т.д. Графически этот метод изображен на рис.15.

Опишем алгоритм и соответствующую программу для нахождения корней уравнения ln(x-3)=0 на отрезке [3.5;5] с помощью этого метода:

Алгоритм

объявление вещ: fa, fb, fc, a, b, c, eps

ввод а

ввод b

fa=ln(a-3)

fb=ln(b-3)

если fa*fb<0

ввод eps

c=а-(b-a)*fa/ (fb-fa)

fc=ln(c-3)

пока (|f(c)|>=eps )

если (fa*fc<0)

b=c

иначе

a=c;

всё если

c=а-(b-a)*fa/ (fb-fa)

fa=ln(a-3)

fb=ln(b-3)

fc=ln(c-3)

всё пока

печать c

печать fc

иначе

печать “на отрезке нет корня”

все_если


Метод касательных (Ньютона)


Метод основывается на утверждении, что если на отрезке [a;b] содержится корень уравнения, то значения f(a) и f(b) имеют разные знаки, т.е. f(a)·f(b)<0. Точность вычислений зависит от выбора точки, с которой начинаются вычисления. Выбор начальной точки x0 вычислений определяет условие . Схема метода аналогична предыдущим. Разница заключается в поиске значения точки c. Для этого в методе касательных используется уравнение касательной к графику функции: . Пусть первая координата т.С(сi;0) – принадлежит [a;b] и расположена на оси Ох. Подставим координаты точки C в полученное уравнение. В итоге получаем уравнение для получения значений точек сi при вычислении корня исходного уравнения:

.

Если |ci-ci-1|>=eps, то вычисления продолжаются. Если |ci-ci-1|i и т.д. Графически этот метод изображен на рис.16.

Опишем алгоритм и соответствующую программу для нахождения корней уравнения ln(x-3)=0 на отрезке [3.5;5] с помощью этого метода:

Алгоритм

объявление вещ: f_2p, fa, fb, a, b, c, c1, eps

ввод а

ввод b

fa=ln(a-3)

fb=ln(b-3)

если fa*fb<0

ввод eps

f_2p=-1/(a-3)2

если fa*f_2p>0

c1=a

иначе

c1=b

все_если

c=c1-ln(c1-3)/(1/(c1-3))

пока (|c-c1|>=eps )

c1=c

c=c1-ln(c1-3)/(1/(c1-3))

всё_цикл

печать c

печать ln(c-3)

иначе

печать “на отрезке нет корня”

все_если


^ Нахождение приближенного значения определенного интеграла


Нахождение приближенного значения определенного интеграла

с заданной точностью


Существует несколько методов приближенного вычисления определенных интегралов . Численно определенный интеграл равен площади фигуры, ограниченной кривой y=f(x), осью Ox и прямыми x=a и x=b. Такую фигуру называют криволинейной трапецией (рис.17). Рассмотрим методы левых, правых и центральных прямоугольников, а также метод трапеций и метод Симпсона. Суть их в том, что отрезок [a;b] разбивается на n равных частей и находится длина каждого частичного отрезка по формуле . Следовательно, криво-линейная трапеция разбивается на множество элементарных трапеций, и её площадь считается как сумма площадей элементарных трапеций. Площадь же элементарной трапеции приблизительно равна площади элементарного прямоугольника или трапеции и вычисляется по соответствующей формуле.

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

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

В методе Симпсона берутся три ближайшие точки разбиения и по ним строится парабола, график которой приближенно описывает график функции на двух близлежащих частичных отрезках. Ищутся приближенно площади криволинейных трапеций на всех участках и складываются. Это и будет приближенное вычисление определенного интеграла по методу Симпсона. Для нахождения приближенного значения интеграла по методу Симпсона необходимо, чтобы количество частичных отрезков было четным.

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

Математические формулы для всех описанных методов приведены в табл.1.

Таблица 1

Название метода

Формула

Метод левых прямоугольников



Метод центральных прямоугольников



Метод правых прямоугольников



Метод трапеций



Метод Симпсона



Общая схема вычисления интегралов с точностью eps:

ввод a

ввод b

ввод количества разбиений n

вычислить шаг h

ввод eps

вычисление интеграла i0

I1=0

пока |I0-I1|>=eps

I1=I0

увеличение количества разбиений n

вычислить новый шаг h

вычисление интеграла I0

все_пока

печать I0


Далее приведены примеры алгоритмов и соответствующих программ для вычисления приближенного значения определенного интеграла.

Вычислить интеграл с точностью eps методом левых прямоугольников:

Алгоритм

объявление вещ: a,b,h,eps,I0,I1,x; цел: i, n;

ввод a,b,n,eps

h=(b-a)/n

x=a

I0=ln(a-3)

для i=1 до n-1 шаг 1

x=x+h

I0=I0+ln(x-3)

все_для i

I0=I0*h

I1=0

пока |I1-I0|>=eps

I1=I0

n=2*n

h=(b-a)/n

x=a

I0=ln(a-3)

для i=1 до n-1 шаг 1

x=x+h

I0=I0+ln(x-3)

все_для i

I0=I0*h

все_цикл

печать I0



Вычислить интеграл с точностью eps методом центральных прямоугольников:

Алгоритм

объявление вещ: a,b,h,eps,I0,I1,x; цел: i, n;

ввод a,b,n,eps;

h=(b-a)/n;

x=a+h/2;

I0=ln(a-3);

для i=1 до n-1 шаг 1

x=x+h;

I0=I0+ln(x-3);

все_для i

I0=I0*h

I1=0

пока |I1-I0|>=eps

I1=I0

n=2*n

h=(b-a)/n

x=a+h/2

I0=ln(a-3)

для i=1 до n-1 шаг 1

x=x+h

I0=I0+ln(x-3)

все_для i

I0=I0*h

все_цикл

печать I0



Вычислить интеграл с точностью eps методом правых прямоугольников:

Алгоритм

объявление вещ: a,b,h,eps,I0,I1,x; цел: i, n;

ввод a,b,n,eps

h=(b-a)/n

x=a+h

I0=ln(a-3)

для i=2 до n шаг 1

x=x+h

I0=I0+ln(x-3);

все_для i

I0=I0*h

I1=0

пока |I1-I0|>=eps

I1=I0

n=2*n

h=(b-a)/n

x=a+h

I0=ln(a-3)

для i=2 до n шаг 1

x=x+h

I0=I0+ln(x-3)

все_для i

I0=I0*h;

все_цикл

печать I0




Вычислить интеграл с точностью eps методом трапеций


Алгоритм

объявление вещ: a,b,h,eps,I0,I1,x; цел: i, n;

ввод a,b,n,eps

h=(b-a)/n

x=a

I0=0

для i=1 до n-1 шаг 1

x=x+h

I0=I0+ln(x-3)

все_для i

I0= h*((log(a-3)+log(b-3))/2+I0)

I1=0

пока |I1-I0|>=eps

I1=I0

n=2*n

h=(b-a)/n

x=a

I0=0

для i=1 до n шаг 1

x=x+h

I0=I0+ln(x-3)

все_для i

I0= h*( (log(a-3)+log(b-3))/2+I0)

все_цикл

печать I0




Вычислить интеграл с точностью eps методом Симпсона:

Алгоритм

объявление вещ: a,b,h,eps,I0,I1,x,f2i_1,f2i; цел: i, n

ввод a,b,n,eps;

//если n – нечетное, то умножаем на 2

если n%2= =1

n=n*2

h=(b-a)/n

f2i_1=0; //для «нечетных» точек

f2i=0; //для «четных» точек

x=a+h;

для i=1 до (n-1)/2 шаг 1

f2i_1=f2i_1+log(x-3);

x=x+h;

f2i=f2i+log(x-3);

x=x+h;

все_для i

f2i_1=f2i_1+log(x-3);

I0=h*(log(a-3)+log(b-3)+4*f2i_1

+2*f2i)/3;

I1=0

пока |I1-I0|>=eps

I1=I0

n=2*n

h=(b-a)/n

x=a

I0=0

для i=1 до (n-1)/2 шаг 1

f2i_1=f2i_1+log(x-3);

x=x+h;

f2i=f2i+log(x-3);

x=x+h;

все_для i

f2i_1=f2i_1+log(x-3);

I0=h*(log(a-3)+log(b-3)+4*f2i_1+

2*f2i)/3;

все_цикл

печать I0


Примечание. Если сравнить результаты вычислений интегралов с точным значением определенного интеграла, то можно сделать вывод о том, что наиболее точным методом является метод Симпсона.





Скачать 339.12 Kb.
оставить комментарий
Дата02.10.2011
Размер339.12 Kb.
ТипРешение, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх