4788

Структурное программирование на языке Pascal

Лекция

Информатика, кибернетика и программирование

Структурное программирование. Основные управляющие структуры. Основные структуры данных. Методология программирования сверху-вниз. Пример: Решение системы линейных уравнений. Проектирование модулей. Модуль RAT. Оформление модуля...

Русский

2012-11-27

156.5 KB

18 чел.

Структурное программирование.

1. Основные управляющие структуры.

2. Основные структуры данных.

3. Методология программирования "сверху-вниз".

4. Пример: Решение системы линейных уравнений.

5. Проектирование модулей. Модуль RAT. Оформление модуля.

6. Итоги.

7. Упражнения.

Структурное программирование

С возникновением языков высокого уровня (конец 50-х годов) появилась возможность проектирования больших программных систем. Программирование из искусства комбинирования машинных команд, секретами которого владели избранные, превратилось в индустрию производства программного оборудования ЭВМ. К началу 70-х годов затраты на производство программ превысили затраты на производство аппаратуры. Поэтому проблема разработки эффективных и надежных программных систем стала центральной задачей информатики. Использование языков высокого уровня сняло лишь часть проблем (таких, например, как проблема распределения вычислительных ресурсов), породив одновременно новые проблемы (например, в связи с неэффективностью машинного кода, генерируемого транслятором по сравнению с кодом "ручной работы", возникла задача оптимизации). Исследования этих проблем привели, в частности, к формированию научно-обоснованного стиля программирования - структурного программирования.

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

1. Основные управляющие структуры

Рассмотрим алгоритмы решения трех задач, относящихся к различным предметным областям:

а) Алгоритм Евклида:

Program Evclid;

                   Var a, b, u, v, w: Integer;

                Begin

                   Read(a,b);

                   u := a; v := b;

                   While u <> v do begin

                      w := u - v;

                      If w > 0 then u := w else v := -w;

                    end;

                  Write(u)

               end.

б) Приближенное решение уравнения методом деления пополам:

Program EquationSol;

     Const Eps = 1e-4;

        Var a, b, u, v, w: Real;

                Begin

                  Read(a, b);

                  u := a; v := b;

                  While u - v >= Eps do begin

                     w := (u + v)/2;

                     If f(u)*f(w) > 0  then u := w  else v := w;

        end;

Write(u)

End.

в) Разделение массива на два по барьерному элементу 0:

Program Partition ;

   Const n = 16;

                      Var f, g, h : array [1..n] of Integer;

                             x, b: Integer;

                             i, j, k: Integer;

               Begin

                  { ввод массива f }

                  i := 1; j := 1; k := 1;

                  While f[i] <> 0 do begin

                     x := f[i];

                    If x > 0

                       then begin

                          g[j] := x; j := j + 1; i := i + 1 end

                       else begin h[k] := x; k := k + 1; i := i + 1 end;

                   end;

                   Write(j, k)

                End.

Программа Еvclid работает с целыми числами. Предметная область программы EquationSol - область вещественных чисел. Третья программа - Partition - обрабатывает массивы, причем тип компонент массива не имеет существенного значения. Несмотря различие в предметных областях, между этими программами существует сходство, играющее большую роль для понимания сути программирования. В самом деле, раздел операторов каждой из этих программ может быть описан так:

Begin

   < процедура ввода >;

   < последовательность простых операторов >;

   while <условие> do begin

                <оператор>;

                if <условие> then < оператор > else < оператор > ;

              end;

             < процедура вывода >

          End.

Еще более наглядно такое описание выглядит на языке блок схем:

 

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

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

К основным структурам управления относятся:

последовательное выполнение

 

 

 

 

 

ветвление

 

повторение

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

Программирование осуществляется комбинированием основных управляющих структур. Например, комбинирование ветвления и повторения приводит к блок-схеме

 

 

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

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

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

Отметим, что оператор перехода Goto не включен ни в список основных, ни дополнительных управляющих операторов. Это - не случайность. Бесконтрольное применение этого оператора приводит к тому, что программа теряет свойства, указанные выше. Поэтому структурное программирование часто называют программированием без Goto.

2. Основные структуры данных

Продолжим анализ примеров, приведенных в начале параграфа. Обратим внимание на совокупности данных, с которыми работают эти программы. Данные определены в разделах типов, переменных и констант:

 Program Evclid;

         Var a, b, u, v, w: Integer;

 

Program EquationSol;

                Const Eps = 1e-4;

                   Var a, b, u, v, w: Real;

 

Program Partition ;

                Const n = 16;

        Var f, g, h : array [1..n] of Integer;

               x, b: Integer;

               i, j, k: Integer;

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

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

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

