Базовые алгоритмы. Лекция 8

1.

ЛЕКЦИЯ 8.
Базовые алгоритмы
подсчет количества каких либо чисел;
накопление суммы каких-либо чисел;
накопление произведения;
поиск минимального и максимального
члена последовательности.

2.

Задача 1. Алгоритм подсчета
количества( организации счетчика)
• Дана последовательность:
cos 1, cos 3, cos 5, ..., cos 99.
Определить количество положительных
членов последовательности

3.

Решение
Представим последовательность в общем виде:
а = cos(n), где п =[1..99], ∆n=2 .
• ПРАВИЛО:
Для организации счетчика в памяти компьютера выделяется
ячейка, содержимое которой должно увеличиваться на 1
каждый раз, когда встречается положительный член
последовательности.
В программе ячейке -счетчику соответствует переменная
целого типа, например переменная L.
В начальный момент содержимое ячейки должно быть равно
нулю. С этой целью предварительно осуществляется очистка
ячейки оператором присваивания L=0;
Изменение значения счетчика реализуется с помощью
оператора присваивания L=L+1;

4.

программа
#include <stdio.h>
#include<math.h>
int
_tmain()
{
float a;
int n,L; // описание переменных
L=0;
// очистка счетчика
for ( n = 1; n<= 99; n=n+2)
// запуск цикла
{
a = cos(n );
if(a>0) L = L + 1; // в теле цикла работа счетчика
}
printf(“L=%d”, L); // вывод значения счетчика
return 0;
}

5.

Задача 2. Алгоритм накопления
суммы
• Дана последовательность:
sin 2x, sin 4x, sin 6x, ..., sin 16x
x - заданное вещественное число.
• Вычислить сумму членов
последовательности, которые по модулю
больше 0.3.

6.

Решение
• Представим последовательность в общем виде:
а = sin(nx), где n =[2..16], ∆n=2 .
ПРАВИЛО:
• Для вычисления суммы в памяти компьютера выделяется
ячейка S, к содержимому которой прибавляется член
последовательности a каждый раз, когда выполняется
условие а > 0.3.
• В начальный момент ячейка для суммирования должна быть
очищена оператором S=0;.
Накопление суммы реализуется оператором присваивания
S=S+a;.

7.

программа
#include <stdio.h>
#include<math.h>
int main()
{
float a, x, S; //описание переменных задачи
int n;
printf(“Введите значение х= ”);
scanf(“%f”,&x);
S=0;
//очистка суммы
for( n = 2; n<= 16; n=n+2) // запуск цикла
{ a = sin(n*x);
if ( abs(a)>0.3) S = S + a; /* добавление числа а в сумму, если
|a|>0.3 */
}
printf(“S=%6.2f”, S); // вывод значения суммы на экран
return 0;
}

8.

Задача 3. Алгоритм накопления
произведения
• Дана последовательность:
cos 0.1, cos 0.2, cos 0.3, ..., cos 10.
• Вычислить значение: Р =|PO|, где РО произведение отрицательных членов
последовательности.

9.

Решение
• Представим последовательность в общем виде:
y = cos x, где х=[ 0.1..10]; Δх = 0.1.
• ПРАВИЛО:
Для реализации алгоритма накопления
произведения выделяется ячейка памяти РО.
В начальный момент в ячейку должна быть занесена
единица оператором РО=1;
далее осуществляется последовательное
домножение отрицательных членов
последовательности с помощью оператора
присваивания РО=РО*у;
.
.

10.

Программа
#include <stdio.h>
#include<math.h>
int
main( )
{
float х, у, Р, РО;
РО = 1;
for (x=0.1; x<=10; x=x+0.1)
{
у = cos(x);
if ( y<0) РО = РО*у //в теле цикла накопление произведения
}
Р = abs(PO);
printf(“P=%6.2f”,P);
return 0;
}
// вывод результата на экран

11.

Задача 4. Алгоритм поиска минимального
(максимального) члена последовательности
• Дана последовательность:
ak=ektg(2k + 1); к=[1..10] .
• Найти минимальный (максимальный) член
последовательности.

12.

Решение
• Для реализации алгоритма выделяется ячейка
памяти min, в которую сначала заносится
первый член последовательности.
• Затем, начиная со второго, производится
сравнение очередного вычисленного члена
последовательности с содержимым ячейки
min. Если текущий член последовательности
меньше содержимого ячейки min, то oн
переписывается в эту ячейку. В противном
случае содержимое ячейки min сохраняет
прежнее значение. При завершении
сравнения всех членов последовательности в
ячейке min остается минимальное значение.

13.

