Вы на НеОфициальном сайте факультета ЭиП

На нашем портале ежедневно выкладываются материалы способные помочь студентам. Курсовые, шпаргалки, ответы и еще куча всего что может понадобиться в учебе!
Главная Контакты Карта сайта
 
Где мы?
» » » Циклические алгоритмы вычисления сумм, произведений, количеств, пределов, последовательностей

Реклама


Циклические алгоритмы вычисления сумм, произведений, количеств, пределов, последовательностей

Просмотров: 13268 Автор: admin

Сложные циклы

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

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

Пример №1. Вычисление суммы известного числа слагаемых. Пусть требуется вычислить сумму N чисел натурального ряда:

S = 1 + 2 + 3  +4 + ... + N, где N – любое наперед заданное число.

Это арифметический цикл, у которого параметром является номер слагаемого, который также определяет и значение очередного слагаемого, включаемого в сумму. Обозначим его буквой n, тогда общая формула тела цикла запишется так:

S = S + n.

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

Номер слагаемого (и его значение) n меняется в диапазоне от 1 до N  с шагом, равным 1.

Код программы примера №1.


void main (void)
{
int       n;                                 // Управляющая переменная.
int       S;                                // Сумма ряда.
int       N;                                // Число слагаемых, включенное в сумму.
printf ("Вычислю сумму чисел натурального ряда. nВведите число слагаемых>1");
scanf ("%d", &N);                 // 
S = 0;                                    // Инициализация переменной S нулем обязательна.
n = 1;                                    // К нулю готовимся прибавить первое слагаемое, = 1.
           do
           {
                      S += n;             // Тело цикла.
                      n ++;                // Приращение параметра цикла.
           } while (n <= N);
printf ("При %d слагаемых сумма = %d", N, S); // Печать результата вне цикла.
}

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

Пример №2. Организация итерационного цикла на примере алгоритма суммирования. Пусть требуется найти сумму прогрессии:

 c точностью e (например, e= 0.001).

Количество слагаемых, которое нужно включить в сумму для достижения заданной точности, неизвестно, но известно условие, определяющее точность вычислений. Зная, что предел значения очередного слагаемого стремится к нулю, с ростом n,

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


// Код программы примера №2.
void main (viod)
{
float    S;
float    eps;                            // Значение точности вычислений.
float    n;                               // Номер слагаемого, определяет также его значение,
                                             // изменяется от 1 с шагом 1
printf ("Вычислю сумму ряда. nВведите точность вычислений <1");
scanf ("%f", &eps);
n = 1;
S = 0;                                    // Входит в подготовку цикла.
           do
           {         
                       S += 1 / n;
                       n += 1;
           } while ( 1. / n  >eps);           // еps достаточно мало.
printf("Слагаемых %5.0f, Сумма %f8.5", n, S);
}

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

Пример №3. Пусть требуется вычислить сумму ряда, как и в примерах №1 и №2, но формула изменена:

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

1.       Вычислить суммы для n1, n2, n3 и так далее слагаемых (в арифметическом цикле или цикле, управляемом событием).

2.       Вычислить суммы для различных x, например, для xÎ[x0, xn] с шагом Dx.

3.       Вычислить суммы для различных степеней точности, например, для           e Π[e0en] (в итерационном цикле).

Рассмотрим случай 2. Сумма заново вычисляется для каждого значения x, поэтому цикл вычисления суммы должен быть внутренним, а цикл изменения переменной x внешним. Управляющей переменной внутреннего цикла является номер слагаемого Π[1, n], ее шаг равен 1. Число повторений должно быть известно, его можно ввести. Внешним циклом управляет переменная x, которая изменяется по закону арифметического цикла, пусть для определенности x Î [0, 1] с шагом 0,1.


// Код программы примера №3.
void main (void)
{
float    x;                                 // Параметр внешнего цикла.
float    n;                                 // Параметр внутреннего цикла.
float    S;
int       N;                                // Число слагаемых, включенных в сумму.
printf ("Вычислю сумму чисел натурального ряда.nВведите число слагаемых>1");
scanf ("%d", &N);
// Управление внешним циклом.
for (x = 0; x <= 1; x += 0.1)
           {
           // Тело внешнего цикла.
           // Управление внутренним циклом.
           S = 0;
           n = 1;
           while (n <= N) 
                       {
    // Тело внутреннего цикла.
                       S += x / n;
                       n += 1;
                       }
           printf ("При x=%6.2fсумма = %6.2fn", x, S);
           }
}