Простые данные: целые числа, вещественные числа, символы, логические значения, данные - имена.

Способы структурирования данных: массивы, записи, файлы, множества, ссылки.

 Например, определения типов

 Word = Array [1..20] of Char;

Man = Record

             Name: Word;

             Age: Integer

             end;

Notebook = array [1..n] of Man;

означает массив из записей, первое поле которых - массив из двадцати символов, а второе - целое число.

Необходимо понимать, что связь "данные - управление" состоит не только и не столько в похожести правил их построения, сколько в ориентации структур управления на обработку структур данных. Оператор присваивания использует данные простых типов. Логические данные применяют для определения условий. Скалярные типы, определяемые программистом, используют для описания данных-индексов в массивах и селектора варианта в операторе выбора. Для обработки массивов удобно пользоваться оператором цикла с параметром, а для обработки файлов - операторами While и Repeat. Записи с вариантами естественно обрабатывать операторами варианта. Ссылочные (динамические) структуры естественным образом обрабатываются рекурсивно. Этот список можно продолжить.

3. Методология программирования "сверху-вниз"

Применение в программировании концепции структур данных и управления требует специфической методологии процесса разработки программ. Этот подход называют программированием "сверху-вниз". Суть метода - в следующем:

1. Процесс разработки программы состоит из последовательности шагов, на каждом из которых программист

уточняет структуру программы;

уточняет структуру данных.

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

3. Уточнение структуры данных состоит в определении и описании данных, обрабатываемых выбранным оператором.

4. Определение структуры данных программы начинается с описания входа-выхода, т.е. с определения структуры исходных и выходных данных.

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

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

7. Основными структурными единицами программы являются процедуры и функции. Каждую относительно самостоятельную подзадачу оформляют как подпрограмму (процедуру или функцию).

4. Пример: Решение системы линейных уравнений.

Рассмотрим пример программирования задачи, реально возникшей в работе авторов.

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

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

Вариант 1. Поле коэффициентов - поле рациональных чисел. Элемент этого поля - либо целое число A, либо несократимая дробь вида A/B, где знаменатель B - натуральное число, а числитель A - целое число. Требуется найти точное решение системы.

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

В нашем случае имеют место следующие ограничения:

Коэффициенты уравнений системы - рациональные числа;

Необходимо получить точное решение системы в виде набора рациональных чисел;

Всегда существует единственное решение системы;

Количество уравнений системы и количество неизвестных совпадают.

На первом шаге уточняем задачу в виде:

Program LinearSystem;

    Type Solution = ...;

             LinSys = ...;

     Var S: LinSys;

           X: Solution;

           n: Integer;

     Procedure SysInp(var A: LinSys);

           Begin

              {ввод системы уравнений A}

           End;

      Procedure SysSol(A: LinSys; var Y: Solution);

           Begin

             {решение Y системы уравнений A}

             End;

      Procedure SolOut(Y: Solution);

            Begin

              {вывод решения Y}

              End;

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

          SysInp(S);

          SysSol(S, X);

          SolOut(X)

       End. {конец программы LinearSystem}

На следующем шаге уточнения возникает проблема выбора метода решения и уточнения структуры данных задачи. Известным точным методом решения систем линейных уравнений является метод Гаусса последовательного исключения неизвестных. Основные шаги метода - выбор ведущего уравнения и ведущего неизвестного и исключение ведущего неизвестного из остальных уравнений системы. Учебники по линейной алгебре рекомендуют представлять данныe в виде n*(n+1) матрицы коэффициентов системы

x1

x2

.  .  .

xn

Cв. член

a11

a12

.  .  .

a1n

b1

a21

a22

.  .  .

a2n

b2

.  .  .

.  .  .

.  .  .

.  .  .

.  .  .

.  .  .

.  .  .

.  .  .

.  .  .

.  .  .

an1

an2

.  .  .

ann

bn

Поскольку параметр n зависит от задачи, для представления матрицы A в виде двумерного массива требуется резервировать память под массив некоторого наибольшего возможного размера Nmax, что приводит к неоправданным расходам оперативной памяти. Радикальное решение состоит в использовании динамических структур данных. Систему можно представить в виде списка уравнений, а каждое уравнение - списком слагаемых (членов уравнения):

LinSys = ^LS_Item; {список уравнений}

LS_Item = Record

LS_Mem : LinEqu;

   NextEqu: LinSys

         End;

LinEqu = ^EquItem; {список членов уравнения}

EquItem = Record

EquMem : Monom;

NextMem: LinEqu

       End;

Компромиссное решение - динамическое резервирование памяти под массив A:

LinSys = ^Array[1..Nmax, 1..Nmax] of Rational; {Rational - рациональные числа}

