Программирование на ЭВМ

         CHAR. Данные этого типа записываются без апострофов и без пробелов.

    VAR C, D: CHAR;

                READ (C, D);   C := ‘A’;

                                              D := ‘+’;

A

+

    Вывод данных осуществляется с помощью процедуры вывода, обращение к которой имеет вид:

                WRITE (<список значений>);

    Список  вывода содержит имена переменных, выражения и константы. Например, WRITE (X, 29);

    Значения  из списка последовательно выводятся  на экран дисплея или на принтер (печатающее устройство).

    Вывод – другое средство общения программы с внешним миром.

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

    Пример.

          PROGRAM P (INPUT, OUTPUT);

          VAR A, B, X: REAL;

          BEGIN

                WRITE (‘Введи A’);

                READ (A);

                WRITE (‘Введи B’);

                READ (B);

                X := A*B-A;

                WRITE (‘X=’,X);

          END.

    Значения  выводятся в той форме, в какой  они описаны, например,

    - 2.300000Е+05 - для вещественных чисел.

    Для удобства чтения можно указать формат выводимых данных:

          WRITE (X:2);  - для целых,

          WRITE (Y:10:2);           - для вещественных (10 – общее количество цифр, 2 – количество цифр в дробной части).

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

    WRITELN (<список вывода>);

    Оператор  осуществляет переход к новой  строке после печати значений списка.

    1.4. Рекуррентные алгоритмы

    Известно, что далеко не все математические задачи имеют точное аналитическое решение. Гораздо большее число задач можно решить приближенно с помощью численных алгоритмов. Численными называют алгоритмы, оперирующие приближенными числами (то есть объектами типа REAL).

    Большое количество численных алгоритмов основано на рекуррентных последовательностях (то есть связано с вычислением рекуррентных последовательностей).

    Рекуррентная  последовательность – это такая  бесконечная числовая последовательность x₀, x₁, …, x_n, … , что

      x_i = f (i, x_i-1, x_i-2, … , x_i-p) для i ≥ p

          x₀ = a₀, задание рекуррентной

          x₁ = a₁, последовательности

          …… ,

          x_p-1 = a_p-1

    Например, если p = 1, то получим последовательность

      x_i = f (i, x_i-1),  i ≥ 1,

          x₀ = a_0.

    Если  задана рекуррентная последовательность, то на ней можно сформулировать некоторые задачи.

        Задача 1. Вычисление  N-го элемента последовательности.

    Для простоты рассмотрим случай, когда  p = 1.

    N – номер элемента (должен быть задан).

    I – номер очередного элемента.

    I, N – целые.

    Схема алгоритма будет следующая:

    X := A0;

    I := 1;

    WHILE I<=N DO

          BEGIN

                X := f (I, X);

                I := I + 1;

          END;

    Чтобы дойти до N-го элемента, цикл проработает N раз.

 

     Задача 2. Вычисление суммы  конечного числа  элементов рекуррентной последовательности:

    Процесс вычисления суммы можно представить  как процесс нахождения члена S_N рекуррентной последовательности:

    S₀ = 0;

    S_{i =} S_i-1 + x_i = f₁(i, S_i-1 ),  1 ≤ i ≤ N 

    Тогда получим следующий алгоритм.

    S := 0;

    I := 1;

    X := a0;

    WHILE I <= N DO

          BEGIN

                S := S + X;

                X := f (I, X);

                I := I + 1;

          END;

    Если  мы знаем, сколько раз должен проработать цикл, можно использовать другой оператор цикла: FOR. Его общая запись:

FOR I := <начальное значение> TO <конечное значение> DO (с шагом 1) или

FOR I := < конечное значение > DOWNTO < начальное значение > DO (с шагом -1).

    Задача 3. Вычисление бесконечных  сумм:

    

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

    

    Иногда  с помощью таких сумм вычисляют  функции. Например:

    

    Такое представление функции называется её разложением в ряд.

    Любое вещественное число можно представить  с помощью конечного числа  цифр, то есть всегда приближенно. Следовательно, и бесконечную сумму можно  вычислить только приближенно, с заданной точностью. Ограничимся конечным числом элементов суммы. Для нахождения критерия окончания вычислительного процесса используем тот факт, что при увеличении номера i эти элементы убывают по абсолютной величине. Поэтому одним из распространенных критериев является следующий: включать в сумму только те члены последовательности, которые по модулю больше или равны некоторой наперед заданной величине ε.

    Тогда

    

    , где N – таково,  
 

