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

    {$F+} {формирование “дальних” адресов для подпрограмм (адрес сегмента и смещения), эквивалентно директиве FAR}                                         

    FUNCTION T1 (I: INTEGER): REAL;

    BEGIN

             T1:= 1/I/I

        END;

    FUNCTION T2 (I: INTEGER): REAL;

    BEGIN

          T2:=1/I/I/I;

    END;

    {$F-} {формирование “ближних” адресов (только смещения), эквивалентно директиве NEAR}

    FUNCTION SUM (A, B: INTEGER; F: FUNC): REAL;

      <Описание функции SUM (см. выше)>

    {Основная программа:}

    BEGIN

          READLN (N);

          Z1:= SUM(1, N, T1);

          Z2:= SUM(1, N, T2);

          WRITELN (Z1, Z2)

    END.

    По умолчанию используется ключ {$F-}.

    Если при выполнении программы встретился оператор процедуры или указатель функции, то ЭВМ работает в следующем порядке.

    По  имени процедуры (функции) находится  соответствующее описание в разделе  описаний программы.

    Производится  сопоставление списка ФРП и ФКП. Должны обязательно совпадать их число и типы.

    В случае совпадения выполняется тело процедуры (функции) с фактическими параметрами.

    После работы тела процедуры (функции) осуществляется возврат в основную последовательность операторов программы:

          - к следующему оператору - после работы процедуры;

          - в точку вызова  – после работы функции.

    1.8. Массивы

    Часто в задачах бывает необходимо рассматривать  не только одиночные (скалярные) объекты (константы, переменные), но некоторую  совокупность элементов. Такой совокупностью является массив.

    Массив – пронумерованная совокупность объектов одного типа:

     ( х₁,   х₂, …, х_n), где 1, 2, …, n – номера (индексы) элементов. 

        Например, точка на плоскости характеризуется двумя координатами (х₁, х₂) : (2.5, 5), в пространстве – тремя (х₁, х₂, х₃): (3.1, 0, -2.3).

    В n-мерном пространстве вектор (точка) имеет n координат.

    Это примеры одномерных массивов. Они  имеют одну степень нумерации (один индекс).

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

     Можно рассматривать  и массивы большей размерности.         

     Пусть каждая плоскость параллелепипеда  – матрица. Тогда весь параллелепипед представляет собой трехмерный массив. В памяти ЭВМ все ячейки пронумерованы. Номером ячейки является ее адрес. Поэтому можно считать ячейки памяти одномерным массивом.

        В программе массив имеет следующее  описание:

    VAR M: ARRAY [1..5, 1..10] OF REAL;

    Переменная  M представляет собой матрицу, для которой m=5,  n=10.Границы изменения индексов должны быть заданы целыми числами.

    Любой элемент массива используется в  программе так же, как переменная, только с указанием индекса (номера), например,

          A:= M[3, 7] - 2; M[1, 1]:=0;

    Рассмотрим  несколько задач, связанных с массивами.

    Задача 1. Суммирование элементов массива

    Рассмотрим  одномерный массив А из n элементов. Для вычисляемой суммы необходимо зарезервировать некоторую переменную и перед началом вычислений занести в нее 0.

    Алгоритм вычислений:

          S:= 0;

          FOR I:= 1 TO N DO

                S:= S+A[I];

    Методом математической индукции можно доказать, что такой алгоритм действительно вычислит сумму n элементов массива.

    Задача 2. Вычисление среднего значения m массива

       . Следовательно, нужно накопленную в задаче 1 сумму разделить на N .

    Задача 3. Сформировать массив, в котором a_i = i²

          FOR I:=1 TO N DO

                A[I]:=I*I;

    С помощью массивов решаются многие задачи линейной алгебры. 

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

    (а₁, а₂, …, а_n), (b₁, b₂, …, b_n)   (длина их должна быть одинакова).

    Скалярным произведением двух векторов называется . Поэтому алгоритм можно записать следующим образом.

          S:= 0;

          FOR I:=1 TO N DO

                S:= S+A[I]*B[I];

    Задача 5. Определение суммы векторов

    Каждая  компонента вектора суммы c_i = a_i + b_i, следовательно,

          FOR I:=1 TO N DO

                C[I]:=A[I]+B[I];

    Задача 6. Вычисление произведения двух матриц

    Пусть даны две матрицы: A:= || a_ij || _m*p, и B:= || b_ij || _p*n.

    Их  произведение есть матрица 

    C:=A*B= || C_ij || _m*n, где -скалярное произведение вектора-строки с номером i на вектор-столбец с номером j. Алгоритм:

      FOR I:=1 TO M DO

            FOR J:=1 TO N DO

            BEGIN

                  S:=0;

                   FOR K:=1 TO P DO

                        S:=S+A[I,K]*B[K,J]; {вычисление одного

                                                      элемента матрицы}

              C[I,J]:=S

            END;

    Контрольные вопросы и задания