Пример №4. Использование реккурентных соотношений при вычислении последовательностей. Кстати сказать, слагаемые сумм и сомножители произведений фактически тоже образуют вычисляемые последовательности. Часто имеет смысл использовать соотношения, существующие между соседними элементами последовательности, чтобы каждое новое значение вычислять реккурентно, то есть исходя из значения, вычисленного на предыдущем шаге, например, .

Используем этот прием для вычисления значения функции S (x) в произвольной точке x по формуле разложения в ряд для 5-ти, 10-ти, 15-ти, 20-ти слагаемых, если формула задана:

 

Переменная x произвольна, и не задана в условии, ее следует ввести. Помимо собственно вычисления суммы требуется сравнить вычисленные значения для разного числа слагаемых, для чего нужно организовать сложный цикл, где внешним циклом будет обычный арифметический цикл с управлением по количеству слагаемых, включенных в сумму: N = 5, 10, 15, 20, т. е. NÎ[1, 20], шаг 5.

В теле внешнего цикла для каждого из значений количества слагаемых N номера слагаемых изменяются от 1 до N, и если дать управляющей переменной имя k, то kÎ [1, N]. Внутренний цикл имеет некоторые особенности.

1. При k = 1 начальное значение суммы S равно 0, а очередное слагаемое а не определено.

2. Во внутреннем цикле очередное слагаемое вычисляется по формуле . Функция возведения числа в степень в Си++ есть, а для вычисления факториала нет. Факториал, во-первых, растет очень быстро, и для n=10-ти и более имеет очень большие значения. Во-вторых, для его вычисления нужен циклический алгоритм. Если для вычисления слагаемого использовать реккурентное соотношение, то мы избавимся от этих двух недостатков.

Вычисление степени, это произведение . Вычисление факториала, это произведение чисел натурального ряда, . Если обозначить именем a значение очередного слагаемого, тогда последующее значение может быть вычислено по отношению к предыдущему по формуле: . Действительно, при = 1, a = x. При = 2, . При = 3,. И так далее. В теле внутреннего цикла для вычисления очередного слагаемого может быть использована именно эта формула.

3. Ряд является знакопеременным, то есть знак слагаемого отрицательный для четных слагаемых, и положительный для нечетных. Однако нет необходимости в формуле вычислений возводить (–1) в степень. Обычно для решения подобных задач вводится переменная, хранящая знак, например, переменная z принимает значения +1 или –1. Смена знака в цикле достигается присваиванием z = –z; при переходе к очередной итерации.


// Код программы примера №4.
#include <stdio.h>
#include <conio.h>
void main (void)
{
int       N;                              // Управление внешним циклом, целая переменная.
float    x;
float    k;                               // Управление внутренним циклом, вещественная
                                             // переменная, потому что участвует в вычислении.
float    a;                               // Очередное слагаемое.
float    S;                               // S – сумма.
int       z;                               // Знак слагаемого.
printf ("Введите x = n");
scanf ("%f", &x);
// Управление внешним циклом по числу слагаемых.
for (N = 5; N < 20; N += 5)
{
           k = 1;                         // Начинаем с номера 1.
           S = 0;                         // Сумма = 0.
           a = 1;                         // Для реккурентного соотношения.
           z = 1;                         // Знак слагаемого «плюс» для k = 1.
           // Управление внутренним циклом.
           while (k <= N)
                      {
                       a = a * x / k;     // Очередное слагаемое реккурентно.
                       S = S + z * a;  // Сложение с учетом знака.
                       // Переход к следующему слагаемому.
                       k += 1;
                      z = z;
                      };
           printf ("При %4.0f слагаемых cумма равна= %8.4fn",k – 1, S);
           };
}

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

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

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

Пусть требуется вычислить элементы арифметической прогрессии, если заданы первый элемент, знаменатель и число элементов. Пусть требуется вычислить элементы геометрической прогрессии, если заданы первый элемент и знаменатель. Для возрастающей прогрессии вычислять значения, пока очередной элемент не превысит 1000, для убывающей прогрессии вычислять значения, пока очередной элемент не станет меньше, чем 0,001.

В этом примере еще раз обратим внимание на использование операторов цикла. Для организации арифметического цикла логичнее использовать for, для организации итерационного цикла while или dowhile.