Выберем радикальный путь решения и уточним процедуры SysInp, SysSol, SolOut. Наш выбор определяет Solution как список рациональных чисел.

Procedure SysInp(var A: LinSys);

        Var i: Integer;

              P: LinSys;

      Begin {ввод системы уравнений A}

          Read(n); S := Nil;

          For i := 1 to n do begin

               Nеw(P); P^.NextEqu := S; S := P;

               {ввод i-того уравнения - списка P^.LS_Mem}

           end

       End;

 Procedure SysSol(A: LinSys; var Y: Solution);

        Begin     {решение Y системы уравнений A}

           For i ;= 1 to n do begin   {прямой ход метода Гаусса}

              -выбор уравнения, содержащего ненулевой коэффициент при Xi в качестве ведущего;

              -перестановка местами i-того и ведущего;

              For j := 1 to n do

                 If  i <> j

                   then  -исключение Xi из j-того уравнения

           end;

           For i := n downto 1 do   {обратный ход метода Гаусса}

               -вычисление Xi;

        End;

 

 Procedure SolOut(Y: Solution);

          Var i: Integer;

       Begin {вывод решения Y}

          For i := 1 to n do   {Вывод i-той компоненты решения}

          Writeln(' Задача решена ')

       End;

Следующее уточнение структуры данных состоит в определении типа Monom. Если мы решим продолжить тактику экономии памяти, можно не хранить члены уравнения вида Aij*Xi при Aij = 0. В этом случае члены уравнения представляются парой

<коэффициент, номер неизвестного>:

Monom = Record

                  Coef: Rational;

                    Unknown: Integer

      End;

Для упрощения структуры данных изменим определение типа EquItem, исключив тип Monom:

EquItem = Record

Coef: Rational;

Unknown: Integer;

NextMem: LinEqu

     End;

Теперь процедуру ввода уравнения реализуем как локальную в процедуре SysInp. Ввод уравнения - это ввод левой и правой частей уравнения, отделенных друг от друга вводом знака "=". Ввод левой части - повторение вводов членов уравнения, отделенное друг от друга вводом знака "+".

 

   Procedure SysInp(var A: LinSys);

           Var i: Integer;

                  P: LinSys;

 Procedure EquInp(Var E: LinEqu);

 Var Q: LinEqu;

      Sign: Char;

 Procedure MemInp(var R: LinEqu);

 { тело процедуры MemInp }

       Begin

Writeln('Ввод первого члена левой части');

MemInp(Q); E := Q;

Write('Нажми = или +');

Sign := ReadKey;

While Sign = '+' do begin

  Writeln('Ввод следующего члена уравнения');

  MemInp(Q^.NextMem); Q := Q^.NextMem;

  Write('Нажми = или +');

  Sign := ReadKey

end;

Writeln('Ввод свободного члена уравнения');

MemInp(Q^.NextMem); Q := Q^.NextMem;

Q^.NextMem := Nil

        End;{процедуры ввода уравнения}

       Begin {ввод системы уравнений A}

Read(n); S := Nil;

For i := 1 to n do begin

 Nеw(P); P^.NextEqu := S; S := P;

 EquInp(P^.LS_Mem}

            end

      End;

Раздел операторов процедуры SysInp приобрел законченный вид. Ввод члена уравнения оформим в виде процедуры MemInp, введя тип Rational, значениями которого являются рациональные числа.

Внимание! Введение численного типа Rational означает необходимость реализации набора процедур, обеспечивающих работу с рациональными числами. Поскольку тип Rational необходим для решения многих других задач, его следует оформить как модуль RAT и активизировать в программе директивой Uses. Принципы проектирования модуля мы рассмотрим ниже. Сейчас нам понадобятся только имена процедур ввода и вывода рациональных чисел - RatInp и RatPrint.

 Procedure MemInp(var R: LinEqu);

       Begin

New(R);

With R^ do begin

      RatInp(Coef);

       If Sign <> '='

         then Read(UnkNown)

         else UnkNown := n + 1

end

       End;

Наш алгоритм решения системы (процедура SysSol) превратит список уравнений в список пар вида <номер неизвестного, значение неизвестного>. Поэтому для вывода решения системы нет необходимости формировать список X. Достаточно установить ссылку X типа LinSys на S и вывести значение X в требуемом виде. Это означает, что тип Solution можно исключить, сделав соответствующие изменения в заголовках процедур.

 Procedure SysSol(A: LinSys; var Y: LinSys);

 Procedure SolOut(Y: LinSys);