Программа поиска min
#include <stdio.h>
#include<math.h>
int main()
{
float a, min; //объявление переменных
int k;
min = +1E6;
//первое значение ячейки min
for( k=l; k<=10; k++)
{
a = exp(k)*tan(2*k + 1);
if (a<min)
min = a;
/*сравнение двух переменных а и min
и замена
содержимого min */
}
printf(“min=%6.2f”, min); // вывод содержимого ячейки min
return 0;
}

14.

• Замечание 1. Алгоритм поиска максимального члена
последовательности отличается от поиска минимального
члена лишь тем, что в ячейке (ей можно дать, например,
имя max) запоминается больший из сравниваемых
членов последовательности.
• Замечание 2. В начальный момент в ячейку min можно
занести не первый член последовательности, а
достаточно большое число, которое превышало бы
область определения сравниваемых чисел (например,
min=+1E6;).
• Замечание 3. При поиске максимального члена
последовательности в ячейку max в начальный момент
заносится, наоборот, достаточно малое число, которое
должно быть меньше всех сравниваемых членов
последовательности (например, mах= -1Е6;).

15.

Прогроамма поиска max
#include <stdio.h>
#include<math.h>
#include<conio.h>
void main()
{
clrscr();
float a, max; //объявление переменных
int k;
max = -1E6;
//первое значение ячейки max
for( k=l; k<=10; k++)
{
a = exp(k)*tan(2*k + 1);
if (a> max) max = a;
/*сравнение двух переменных а и max и замена
содержимого max */
}
printf(“min=%6.2f”, max); // вывод содержимого ячейки max
}

16.

Задача 6. Вычисление сумм
последовательностей
Последовательности с заданным числом элементов
• Пример 1. Найти сумму первых 20 элементов последовательности
S=1/2 – 2/4 + 3/8 – 4/16+…
Чтобы решить эту задачу, надо определить закономерность в изменении
элементов:
• Каждый элемент представляет собой дробь.
• Числитель дроби при переходе к следующему элементу возрастает на
единицу.
• Знаменатель дроби с каждым шагов увеличивается в 2 раза.
• Знаки перед дробями чередуются (плюс, минус и т.д.).
• Любой элемент последовательности можно представить в виде
S=z*c/d
У переменной z меняется знак (эту операцию можно записать в виде z=-z),
значение переменной c увеличивается на единицу (c++), а переменная d
умножается на 2 (d=d*2).

17.

Алгоритм решения :
• Записать в переменную S значение 0. В этой
ячейке будет накапливаться сумма;
• Записать в переменные z, c и d начальные
значения (для первого элемента): z=1, c=1,d=2;
• Сделать 20 раз следующие две операции:
добавить к сумме значение очередного
элемента;
изменить значения переменных z, c и d
для следующего элемента

18.

Программа
#include <stdio.h>
int main()
{
float S, z, c, d;
int
i;
S = 0;
z = 1; c = 1; d = 2; // Начальные значения
for ( i = 1; i <= 20; i ++ ) // запуск циклического процесса
{
S = S + z*c/d;
// добавить элемент к сумме
z = - z;
c ++;
d = d * 2;
// изменить переменные
}
printf(“Сумма S = %f”, S);
rerurn 0;
}

19.

Суммы с ограничивающим условием
• Рассмотрим более сложную задачу, когда
количество элементов заранее неизвестно.
• Пример 2. Найти сумму всех элементов
последовательности
S=1/2 – 2/4 + 3/8 – 4/16+…
которые по модулю меньше, чем 0.001.
• Поскольку мы не знаем, сколько элементов
войдет в сумму, надо использовать цикл
while
(или do - while).

20.

Один из вариантов решения
( с помощью итерационного цикла)
#include <stdio.h>
int
main()
{
float
S, z, c, d, a;
z = 1; c = 1; d = 2;
// начальные значения
S=0;
a = 1;
while ( a >= 0.001 )
// Запустить цикл и цикл будет работать, пока а≥0.001
{
a =abs( c / d);
S = S + z*a;
// добавить элемент к сумме
z = - z;
// изменить переменные
c ++;
d=d*2
}
printf(“Сумма S = %f”, S);
return 0;
}

21.

Замечания
• Цикл закончится тогда, когда переменная a
(она обозначает модуль очередного элемента
последовательности) станет меньше 0.001.
• Чтобы программа вошла в цикл на первом
шаге, в эту переменную надо записать любое
значение, большее, чем 0.001.
• Очевидно, что если переменная a не будет
уменьшаться, то условие в заголовке цикла
всегда будет истинно и программа
«зациклится».