- •Лекция 1 Создание консольного приложения
- •2. Консоль. Построение консольного проекта
- •3. Запуск приложения
- •4. Сохранение и редактирование проекта
- •Лекция 2
- •4. Функции форматированного ввода и вывода
- •4.1. Функция форматированного ввода с клавиатуры
- •4.2. Функция форматированного вывода на экран
- •5. Математические функции
- •Лекция 3 Линейные вычислительные процессы
- •1. Алгоритм. Управляющие структуры
- •2. Линейные вычислительные алгоритмы
- •2.1. Условный оператор if()
- •2.2. Условное выражение
- •2.3. Оператор выбора switch()
- •Лекция 5 Программирование разветвляющихся вычислительных процессов
- •Лекция 6 Циклические вычислительные процессы.
- •1. Типы циклов
- •3. Операторы безусловного перехода
- •Лекция 7 Вычисление последовательностей
- •4. Примеры вычисления последовательностей
- •5. Структура алгоритмов вычисления рекуррентных последовательностей
- •Лекция 8 Одномерные массивы
- •1. Массивы
- •1.1. Примеры программ обработки одномерных массивов
- •1.2. Сортировка выбором
- •1.3. Сортировка простыми вставками
- •Лекция 10 Двухмерные массивы
- •1. Двухмерные массивы
- •Лекция 11 Алгоритмы матричной алгебры
- •1. Алгоритмы матричной алгебры
- •Лекция 12 Динамические массивы
- •1. Память компьютера. Адресное пространство
- •2. Динамическая память
- •3. Адреса и указатели
- •4. Указатели и массивы. Динамические массивы
- •5. Проблемы, связанные с указателями
- •6. Поразрядные операции
- •1.2. Способы объявления и обращения к элементам двухмерных массивов
- •Лекция 14 Символы и строки
- •1. Символьный тип данных
- •2. Строки
- •Лекция 15 Структуры
- •1. Понятие структуры
- •2. Определение нового имени типа
- •3. Массивы структур. Указатели на структуры
- •3.1. Определение статического массива структур
- •3.1. Определение динамического массива из n структур
- •Лекция 16 Файлы
- •1. Потоковый ввод-вывод данных
- •3. Понятие файла. Функции работы с файлами
- •Лекция 17 Файлы
- •Лекция 18 Функции пользователя
- •I. Приёмы построения алгоритмов
- •2. Понятие функции
- •2.1. Определение функции
- •2.2. Область видимости переменных
- •2.3. Параметры функции
- •2.4. Описание функции
- •2.5. Организация вызова функции
- •2.5. Передача параметров в функцию
- •3. Рекурсия
- •Лекция 20 Нахождение приближенного значения корня нелинейного уравнения
- •На отрезке [a;b] с заданной точностью eps
- •1.1. Метод дихотомии (половинного деления)
- •1.2. Метод хорд
- •1.3. Метод касательных (Ньютона)
- •Лекция 22 Объектно-ориентированное программирование
- •Полиморфизм – это свойство класса, позволяющее определить одно и то же по имени, но разное по смыслу действие. Основные этапы ооп:
- •Уточнённое имя принадлежит классу (т.Е. Компонентной) функции
- •Лекция 23 Объектно-ориентированное программирование
- •1. Конструкторы и деструкторы
- •1.2. Определение компонентных функций
- •Лекция 25 Объектно-ориентированное программирование
- •1. Свойства классов
- •1.1. Наследование классов
- •1.2. Полиморфизм
- •Библиографический список
Лекция 7 Вычисление последовательностей
Цели:
-
получить представление о типах последовательностей и способах их обработки;
-
освоить методику написания циклических вычислительных алгоритмов для вычисления последовательностей, перевода таких алгоритмов на язык программирования С++ и разработки соответствующего проекта в среде Visual C++ 6.0.
Циклические структуры используются для вычисления элементов рекуррентных последовательностей, обработки массивов, а также решения задач, которые предполагают использование численных методов.
4. Примеры вычисления последовательностей
-
Пусть переменная х принимает последовательно значения х1, х2, х3, … , хn, … . Такое нумерованное множество чисел называется последовательностью. Закон образования последова-тельности задается формулой n-го члена хn.
Из данного определения видно, что для задания последовательности нужно знать закон образования n-го члена последовательности, т.е. функцию, которая ставит натуральному числу n в соответствие некоторое значение f(n): xn=f(n).
-
Последовательность {xn} называется сходящейся к х*, если при n→ ∞ |x*-xn|→0.
-
Последовательность {xn} называется убывающей, если при n→ ∞ |xn|→0.
-
Последовательность {xn} называется возрастающей, если при n→ ∞ |xn|→∞.
При вычислении возрастающих последовательностей должно быть задано условие, ограничивающее вычисление элементов такой последовательности.
-
Пусть дана некоторая последовательность элемент-ов а1,а2, а3, … , аn,…, причём ак+1=F(а1, а2,… аn, ак), ак+2=F(а2,а3,...аn, ак, ак+1). Если функцию F можно определить или она задана, то последовательность а1, а2, а3, … , ак, ак+1, … называется рекуррентной последовательностью.
Формула n-го члена рекуррентной последовательности (рекуррентная формула) аn=F(an-k ,an-k+1,аn-к+2,…,аn-1), где число k называется глубиной рекурсии и определяет количество предшествующих элементов, необходимых для вычисления аn. Смысл глубины рекурсии в том, что она показывает, сколько переменных необходимо для вычисления элементов последовательности.
Примеры задач с использованием
рекуррентных последовательностей
Вычислить заданный n-й элемент последовательности.
Вычислить сумму или произведение n элементов последовательности.
Найти количество элементов на данном отрезке последовательности, удовлетворяющих определенному условию.
Найти номер первого элемента последовательности, удовлетворя-ющего определённому условию.
Пример 1. Вычислить n-й элемент арифметической прогрессии а1=1, а2=3, а3=5 и т.д.
Ход выполнения работы
-
Написание алгоритма решения задачи будет состоять из двух шагов.
Выведем рекуррентную формулу. Так как разность прогрессии равна 2, то рекуррентная формула будет следующей: . Читается формула так: при i=1 ai=1; при i≥2 ai=ai-1+2, т.е. каждый последующий элемент равен сумме предыдущего и 2.
Определим глубину рекурсии. Поскольку каждый следующий элемент вычисляется только через один предыдущий, то глубина рекурсии равна 1. Следовательно, для вычисления элементов последовательности нужны две переменные. Однако в этом случае можно обойтись одной переменной. Для определения значения последующего элемента последовательности будем использовать рекурсивную формулу
-
Алгоритм
Программа
объявление цел: а,n,i
ввод n
//текущий элемент последовательности и //его текущий номер
а=1,i=1
//вычисляем элементы последовательности
для i=2 до n шаг 1
а=а+2
всё_для i
печать а
#include "stdio.h"
#include "math.h"
int main ( )
{
int a, i, n;
printf("n=");
scanf("%i",&n);
a=1,i=1;
for (i=2;i<=n;i++)
a=a+2;
printf("a%i=%i \n",n,a);
return 1;
}
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Пример 2. Вывести на печать первые n (n≥3) чисел Фибоначчи. Распечатать все элементы и подсчитать, сколько среди них четных чисел. Числа Фибоначчи образуются по закону:
а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 если а2%2=0 //условие четности //значения переменной а2 s=s+1 все_если а1= a2 а2=а3 всё_для i печать s
|
#include "stdio.h" #include "math.h" int main ( ) { int a1, a2, a3, s, i, n; printf("n="); scanf("%i",&n); a1=1, a2=1, s=0; printf("a1=%i\n", a1); printf("a2=%i\n", a2); for (i=3;i<=n;i++) { a3=a2+a1; printf("a%i=%i \n", i, a3); if(a2%2==0) s=s+1; a1=a2; a2=a3; } printf("s=%i \n", s); return 1; } |
Примечание. В алгоритме использована рекурсивная формула
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Последовательности в примерах 1 и 2 являются возрастающими, поэтому вычисление элементов ограничивается заданием их количества.
Пример 3. Для заданных действительного x и целого n вычислить сумму .
Ход выполнения работы
-
Написание алгоритма решения задачи будет состоять из двух шагов.
Формула для вычисления суммы:
.
Здесь i обозначает номер текущего элемента последовательности, n – количество элементов последовательности, сумму которых нужно вычислить.
Глубина рекурсии в данном случае не определяется, так как данная формула не является рекуррентной.
-
Написать программу, соответствующую алгоритму6
Алгоритм |
Программа |
Объявление цел: i, n; вещ: х, s, а //ввод количества элементов ввод n ввод x //начальное значение номера элемента //последовательности i=0 //начальное значение элемента // последовательности а=sin(x)/x //начальное значение суммы элементов //последовательности s=a //цикл для вычисления элементов и суммы //последовательности для i=1 до n шаг 1 a= (-1)isini(x)/xi s=s+a всё_для i //вывод полученной суммы на экран печать s
|
#include "stdio.h" #include "math.h" int main ( ) { int i, n; float x, s, a; printf("n="); scanf("%i",&n); printf("x="); scanf("%f",&x); // инициализация переменных i=0; a=sin(x)/x; s=0; //цикл для вычисления элементов и //суммы последовательности for (i=1;i<=n;i++) { a=pow(-1,i)*pow(sin(x),i)/pow(x,i); s=s+a; } //вывод полученной суммы на экран printf("s=%f \n", s); return 1; } |
Примечание. В алгоритме использована рекурсивная формула
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Пример 4. Для заданного вещественного х и малой величины eps вычислить сумму ряда .
Ход выполнения работы
-
Написание алгоритма решения задачи будет состоять из двух шагов.
Рекуррентная формула выводится из предположения, что слагаемые ряда являются членами бесконечно убывающей геометрической прогрессии. Пусть . Таким образом, рекуррентная формула выглядит следующим образом:
,
где . Формула для берется из формулы ряда . Для нахождения формулы подставим в формулу 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). Вычислим . Получим рекуррентную формулу
.
При записи этой формулы наиболее частой ошибкой является следующая
запись этой формулы:
.
Эта формула не будет являться рекуррентной, так как в ней нет зависимости последующего элемента последовательности от предыдущего, следовательно, нет возможности применить стандартный алгоритм вычисления элементов и суммы этих элементов (описание см. ниже).
Глубина рекурсии равна 2, т.е. для вычисления элементов последовательности требуются две переменные. Как и в примере 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
#include "stdio.h"
#include "math.h"
int main ( )
{
int i;
float x, eps, a, s;
printf("x="); scanf("%f",&x);
printf("eps="); scanf("%f",&eps);
// инициализация переменных
i=0;
a=1;
s=a;
//цикл для вычисления элементов и //суммы последовательности
while (fabs(a)>=eps)
{
i=i+1;
a=a*(-x)/(2*i*(2*i+1));
s=s+a;
}
//вывод полученной суммы на экран
printf("S=%f \n",s);
return 1;
}
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.
Пример 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
#include "stdio.h"
#include "math.h"
int main ( )
{
int i;
float at, ap, eps;
printf("eps=");
scanf("%f",&eps);
i=1;
at=0.01;
printf("a%i=%f\n",i, at);
i++;
ap=pow(log(at),2)+1;
printf("a%i=%f\n",i, ap);
// цикл для вычисления элементов
//последовательности
while (fabs(at-ap)>=eps)
{
i++;
at=ap;
ap=pow(log(at),2)+1;
printf("a%i=%f\n",i, ap);
}
printf("min №=%i \n", i);
return 1;
}
-
Создать проект и реализовать данную задачу в среде Visual C++ 6.0.