Уточним процедуру вывода решения:

 Procedure SolOut(Y: LinSys);

          Var i: Integer;

      P: LinSys;

       Begin {вывод решения Y}

           P := Y;

           For i := 1 to n do begin

           {Вывод i-той компоненты решения }

           With P^, LS_Mem^ do begin

              Writeln('X[',i,'] = ');

              RatPrint(Coef)

           end;

           P := P^.NextEqu

       end;

       Writeln(' Задача решена ')

  End;

Мы закончили проектирование процедур ввода-вывода с точностью до средств модуля RAT. Продолжим уточнение основной процедуры программы - процедуры SysSol.

Procedure SysSol(A: LinSys; var Y:LinSys);

         Var P, Q: LinSys;

               TempRef: LinEqu;

                i: Integer;

    Begin {решение Y системы уравнений A}

        P := A;

        For i := 1 to n do begin {прямой ход метода Гаусса}

          {выбор ведущего уравнения}

           Q := P;

           While Q^.LS_Mem^.Unknown <> i do

              Q := Q^.NextEqu;

              {перестановка местами i-того и ведущего}

              TempRef := P^.LS_Mem;

               P^.LS_Mem := Q^.LS_Mem;

               Q^.LS_Mem := TempRef;

             {исключение Xi из уравнений системы}

             {1. нормализация ведущего уравнения}

             {2. исключение Xi из верхней части системы}

             {3. исключение Xi из нижней части системы}

             P := P^.NextEqu;

         end;

         Y := A;

    End;

Для выбора ведущего уравнения используется последовательный просмотр уравнений системы с помощью ссылки Q. Единственность решения системы гарантирует существование ведущего уравнения - уравнения с ненулевым коэффициентом при Xi.

Перестановка уравнений осуществляется переброской ссылок P^.LS_Mem и Q^.LS_Mem.

Основная часть алгоритма - исключение неизвестного Xi. Она состоит из шагов 1, 2, 3, выполняемых последовательно.

Шаг 1 - нормализация ведущего уравнения, т.е. деление всех членов уравнения на коэффициент при Xi.

Шаг 2 - исключение Xi из верхней части системы. j-тое уравнение верхней части (j < i) имеет вид Xj + Aji1*Xi1 + ... + Ajik*Xik = Bj, причем i1 >= i поскольку оно нормализовано и неизвестные Xk, k < i, исключены на предыдущих шагах основного цикла. Поэтому исключение осуществляется при i1 = i. Нужно домножить ведущее уравнение на Aji1 и вычесть его из j-того уравнения.

Шаг 3 - исключение Xi из нижней части системы. j-тое уравнение нижней части (j > i) имеет вид Aji1*Xi1 + ... + Ajik*Xik = Bj, причем i1 >= i. Исключение осуществляется точно также, как и на шаге 2.

Шаги 2 и 3 настолько схожи, что естественно было бы реализовать их одной и той же процедурой. Для этого необходимо всего лишь реализовать одинаковое представление уравнений из нижней и верхней частей системы, т.е. не хранить в списке уравнения верхней части системы соответствующий ведущий член Xj !

Таким образом, на выходе шага 1 - процедуры нормализации мы должны получить "хвост" Aji1*Xi1 + ... + Ajik*Xik = Bj нормализованного уравнения. Основная часть алгоритма будет выглядеть так:

{исключение Xi из уравнений системы}

{нормализация i-того уравнения и получение "хвоста"}

 EquNorm(P);

 Q := A;

 For j := 1 to n do begin

    If i <> j

    then  If Q^.LS_Mem^.Unknown = i

        {исключение Xi из j-того уравнения}

          then EquTrans(Q, P);

          Q := Q^.NextEqu

            end;

В нашей версии метода Гаусса та его часть, которую называют обратным ходом, совмещена с прямым ходом метода. Мы приводим матрицу системы сразу к диагональному виду. Заметим, что структура данных выхода процедуры SysSol изменилась: теперь i-тый член списка Y имеет вид <n + 1, значение Xi>. Процедура SysSol приобрела законченный вид. Осталось уточнить процедуры EquNorm(P) и EquTrans(Q, P), которые обрабатывают отдельные уравнения.

{нормализация уравнения и выделение "хвоста"}

 Procedure EquNorm(var P: LinSys);

          Var LCoef: Rational;

                TempRef: LinEqu;

      Begin

        TempRef := P^.LS_Mem;

        New(LCoef);

        LCoef^ := TempRef^.Coef^;   {ведущий коэффициент }

        {установка ссылки на «хвост» уравнения}

        P^.LS_Mem := P^.LS_Mem^.NextMem;

        Dispose(TempRef); {сборка мусора}

        TempRef := P^.LS_Mem;    {инициализация цикла}

        Repeat

          TempRef^.Coef := DivRat(TempRef^.Coef, LCoef);

          TempRef := TempRef^.NextMem  {следующий член}

        until TempRef = Nil;

        Dispose(LCoef)

   End {процедуры нормализации};

