Как составить алгоритм вычисления суммы ряда

написать алгоритм вычисления суммы ряда. Хотя бы примерно как делать. Хотя бы примерно как делать.

Ученик

(216),
на голосовании

11 лет назад

17

Рис.9. Алгоритм вычисления корней уравнения X2+B*X+C=0

Задания для самостоятельного выполнения

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

1.Для двух чисел Х,У определить, являются ли они корнями уравнения А*Р^4+D*P^2+C=0

2.Если среди трех чисел А,В,С имеется хотя бы одно четное вычислить максимальное, иначе – минимальное 3.Ввести положительное А>=1. Найти наибольшее из выражений вида 1А и SIN(A).

4.Ввести два числа . Меньшее заменить полусуммой, а большее – удвоенным произведением. 5.Ввести три числа А,В,С . Удвоить каждое из них , если А>=В>=С, иначе поменять значения А и В.

6.Определить является ли точка с координатами X,Y точкой пересечения диагоналей квадрата со стороной R ,одна вершина которого расположена в начале координат.

7.* Определить значения функции в зависимости от значения аргумента

7.ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ

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

Существуют два основных видов циклических алгоритмов: циклические алгоритмы с предусловием, циклические алгоритмы с постусловием. Они отличаются друг от друга местоположением условия выхода их цикла.

Цикл с предусловием начинается с проверки условия выхода из цикла. Это логическое выражение, например I<=6. Если оно истинно, то выполняются те действия, которые должны повторяться. В противном случае, если логическое выражение I<=6 ложно, то этот цикл прекращает свои действия.

Цикл с постусловием функционирует иначе. Сначала выполняется один раз те действия, которые подлежат повторению, затем проверяется логическое выражение , определяющее условие выхода из цикла, например, I>6

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

18

называются “телом цикла”.Разновидности циклов приведены на рис. 10а),б).

K:=K+S

+

i>6 K

i:=i+1

Рис. 10. Виды циклических алгоритмов

Классическим примером циклического алгоритма служит алгоритм для вычисления степени числа Y=Xⁿ . Этот алгоритм может быть реализован на основе операции умножения. Табличное представление такого алгоритма, отражающего зависимость У от Х при изменении показателя степени n от 1 до 3, представлено в табл.3. В этой таблице показанны также реккурентные соотношения между У и Х, определяющие как на каждом шаге зависит значение У от значения Х и от значения У, вычисленного на предыдущем шаге.

Таблица 3.Реккурентные соотношения при вычислении Y=Xⁿ

20

ции Y= SIN(X) на отрезке -15<X<15 при изменении Х на каждом шаге итерации на величину 1,5. Результатом выполнения алгоритма является циклический вывод множеств пар

(Y,X) .

Рис. 13. Циклический алгоритм табулирования функции Y =sin (X)

Задания для самостоятельного выполнения

Составить визуальные циклические алгоритмы для следующих задач.

1.Вычислить число в факториале Y=X!

2.Вычислить сумму ряда , общий член которого задан формулой An=(x*n)/n!.

3.При табулировании функции y=cos(x+a) на отрезке [1,10] c шагом h=1 определить сумму значений y , больших p.

4.Подсчитать количество цифр в целом числе Х.

5.Вычислить сумму значений функции у=x^2 на отрезке [1,5] c шагом 1.

6.* Найти минимальное значение функции Y=Sin(X)*X , на отрезке [C,D] с шагом 0.001. Реализовать цикл с постусловием.

7.Протабулировать функцию y=sin(x) на отрезке [1,5] с шагом h=0,5. Вывести предпоследнее положительное значение функции.

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

9.Составить визуальную и табличную формы алгоритма по его текстовому представлению, а также определить конечное значение S .

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

21

11.Определить является ли данный фрагмент алгоритма циклом, если да, то какого вида и какое действие является телом цикла?

22

12.* Протабулировать функцию Y=tg(X), при изменении X на отрезке [A,B] с шагом K и определить количество точек разрыва(M) этой функции.

13.Определите местонахождение ошибок в алгоритмическом решении следующей задачи. Найти минимальное значение функции Y=A*X2+Sin(X)*X0,5 , для Х изменяющемся на отрезке [C,D] с шагом 0,01.

