Лабораторная работа №6
Тема: Итерационные и рекурсивные алгоритмы. Организация итерационных циклов.
Цель работы: Приобрести навыки разработки простых рекурсивных и итерационных алгоритмов. Закрепление конструкций базовых структур циклов.
Литература: И.Г. Семакин, А.П. Шестаков Основы программирования: М.: Мастерство,2002
Краткие теоретические сведения.
Из курса математики известно понятие рекуррентной последовательности. Это понятие вводится так: пусть известно K чисел a1, a2,….,ak. Эти числа являются первыми числами числовой последовательности. Следующие элементы данной последовательности вычисляются так ak+1=F(a1,…,ak); ak+2=F(a2,…,ak+1); ak+3=F(a3,…,ak+2); Формула вида ai=F(ai-1,ai-2…,ai-k);называется рекуррентной формулой.
Рекуррентная последовательность -это бесконечный ряд чисел, каждое из которых, за исключением K-начальных, выражается через предыдущие.
Примерами рекуррентных последовательностей являются арифметическая и геометрическая прогрессии. С рекуррентными последовательностями связаны задачи в которых не требуется одновременно хранить в памяти множество элементов числового ряда. В таком случае его элементы могут получаться последовательно в одной переменной, сменяя друг друга.
Итерационным вычислительным процессом называется такой циклический процесс, который продолжается до тех пор, пока разность между соседними, уточняемыми на каждом шаге цикла (итерации) значениями, не окажется меньше или равной некоторой заданной величине.
Решение об окончании вычислений принимается тогда, когда результаты счета(значение функции, искомые величины) на очередной итерации (цикле) отличаются от предыдущих или эталонных не более, чем на некоторую, наперед заданную, величину (ξ – эпсилон), т.е. найдены с заданной точностью.
Второй особенностью итерационного процесса является то, что результаты вычислений очередного выполнения цикла используются как исходные данные при следующем выполнении цикла, т.е. решение находится последовательными приближениями, путем уточнения на каждом шаге.
Такой подход чаще всего применяется при решении задач, требующих вычисления суммы ряда. Известно, что сумма степенных и тригонометрических рядов (бесконечного) имеет конечное значение, поскольку они представляют собой убывающую последовательность чисел стремящихся к нулю, то суммирование нужно производить до первого слагаемого, по абсолютной величине не превышающего эпсилон. Не трудно видеть, что между элементами данной последовательности имеется рекуррентная зависимость. Её можно найти интуитивно, но можно и вывести формально. авляют собой убывающую последовательность чисел стремящихся к нулю, то суммирование нужно производитьдо первого элементов числ
Рассмотрим пример алгоритма вычисления суммы ряда 
Определим, что сумма ряда вычисляется по формуле S:=S+y, где Y- каждое новое слагаемое.
; 
; 
Если учесть, что начальное значение S=1; Y=1;i:=1, то в цикле с предусловием получим следующее:
while (fabs(y) >= EPS)
{
y=y*x/i;//здесь соответственно формула }
s=s+y;
printf(“ %d %8.4f %8.4f “, i,y,s);// здесь выводится на экран значение I, Y,S}
i=i+1; {увеличивается i на единицу, переход к расчету след.слагаемого}
}
Текст программы приведен ниже. Для вычисления любой другого числового ряда нужно вывести рекуррентную формулу, и определить исходные значения перед циклом WHILE. В остальном текст программы остается без изменения.
#include <stdio.h>
#include <conio.h>
#include <math.h>
void main()
{
const float eps=0.001;
float x,s,y,p,k;
int i,m;
clrscr();
printf(“x=”);scanf(“%f%”,&x);
i=1; y=1; s=1;
printf(“ i y s “);
while (fabs(y) >= EPS)
{
y=y*x/i;
s=s+y;
printf(“ %d %8.4f %8.4f “, i,y,s);
i=i+1;
}
printf(“s=% 8.4f”,s);
printf(“exp(X)=%8.4f”,exp(x));
getch();
}
Рассмотрим следующий числовой ряд:
x=1.5, E=10-4
Выпишем слагаемые Y:
; 
; 
; 
Порядок выполнения работы:
1. Получить допуск к работе у преподавателя.
2. Осуществить вызов системы TURBO C
3. Ввести текст программы.
4. Записать исходный модуль в файл на диске
5. Провести отладку программы. Выполнить программу, провести анализ результатов и, убедившись в правильности решения, предъявить их преподавателю для проверки.
6. Занести результаты расчета в отчет
7. Выйти из системы TURBO C
Содержание отчета:
1. Цель работы
2. Задание к практической работе
3. Блок-схема алгоритма решения задачи
4. Текст программы на языке C.
5. Запись команд сеанса работы.
6. Результаты расчетов.
7. Ответы на контрольные вопросы
8. Вывод по результатам проделанной работы
Контрольные вопросы
1. Что такое итерационный цикл, число итераций, сходимость итерационного цикла? Основные отличия итерационного цикла от конечного.
2. Взаимосвязь понятий итерация и рекурсии, итерационного и рекурсивного алгоритмов.
3. Организация итерационных циклов с использованием базовых структур(с предусловием, с пост условием)
4. Чем определяется выбор базовой структуры при построении итерационных алгоритмов?
5. Как средствами алгоритмического языка организовать итерационный цикл?
Задание к лабораторной работе
Вычислить на ЭВМ значение суммы членов бесконечного ряда с заданной точностью и значение суммы, определяемое пределом суммы ряда (по формуле). Напечатать значения сумм и число циклов ряда, вошедших в сумму.
1)
2)
3)
4)
5)
x=1.5, E=10-4
6) 
7) 
8) 
9) 
10) 
11) 
12) 
13) 
14) 
15)
Дата добавления: 2015-10-21; просмотров: 102 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| | |