Наиболее интересна с точки зрения техники программирования процедура EquTrans элементарного преобразования линейного уравнения E1 c с помощью ведущего уравнения E2.

E1 := E1 - C*E2

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

E1 = A1*X + T1, E2 = A2*Y + T2, где A1*X, A2*Y - первые члены списков (головы), а T1 и T2 - хвосты списков. Возможны следующие случаи:

Случай 1. Неизвестные X и Y одинаковы. Тогда:

Если A1 - C*A2 <> 0

 то (A1*X + T1) - С*(A2*X + T2) = (A1-C*A2)*X + (T1 - C*T2)

 иначе (A1*X + T1) - С*(A2*X + T2) = (T1 - C*T2)

 Случай 2. Номер X меньше, чем номер Y. Тогда:

 (A1*X + T1) - С*(A2*X + T2) = A1*X + (T1 - C*E2)

 Случай 3. Номер X больше, чем номер Y. Тогда:

 (A1*X + T1) - С*(A2*X + T2) = (-C*A2)*Y + (E1 - C*T2)

В каждом из этих случаев правая часть соответствующего соотношения - равенства есть сумма (голова + хвост) результирующего уравнения, причем вычисление хвоста легко организовать с помощью рекурсии и чуть сложнее - итерации. Признак окончания вычислений - свободные члены в головах списков и отсутствие хвостов. Перед применением описанного алгоритма (процедура EquDiff) вычисляется множитель C и из преобразуемого уравнения удаляется первый член. Все вычисления сопровождаются "сборкой мусора" - освобождением памяти, занимаемой удаляемыми членами.

Procedure EquTrans(var Q: LinSys; P: LinSys);

        Var LCoef: Rational;

               CurP, CurQ: LinEqu;

Procedure EquDiff(var RefQ, RefP: LinEqu; C: Rational);

        Var NextP, NextQ: LinEqu;

               NextC: Rational;

   II ,JJ: Integer;

                            Finish: Boolean;

{Удаление члена уравнения с нулевым коэффициентом}

Procedure MemDel(var RefQ: LinEqu);

         Var TempRef: LinEqu;

     Begin

TempRef := RefQ^.NextMem;

RefQ^.NextMem := RefQ^.NextMem^.NextMem;

RefQ^.Coef := TempRef^.Coef;

RefQ^.Unknown := TempRef^.UnkNown;

Dispose(TempRef) {сборка мусора}

End {процедуры удаления члена уравнения};

{вставка члена уравнения}

Procedure MemInc(var RefQ, RefP: LinEqu; C: Rational);

        Var C0: Rational;

  TempRef: LinEqu;

    Begin

                    New(TempRef);

        TempRef^.Coef := RefQ^.Coef;

                     RefQ^.Coef := MinusRat(MultRat(RefP^.Coef, C));

                     TempRef^.Unknown := RefQ^.UnkNown;

RefQ^.Unknown := RefP^.Unknown;

  TempRef^.NextMem := RefQ^.NextMem;

  RefQ^.NextMem := TempRef;  RefQ := TempRef

    End {процедуры вставки члена уравнения};

Begin

     NextQ := RefQ; {указатели на голову списка}

     NextP := RefP;

     Finish := False; {признак окончания вычислений}

Repeat

       II := NextQ^.Unknown; {номера неизвестных}

     JJ := NextP^.Unknown;

    {случай 1 и случай окончания вычислений}

If II = JJ

 then begin {вычисление коеффициента уравнения}

    NextC := SubRat(NextQ^.Coef, MultRat(NextP^.Coef, C));

    If II = n + 1

        then begin {случай окончания вычислений}

            NextQ^.Coef := NextC;

            Finish := True end

        else {случай 1}

if NextC^.Num <> 0

  then begin

      NextQ^.Coef := NextC;

      NextQ := NextQ^.NextMem;

      NextP := NextP^.NextMem end

  else begin

      MemDel(NextQ);

       NextP := NextP^.NextMem end

   end

 else if II < JJ

                 then {случай 2}

                     NextQ := NextQ^.NextMem

                  else begin {случай 3}

                     MemInc(NextQ, NextP, C);

                     NextP := NextP^.NextMem end

          until Finish

       End {процедуры EquDiff преобразования уравнения};

      Begin  

        {подготовка к вызову процедуры EquDiff}

         CurQ := Q^.LS_Mem;

         CurP := P^.LS_Mem;

         New(LCoef);

         Lcoef^:=CurQ^.Coef^;

         Q^.LS_Mem :=Q^.LS_Mem^.NextMem;

         Dispose(CurQ);

         CurQ := Q^.LS_Mem;

         EquDiff(CurQ, CurP, LCoef)

     End {исключения неизвестного};

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

 