Решение. Обозначим за Х переменную, содержащую очередное значение последовательности, за K – количество четных значений (рис. 15). Условие для выбора четных значений Х mod 2=0 (остаток приделении Х

максимальное число (Рекомендуем реализовать такой алгоритм :

Рис. 17. Алгоритм вычисления суммы положительных элементов

27

Рис.18. Алгоритм поиска максимального значения в массиве

Таблица 4. Таблица трассировки алгоритма примера 10.

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

Основным требованием при составлении алгоритмов обработки массивов является неиспользование дополнительных массивов.

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

Пример 11.Составить алгоритм решения и таблицу трассировки следующей задачи. В одномерном массиве поменять местами 2-ой нулевой элемент и последний положительный элемент. Применить нисходящее проектирование алгоритма.

Решение. Пусть одномерный массив содержит 9 элементов: (5, 0, 4, -3, -7, 0, -2, -4, 0). Среди этих элементов имеются три нулевых значения, отрицательные и положительные значения. Второй нулевой элемент имеет порядковый номер 6, а последний положительный элемент – номер 3, его значение равно 4. Если поменять местами 2-ой нулевой элемент и последний положительный в исходном массиве (5, 0, 4, -3, -7, 0, -2, -4, 0)

то получим новый массив, в котором изменен порядок следования элементов 5, 0, 0, -3, -7, 4, -2, -4, 0 . Основными операциями алгоритма будут: поиск второго нулевого элемента массива, поиск по-

следнего положительного элемента массива и перестановка найденных элементов. Отметим, что для пере-

Вывод Определение номера массива второго нулевого

элемента

КОНЕЦ

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

28

Рис. 19. Обобщенный алгоритм к примеру 11

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

Поиск второго нулевого элемента массива будем осуществлять в цикле, проверяя значение очередного элемента на 0. Если очередной элемент равен 0, то для подсчета количества таких элементов используем реккурентную формулу M=M+1. В тот момент времени, когда значение М=2, нам необходимо запомнить номер текущего элемента массива, так как это и есть искомый второй положительный элемент исходного массива. На рис.20 приведен фрагмент алгоритма, реализующего поиск второго нулевого элемента в некотором массиве А из N элементов.

Рис. 20. Фрагмент алгоритма поиска второго нулевого элемента в массиве А, состоящем из N элементов. Здесь К- номер очередного элемента, А(К) – значение

P:=K

K:=K+1

+

K=N

очередного элемента, m -количество нулевых элементов, Р- номер второго нулевого элемента в массиве

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

Рис. 21. Фрагмент алгоритма поиска последнего положительного элемента

Рассмотрим фрагменты алгоритма, приведенные на рис. 20 и 21. Можно заметить, что оба этих фрагмента выполняют поиск под управлением цикла, с одинаковым числом повторений, равным количеству элементов исходного массива N. Поэтому в итоговом алгоритме решения задачи примера 11 вместо композиции этих двух фрагментов в виде двух последовательных циклов можно использовать параллельное выполнение операций поиска под управлением одного цикла, который приведен на рис. 22.

+

S=K

K:=K+1

+

29

Рис 22. Алгоритм поиска второго нулевого и последнего положительного элементов массива А.

КОНЕЦ

Напомним, что исходный одномерный массив содержит 9 элементов: (5, 0, 4, -3, -7, 0, -2, -4, 0).По условию задачи необходимо поменять местами 2-ой нулевой элемент и последний положительный элемент.

Так как задачи поиска необходимых для перестановки элементов алгоритмически решены (рис. 22), то рассмотрим задачу перестановки элементовДля реализации перестановки найденных элементов достаточно воспользоваться управляющей структурой следования. Для того, чтобы во время перестановки не потерять переставляемые значения используем дополнительную переменную Q, временно хранящую одно из переставляемых значений элемента массива, в частности второе нулевое значение.На рис. 23 представлен универсальный алгоритм перестановки двух элементов одномерного массива, имеющих порядковые номера P и

S .

Рис.25. Алгоритм перестановки второго нулевого и последнего положительного элемента в одномерном массиве

S = 0;
for(int i = 0; i < n; i++)
  S = S + x[i];

Листинг
3.1.
Последовательный алгоритм вычисления суммы элементов массива

int[] y = new int[n];
Array.Copy(x, y, n);
int m = n;
while (m != 1)
{
    for (int i = 0, j = m - 1; i < j; i++, j--)
        y[i] = y[i] + y[j];
    m = (m + 1) / 2;
}
S = y[0];

Листинг
3.2.
Пирамидальный алгоритм вычисления суммы элементов массива

int count_p = Environment.ProcessorCount;          
          int[] y = new int[count_p];           
            int m = n / count_p + 1;
            int start = 0, finish = 0;
           for(int k =0; k < count_p; k++)
            {
               start = k * m; 
               finish =  (k+1)*m < n ? (k+1)*m : n;
               for (int i = start; i < finish; i++)
                    y[k] += x[i];               
            }
            S = y[0];
            for (int i = 1; i < count_p; i++)
                S += y[i];

Листинг
3.3.
Сегментный алгоритм вычисления суммы p процессорами

int[] y = new int[count_p];           
            for (int k = 0; k < count_p; k++)
            {               
                for (int i = k; i < n; i += count_p)
                    y[k] += x[i];
            }
            S = y[0];
            for (int i = 1; i < count_p; i++)
                S += y[i];

Листинг
3.4.
Шаговый алгоритм вычисления суммы p процессорами

double eps = 1E-15;
           double i = 1;
           double a = 1;
           double S = 0;
           while (Math.Abs(a) > eps)
           {
               //Вычисление общего члена ряда 
               a = 1.0 / ((4 * i + 1) * (4 * i - 1));   // пример 
               S += a;
               i++;
           }

Листинг
3.5.
Классический алгоритм вычисления суммы сходящегося ряда

double i = 1;
            double a = 0;
            double[] y = new double[count_p];
            for (int k = 0; k < count_p; k++)
            {
                i = k+1;
                a = 1.0 / ((4 * i + 1) * (4 * i - 1)); //начальное значение               
                while (Math.Abs(a) > eps)
                {                    
                    y[k] += a;
                    i += count_p ;
                    a = 1.0 / ((4 * i + 1) * (4 * i - 1));
                }
            }
            S = y[0];
            for (int k = 1; k < count_p; k++)
                S += y[k];

Листинг
3.6.
Шаговый алгоритм вычисления суммы сходящегося ряда p процессорами