1. Дайте интуитивное  определение понятия “алгоритм”.
2. Каковы основные способы записи алгоритмов?
3. Каковы основные принципы и конструкции структурного  программирования?
4. Для исполнителя, умеющего выполнять только одну операцию на каждом шаге, опишите порядок вычисления трехчлена y=x³+bx² +c.
5. Приведите пример алгоритма, где использовался бы условный переход.

 
 
 

6. Составьте алгоритм вычисления значения функции f(n) по формуле

          если n<m/2,

                                  если n = m/2,

          если n > m/2. 

7. Составьте алгоритм вычисления суммы четных чисел  из интервала [M, N], где M и N – нечетные. Пометьте входы и выходы алгоритма.
8. В чем заключается метод пошаговой детализации при составлении алгоритмов?
9. Что представляет собой алфавит языка Паскаль?
10. Чем характеризуются объекты программы на Паскале?
11. Назовите основные операторы языка Паскаль.
12. Охарактеризуйте константы как объекты программы. Укажите интервалы значений.
13. Что представляют собой переменные как объекты программы? Дайте определение идентификатора, приведите примеры.
14. Приведите примеры описаний переменных различных типов с записью значений в виде констант.
15. Дайте определение выражения. Приведите примеры арифметических выражений. Поясните правила записи и приоритеты операций.
16. Поясните смысл оператора присваивания. Приведите примеры операторов присваивания с выражениями.
17. Приведите примеры логических выражений. Поясните правила их вычисления.
18. Что представляет собой структура программы на Паскале? Приведите примеры.
19. Как вводить данные и выводить результаты в программе на Паскале?
20. Дайте определение рекуррентной последовательности. Приведите примеры.
21. Охарактеризуйте основные задачи, решаемые на заданной рекуррентной последовательности.
22. Запишите алгоритм вычисления члена рекуррентной последовательности с заданным номером.
23. Запишите алгоритм вычисления суммы конечного числа элементов рекуррентной последовательности.
24. В чем состоит смысл задачи вычисления бесконечной суммы рекуррентной последовательности? Приведите алгоритм решения этой задачи.
25. На чем основаны приближенные методы вычисления корней функции?
26. В чем суть метода дихотомии? Запишите его алгоритм операторами Паскаля.
27. На чем основан поиск корня функции методом касательных? Приведите алгоритм.
28. Поясните смысл метода линейной интерполяции и запишите его алгоритм операторами Паскаля.
29. Как оценить трудоемкость алгоритмов отыскания корней функции?
30. Каковы основные источники ошибок в программе и в чем состоят методы борьбы с ними?
31. Каким образом можно доказать правильность алгоритма, не прибегая к тестированию? Приведите примеры.
32. Дайте определение процедуры. Какие разновидности процедур существуют в языке Паскаль?
33. В чем состоят различия в описании и вызове процедуры и функции?
34. Какова связь между формальными и фактическими параметрами процедуры (функции)?
35. Перечислите разновидности формальных параметров, поясните их смысл и приведите примеры.
36. Что называют массивами данных? Приведите примеры алгоритмов обработки массивов.

            
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                  

2. АЛГОРИТМЫ ИНФОРМАЦИОННОГО ПОИСКА

И СОРТИРОВКИ

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

    2.1. Задача поиска  и ее разновидности

    Задача  поиска состоит в отыскании в  последовательности  элемента (или  нескольких элементов) с заданными  свойствами его значения. Например, найти элемент с наибольшим (наименьшим) значением или найти элемент с заданным значением. Подобные задачи возникают очень часто при составлении алгоритмов разной сложности. Постоянно решаются они машинами в различных информационно-поисковых системах. Конечно, поиск там более сложен, чем в тех задачах, которые мы сейчас рассмотрим, но идея остается той же самой.

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

1. Найти минимальное значение элементов последовательности (все элементы разные).
2. Найти номер минимального элемента последовательности (все элементы разные).
3. Найти минимальный элемент и его номер в последовательности  с совпадающими элементами.
4. Найти номер элемента с заданным значением (все элементы разные).

    Обозначим исследуемую последовательность x₁ , x₂ , x₃ , …,x_N   и составим алгоритмы решения каждой из предложенных задач.

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

 

    Сделаем из мягкой проволоки рамку размером в любое произвольное яблоко. Таким образом, мы задались произвольным размером, который назовем эталоном. Берем следующее яблоко и пытаемся протащить его через рамку. Если оно не проходит, значит оно больше эталона. Такое яблоко нас не интересует, и мы его отбрасываем. Если же окажется, что очередное яблоко меньше эталона, то это уже претендент на наименьшее. Изменим эталон до размера этого яблока, подкрутив проволоку, и продолжим сравнение. Когда мы таким образом пропустим все яблоки через рамку, ее размер и будет размером наименьшего.