5. Проектирование модулей. Модуль RAT.

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

описание типа Rational, констант типа Rational;

процедуры ввода-вывода рациональных чисел;

функции преобразования числовых типов и типа Rational;

функции арифметических операций и сравнений рациональных чисел;

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

Проектирование начнем с определения понятия рационального числа. Рациональные числа - это дроби вида Num/Den, где Num - числитель, а Den - знаменатель. Для обеспечения корректности и единственности представления рационального числа в виде пары <Num, Den> (дроби Num/Den) потребуем выполнения следующих ограничений:

 Den > 0, НОД(Num, Den) = 1, Если Num = 0, то Den = 1

Такое представление мы будем называть канонической формой. Действия над дробями естественно и удобно реализовать в виде функций. Но функции языка Pascal возвращают скалярные значения. Поэтому представление дроби в виде записи в этом случае непригодно. Для того, чтобы обойти это чисто лингвистическое препятствие, уточним тип Rational как ссылку на запись:

Type

   Rational = ^RatValue;

   RatValue = Record

   Num, {числитель }

   Den: LongInt {знаменатель}

End;

{Тип LongInt - один из целочисленных типов в TP-6. Множество значений определено константой MaxLongInt = 231 - 1.}

Ниже описаны некоторые (далеко не все) средства RAT, необходимые для работы с рациональными числами. Ключевой функцией модуля является функция CanRat, приводящая дробь к канонической форме. В свою очередь, CanRat использует целочисленную функцию GCD, вычисляющую наибольший общий делитель (НОД) двух натуральных чисел.

A / B = A div НОД(А, В) / В div НОД(А, В)

{------------НОД двух натуральных чисел-------------------------}

Function GCD(u, v: LongInt): LongInt;

   Begin

     While (u <> 0) and (v <> 0) do

       If u > v

         then u := u mod v else v := v mod u;

         If u = 0 then GCD := v else GCD := u

     End;

{------------канонизация рационального числа--------------------}

Function CanRat(X: Rational): Rational;

      Var u, v, w: LongInt;

   Begin

        u := X^.Num; v := X^.Den;

      If  v = 0

                      then CanRat := Nil {дробь с нулевым знаменателем}

                      else begin

                          If v < 0 {знаменатель > 0}

                            then begin u := -u; v := -v end;

                            w := GCD(Abs(u), v);

  If  w <> 1

                              then {сокращение числителя и знаменателя}

                                 begin u := u div w; v := v div w end;

                                 New(R);

                                 Z^.Num := u;

                                 Z^.Den := v ;

                                 CanRat := Z;

                     end

     End;

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

{ВВОД-ВЫВОД}

 Procedure RatInp(var X: Rational);    {Ввод}

          Var Ch: Char;

       Begin

                     New(X);

                     Write('ввод числителя '); Read(X^.Num);

                     Ch := ReadKey;

                     If Ch = '/'

                       then begin

                          Write('ввод знаменателя '); Read(X^.Den);

                          X := CanRat(X)

                       end

                       else X^.Den := 1

                 End;

 

 Procedure RatPrint(X: Rational);    {Вывод}

       Begin

                    If  X = Nil

  then Write('Деление на ноль')

  else begin

     Write(X^.Num);

     If X^.Den <> 1

         then begin Write('/'); Write(X^.Den) end;

  end;

          Writeln

       End;

 

{АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ}

Function AddRat(X, Y: Rational): Rational;   {Сложение}

     Begin

       New(Z);

       Z^.Num := X^.Num*Y^.Den + X^.Den*Y^.Num;

       Z^.Den := X^.Den*Y^.Den;

       AddRat := CanRat(Z)

     End;

Function SubRat(X, Y: Rational): Rational;   {Вычитание}

     Begin

        New(Z);

        Z^.Num := X^.Num*Y^.Den - X^.Den*Y^.Num;

        Z^.Den := X^.Den*Y^.Den;

        SubRat := CanRat(Z)

    End;

 

 Function MultRat(X, Y: Rational): Rational;   {Умножение}

     Begin

        New(Z);

        Z^.Num := X^.Num*Y^.Num;

        Z^.Den := X^.Den*Y^.Den;

        MultRat := CanRat(Z)

     End;

 Function DivRat(X, Y: Rational): Rational; {Деление}

     Begin

        If Y^.Num = 0

  then DivRat := Nil

  else begin

     New(Z);

          Z^.Num := X^.Num*Y^.Den;

           Z^.Den := X^.Den*Y^.Num;

             DivRat := CanRat(Z)