// Код программы примера №5.
#include <stdio.h>
#include <conio.h>
void main (void)
{
float    Ar, d_Ar;                              // Первый элемент и знаменатель.
float    Geom, d_Geom;                   // Первый элемент и знаменатель.
int       Cou_Ar;
//----- Задача 1. ----------------------------------------------------------------------------------
printf ("Введите первый элемент и знаменатель арифметической прогрессииn");
scanf ("%f%f", &Ar, &d_Ar);
printf ("Введите число элементовn");
scanf ("%d", &Cou_Ar);
// Управление первым циклом по числу слагаемых.
for (intk = 2; k <= Cou_Ar; k++)   // Номер начинается с 2.
{
           Ar = Ar + d_Ar;
           printf ("%d-й элемент равен: %6.2fn", k, Ar);
}
//------ Задача 2. ---------------------------------------------------------------------------------
printf ("Введите первый элемент и знаменатель геометрической прогрессииn");
scanf ("%f%f", &Geom, &d_Geom);
if (d_Geom > 1)
           {
           printf ("Возрастающая последовательностьn");
           k = 2;
           while (Geom < 1000)  // while, так как Geom известно.
                       {
                       Geom = Geom * d_Geom;
                       printf ("%d-й элемент равен: %6.2fn", k, Geom);
                       k++;
                       }
           }
           else
                       if (d_Geom < 1)
                                  {
                                  printf ("Убывающая последовательностьn");
                                  k = 2;
                                  while (Geom > 0.001)
                                             {
                                             Geom = Geom * d_Geom;
                                             printf ("%d-й элемент равен: %8.4fn", k, Geom);
                                             k++;
                                             }
                                  }
                                  else                 // Здесь знаменатель равен 1.
                                             printf ("Все элементы одинаковыn");
}

Пример №6. Использование операторов break и continue для циклов do, while, for. Оператор прерывания break внутри любого цикла прекращает выполнение цикла с передачей управления следующему за циклом оператору. Осуществляя выход из цикла при наступлении каких-либо обстоятельств, позволяет корректно завершить цикл. В случае вложения прерывает только непосредственно охватывающий цикл.

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

// Код программы примера №6-1.

#include <stdio.h>

void main (void)

{

int       Max, Sum = 0, k;                 // Max – наибольшее значение суммы.

printf ("\nВведите наибольшее значение\n");

scanf ("%d", &Max);

for (k = 1; ;k ++)                              // Бесконечный цикл.

{

           Sum += k;

           if (Sum > Max)                     // Условие завершения цикла.

                       break;                        // Прерывание. При выходе известно k.

}

printf ("количество элементов %d", k);

}

Оператор continue внутри любого цикла выполняет переход к следующей итерации тела цикла. Противоположен break. В любой точке цикла прервет текущую итерацию и перейдет к проверке условия завершения цикла.

Найдем сумму слагаемых вида  для x Î [–1;+1] с шагом 0,1. Особой точкой в этом ряду является точка x = 0, функция в этой точке не определена. При x = 0 вычисление выполнять нельзя, значит, это действие следует пропустить.


// Код программы примера №6-2.
#include         <stdio.h>
#include         <math.h>
void main (void)
{
float    Sum=0;
float    x;
for (x = – 1; x <= 1.1; x += 0.1) 
           {
           if (fabs (x) < 0.0001)
                       continue;                             //Если в знаменателе 0.
           Sum += 1 / x;
           }
printf ("Сумма %6.2f", Sum);
}

Пример №7. Бесконечный цикл. В тех случаях, когда управление циклом осуществляется не по событиям или условиям извне, а возникает непосредственно в теле цикла, можно использовать бесконечные циклы. Бесконечным он может быть назван только с точки зрения синтаксиса, потому что условие выхода из цикла не прописано непосредственно в операторе цикла. Содержимое тела цикла может быть произвольным, но какие-то действия внутри должны привести к тому, что процесс когда-то закончится. Прерывание и выход из цикла выполняет обычно оператор break.


while (1)
 
{
 
 
 
         // Проверка условия и выход.
 
}
 
for (; ; ;)
 
{
 
 
 
         // Проверка условия и выход.
 
}

Варианты заданий

Задание 1. Найти число π, используя произведение:

 

Точность для печати не менее 5-ти знаков. Во внешнем цикле выполнить вычисления для 50-ти, 100, 200, 400 сомножителей.

Задание 2. Найти число π, используя формулу суммы ряда:

 

Во внешнем цикле выполнить вычисления для 50-ти, 100, 200 слагаемых. Точность для печати не менее 5-ти знаков.

Задание 3. Вычислить значение полинома P(x) в произвольной точке x, если

 