что   
 

    Таким образом, сумма всех отброшенных  элементов будет либо меньше, либо ненамного больше ε.

    Часто в таких суммах можно последующий  элемент вычислить с помощью предыдущего. Тогда нужно выразить (i+1)-й через i-й или i-й через       (i-1)-й, а не считать непосредственно каждый элемент.

    Пример  для е^t.

      

    то  есть       - формула пересчета.

    Тогда алгоритм запишется следующим образом.

    S := 1; I := 1; T:=1; x:=1;

    WHILE  ABS (x) >= Eps   DO

          BEGIN

            x := x * T / I;

            S := S + x;

            I := I + 1;

          END;

    Подумайте над следующим вопросом. Почему для вычисления бесконечных сумм нельзя использовать цикл типа FOR?

    Для самостоятельной тренировки вычислите  значения по формулам:

    

     1.5. Алгоритмы нахождения корней функции

    Корнем  функции f(x) является решение уравнения f (x) = 0. На практике в редких случаях можно записать в явном виде x как некоторую функцию g от коэффициентов уравнения.

    Однако  почти всегда мы можем решить задачу приближенно, численными методами. Это можно сделать практически для любой функции. Предположим, что приближенное значение корня известно. Это точка С₀ (рис.1.1). 

 

Рис. 1.1– Численное нахождение корня функции 

    Задача  численного нахождения корня состоит  в том, чтобы из данной точки С₀ найти более точное  значение  C_n,  построив  определенным   образом последовательность шагов. При этом мы должны быть уверены, что точное значение корня будет лежать в области C_n±d ( значение d известно). Если d достаточно мало, то точность можно считать удовлетворительной. Рассмотрим наиболее распространенные методы нахождения корней функции. 

                 Метод дихотомии  (деления отрезка  пополам) 

    Для реализации метода кроме начального приближения C₀ должна быть задана величина d₀ такая, что в отрезок [C₀-d₀, C₀+d₀] корень попадает заведомо (рис.1.2). 
 
 
 
 
 

      
 
 
 
 
 
 
 
 

    Рис.1.2 – Метод дихотомии 

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

    С₀, С₁, …, С_i, …

      d₀, d₁, …, d_i, …

    Критерием перехода к новой точке является результат анализа: пересекает ли график функции f (x) ось абсцисс левее или правее предыдущей точки.

    И тогда

    

    если  правее; 

    если  левее. 
 

    Чтобы выяснить это обстоятельство, вычислим f (C₀) и f (C₀+d₀), а потом сравним их знаки. Если эти знаки одинаковы, то график проходит через ось Х левее точки C₀, если разные, то между C₀ и C₀+d₀.

    Формально проверку можно провести следующим образом:

    f (C₀)*f (C₀+d) > 0  - знаки одинаковые,

    f (C₀)*f (C₀+d) < 0  - знаки разные,

    f (C₀)*f (C₀+d) = 0  - корень найден (случай редкий, рассматривать

                                                   не будем).

    Тогда рекуррентные последовательности для C_i и d_i:

    

    если f (a_i-1)*f (a_i-1 + d_i-1) < 0 ; 

    иначе; 
 
 
 
 

    где С₀, d₀ – заданы.

    Один  из критериев окончания вычислительного  процесса состоит в следующем. Нужно задать некоторое малое число ε и считать корень найденным, когда абсолютная величина d_i станет меньше ε. Таким образом, число ε – заданная точность нахождения корня с помощью нашего приближенного метода. Возможны другие критерии.

    Алгоритм  нахождения корней методом дихотомии.

    READ (C, D, EPS);

    A:=F (C); B:=F(C+D);

    WHILE D>=EPS DO

    BEGIN

            D:=D/2;

            IF A*B<0 THEN C:=C+D;

            ELSE BEGIN

                C:=C-D;

                B:=A;

                END;

            A:=F(C);

    END;

    Если  функция имеет несколько корней, то есть на отрезке 2d график несколько раз пересекает ось Х, то метод позволяет найти один корень. Метод работает довольно медленно, но сходится всегда. 

                        Метод Ньютона  (метод касательных)