end

        End;

 Function MinusRat(X: Rational): Rational; {число со знаком минус}

     Begin

        New(Z);

        Z^.Num := -X^.Num;

        Z^.Den := X^.Den;

        MinusRat := Z

     End;

{СРАВНЕНИЯ}

 Function EquRat(X, Y: Rational): Boolean; {Равенство}

     Begin

         EquRat := (X^.Num = Y^.Num) and (X^.Den = Y^.Den)

      End;

 

Function GrtRat(X, Y: Rational): Boolean; {Сравнение на "больше"}

   Begin

                   GrtRat := SubRat(X, Y)^.Num > 0

                  End;

{ПРЕОБРАЗОВАНИЯ ТИПОВ}

  Function RatReal(X:Rational): Real; {Рациональное в вещественное}

     Begin

         RatReal := X^.Num/X^.Den

       End;

Function IntRat(X: LongInt): Rational; {Целое в рациональное}

     Begin

                   New(Z);

                   Z^.Num := X; Z^.Den := 1;

                   IntRat := Z

      End;

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

A/B + C/D = CanRat((A*D + B*C)/(B*D))

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

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

Еще один путь повышения эффективности - уменьшение среднего количества вызовов функции CanRat в функциях модуля. В функции AddRat, например, это можно сделать, рассмотрев наряду с общей формулой сложения ее частные случаи, в которых вызов CanRat не нужен. Попутно уменьшается и количество арифметических операций. В самом деле, при определении сложения выделим частные случаи сложения дроби и целого числа, а также дробей с равными знаменателями

  A/B + C/D = CanRat((A*D + B*C)/(B*D)); (*)

  A/B + C/B = CanRat((A + C)/B);

  A/B + C = (A + B*C)/B;

  A + C/D = (A*D + C)/D

Функция AddRat, реализованная в соответствии с этим определением, в среднем эффективнее, чем описанная в модуле.

 Оформление модуля.

В системе программирования TP-6 наряду со стандартными модулями можно применять и собственные модули. Модуль содержит: заголовок модуля, интерфейсную часть, реализационнуя часть и инициализационную часть.

Заголовок модуля имеет вид:

Unit < Имя модуля >.

Имя модуля должно совпадать с именем файла, содержащего этот модуль.

Интерфейсная часть имеет вид:

Interface

 <

Описания констант, меток, типов и переменных, доступных для для использования внешними программами;

Заголовки процедур и функций, доступных для использования внешними программами;

Uses-директивы с именами модулей, доступных для использования внешними программами.

>

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

Реализационная часть имеет вид:

Implementation

 <

Описания всех средств модуля, скрытых от внешних программ;

Uses-директивы с именами модулей, используемых в этом модуле и скрытых от внешних программ;

Полные описания всех процедур и функций модуля.

>

Инициализационная часть - раздел операторов модуля. Он выполняется перед выполнением внешней программы, использующей модуль. Во внешнюю программу модуль включается директивою Uses.

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

{заголовок модуля}

Unit RAT; {<RAT.pas>}

Uses CRT;

{интерфейсная часть}

Interface

     Type

        Rational = ^RatValue;

                   RatValue = Record

                                        Num, {числитель }

                                        Den: LongInt {знаменатель}

     End;

Procedure RatInp(var X: Rational);

Procedure RatPrint(X: Rational);

Function AddRat(X, Y: Rational): Rational;

Function SubRat(X, Y: Rational): Rational;

Function MultRat(X, Y: Rational): Rational;

Function DivRat(X, Y: Rational): Rational;

Function MinusRat(X: Rational): Rational;

Function EquRat(X, Y: Rational): Boolean;

Function GrtRat(X, Y: Rational): Boolean;

Function RatReal(X:Rational): Real;

Function IntRat(X: LongInt): Rational;

{реализационная часть}

Implementation

      Var Z: Rational;

 {полные описания всех процедур и функций модуля}

{Инициализационная часть}

Begin

  ClrScr;

  Writeln(' Модуль Rat v.0.0 ')

End.

 6. Итоги.

Подведем некоторые итоги проектирования программы LinearSystem. В процессе проектирования "сверху-вниз" мы выделили четыре уровня программы: уровень системы, уровень уравнения, уровень члена уравнения, уровень коэффициентов. С точки зрения управления вычислениями это означает построение иерархии процедур:

 

{Процедуры SysOut, EquOut, MemOut использовались для отладки и в тексте не описаны.}

С точки зрения данных это означает построение иерархии типов данных и соответствующей иерархической структуры данных:

 

Типы:   LinSys  LinEqu     {Monom}   Rational