Выполнить вычисления для 100 слагаемых. Во внешнем цикле составить таблицу, выводящую на экран значение полинома для х Î [-0.5; 1,1].

Задание 4. Вычислить значение функции Y(x) в произвольной точке x по формуле разложения в ряд:

  

Величину х вводить. Во внешнем цикле выполнить вычисления для 5-ти, 10, 15, 20, 25 слагаемых. Точность для печати не менее 5-ти знаков.

Задание 5. Вычислить значение суммы ряда Y(x) в произвольной точке x, если

Y(x) = Sin x + Sin 2 x + Sin 3 x + ...+ Sin n x.

Величину x вводить в градусной мере. Во внешнем цикле выполнить вычисления для 10-ти, 20, 30 слагаемых. Точность для печати не менее 5-ти знаков.

Задание 6. Вычислить значение функции Y(x) в произвольной точке x по формуле разложения в ряд:

 

Величину x вводить. Во внешнем цикле выполнить вычисления для 5-ти, 10, 15, 20 слагаемых. Точность для печати не менее 5-ти знаков.

Задание 7. Вычислить значение функции Y(x) в произвольной точке x по формуле разложения в ряд:

 

Величину x вводить. Во внешнем цикле выполнить вычисления для 5-ти, 10, 15, 20 слагаемых. Точность для печати не менее 5-ти знаков.

Задание 8. Составить программу для вычисления таблицы значений функции:

Y(x)=x×(x – 0,5)×(x – 1)×(x – 1,5)×...×(x – 5),

для x Î [0; 0,9], шаг 0,1. Параметром внутреннего цикла является величина а (в сомножителе вида х – а).

Задание 9. Вычислить значение суммы ряда

 

Во внешнем цикле выполнить вычисления для n = 5, 10, 15, 20. Один из тестовых примеров проверить вручную. Точность для печати не менее 5-ти знаков.

Задание 10. Вычислить значение суммы ряда Y(x) в произвольной точке x, если

 

Величину x вводить в градусной мере. Во внешнем цикле выполнить вычисления для 5-ти, 10, 15, 20 слагаемых. Точность для печати не менее 5-ти знаков.

Задание 11. Найти произведение n сомножителей вида:

 

Во внешнем цикле выполнить вычисления для 50-ти, 100, 200 сомножителей. Точность для печати не менее 5-ти знаков.

Задание 12. Вычислить значение функции Y(x) в произвольной точке x по формуле разложения в ряд:

 

Во внешнем цикле выполнить вычисления для 5-ти, 10, 15, 20, 25 слагаемых. Один из тестовых примеров проверить вручную.

Задание 13. Составить программу для вычисления таблицы значений функции:

Y(x) = 1+ 2×x+3×x2  +4×x3  +...+20×x19, для x Î [0; 1,2], шаг 0,05.

Задание 14. Составить программу для вычисления таблицы значений функции:

 

Отследить значение функции для числа взятых слагаемых, равного 5,10,15,20. Во внешнем цикле задать значение x Î [0; 1,2], шаг 0,2.

Задание 15. Вычислить значение функции Y(x) в произвольной точке x по формуле разложения в ряд:

 

Значение х ввести в градусной мере. Во внешнем цикле выполнить вычисления для 5-ти, 10, 15, 20 слагаемых. Точность для печати не менее 5-ти знаков.

Задание 16. Вычислить значение функции Y(x) в произвольной точке x , если

 

Выполнить вычисления для x Î [-1,1], шаг = 0,1.

Задание 17. Составить программу для вычисления суммы:

 

а) последовательно слева направо;

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

Если результаты различны, объяснить.

Задание 18. Вычислить значение суммы

S = 1×2 + 2×3×4 + 3×4×5×6 + ... + n×(n+1)×...×2n

Во внешнем цикле вычислить сумму для значений  n = 10, 20, 30, 40, 50.

Задание 19. Вычислить значение дроби

Выполнить вычисления в диалоге, чтобы можно было ввести произвольное значение n. Один из тестовых примеров проверить вручную.

Задание 20. Вычислить значение суммы:

 

Во внешнем цикле выполнить вычисления для n = 5, 10, 15, 20. Один из тестовых примеров проверить вручную. Точность для печати пять знаков.


Информация

Комментировать статьи на нашем сайте возможно только в течении 60 дней со дня публикации.

Популярные новости

Статистика сайта



Rambler's Top100



 
Copyright © НеОфициальный сайт факультета ЭиП