Структура данных:

       EquMem

S    LS_Mem    NextMem

     Unknown

      NextEqu    Coef 

{Тип Monom и поле EquMem было решено явным образом не вводить, поскольку на этом уровне структура данных достаточно проста.}

Построение программы как четырехуровневой иерархии обусловлено иерархией математических абстракций, используемой в математической теории систем линейных уравнений:

Система -> Уравнение -> Член уравнения -> Коэффициент

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

Проектирование модуля RAT представляет из себя отдельную задачу - задачу из другой предметной области. Заменив модуль RAT, например, модулем COMPLEX, в котором реализованы действия с комплексными числами, мы получим программу решения системы линейных уравнений с комплексными коэффициентами. С другой стороны, наличие модуля RAT позволяет легко программировать и другие задачи, требующие действий с рациональными числами.

7. Упражнения.

 1.Реализовать все функции арифметических действиий модуля RAT в соответствии с определениями. аналогичными определению (*) функции AddRat.

2.Используя модуль RAT и представление системы линейных уравнений в виде n*(n+1) матрицы, реализованной как двумерный массив, реализовать другую версию задачи решения системы линейных уравнений.

3.Реализовать модуль COMPLEX как расширение типа REAL. Подключить этот модуль вместо RAT к программе LinearSystem и модифицировать эту программу для решения систем линейных уравнений с комплексными коэффициентами.

4.Реализовать модуль COMPRAT как расширение типа Rational. Использовать этот модуль вместе c RAT для модификации программы LinearSystem, которая решает системы линейных уравнений с комплексными рациональными коэффициентами.


Ввод

Инициализация

Оператор

Условие

Оператор

Оператор

 Условие

фрагмент 1

фрагмент 2

Оператор 1

Оператор 2

 Условие

 Условие

 Оператор

Оператор

Оператор

 Условие

 Условие

Основная программа

 LinearSystem

Процедура SysInp

Процедура SysSol

роцедура SolOut

Процедура  SysOut

Процедура EquInp

Процедура EquDiff

Процедура EquNorm

Процедура EquOut

Процедура MemInp

Процедура MemDel

Процедура MemInc

Процедура MemOut

Средства модуля RAT

  

 Num     Den


 

А также другие работы, которые могут Вас заинтересовать

66066. Национальные и региональные инвестиционные проекты РФ. Инвестиционные программы Омска 45.83 KB
  Согласно действующему законодательству инвестиционная деятельность на территории РФ может финансировать за счет: собственных финансовых ресурсов и внутрихозяйственных резервов инвестора (прибыль, амортизационные отчисления, денежные накопления и сбережения граждан и юридических лиц...
66067. Всемирный банк 38.27 KB
  В настоящее время под Всемирным банком фактически понимают две организации: Международный банк реконструкции и развития Международная ассоциация развития В разное время к ним присоединились созданные для решения задач Всемирного банка ещё три организации...
66068. Бюджетный дефицит в период до 1990 года 34.5 KB
  Падение объема производства естественно привело к сокращению доходной базы бюджета. Уклонение от налогов в условиях несовершенства налогового законодательства и существующего в обществе отношения к обязательности налоговых платежей...
66069. Бюджетный дефицит в зарубежных странах 32.5 KB
  Бюджетный дефицит в США Дефицит федерального бюджета США в 20112012 финансовом году завершившемся 30 сентября с. По сравнению с прошлым финансовым годом дефицит бюджета сократился на 16 в 2010-2011 финансовом году он составлял 1299 трлн долл.
66070. Инвестиционные и кредитные рейтинги РФ и регионов 161 KB
  Распределение российских регионов по рейтингу инвестиционного климата в 2010-2011 годах: Максимальный потенциал минимальный риск 1 10 Московская область 29 г.Санкт-Петербург 32 Краснодарский край Средний потенциал минимальный риск 2 1 Белгородская область...
66072. Негосударственный пенсионный фонд (НПФ) 40 KB
  Негосударственный пенсионный фонд (НПФ) — особая организационно-правовая форма некоммерческой организации социального обеспечения, исключительными видами деятельности которой являются...
66073. Ипотека. Ипотека с государственной поддержкой 66 KB
  Его обязательством перед кредитором является погашение кредита а обеспечивает исполнение этого обязательства залог недвижимости. Недвижимость приобретенная с помощью ипотеки является собственностью заемщика кредита с момента приобретения.
66074. Глобализация финансов 124.69 KB
  Вследствие финансовой глобализации национальные экономики становятся особенно уязвимы к потрясениям мировой финансовой системы основанной на необеспеченных реальными активами долларах США. Кроме того монетаристская основа денежной политики финансовых властей...