Логическая структура программы

Процедурно-ориентированное программирование. Пример

Постановка задачи

Заполнить разными случайными целыми числами квадратную матрицу порядка 2n из заданного диапазона значений от beg по fin. В этой матрице отсортировать строки в заштрихованной части по возрастанию, остальные элементы заполнить 0 (рис. 19.1).

Рис. 19.1. – Постановка задачи

Логическая структура программы

Рис. 19.2. – Логическая структура программы

Предлагается задачу разбить на 5 подзадач:

- ввод диапазона значений для заполнения;

- заполнение матрицы разными целыми случайными числами равномерно распределенными в заданном диапазоне;

- вывод на экран матрицы;

- сортировка заштрихованной части матрицы;

- заполнение нулями не заштрихованной части матрицы.

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

Предложенная логическая структура программы приведена на рис. 19.2.

Разработка подпрограммы vvdiap

Спецификация

1. Назначение: ввод и контроль за правильностью ввода диапазона значений элементов двумерного массива (результат истина при правильно заданном диапазоне значений).

2. Имя: vvdiap

3. Вид: функция

4. Перечень параметров:

Таблица 19.1. Перечень параметров

Статус	Назначение	Имя	Тип	Вид
Выход	Начало диапазона значений	beg	integer	параметр-переменная
Выход	Конец диапазона значений	fin	integer	параметр-переменная
Возвращаемый результат	Результат проверки правильности ввода диапазона	vvdiap	boolean	-

5. Заголовок подпрограммы:

function vvdiap(var beg,fin:integer):boolean;

 

Метод решения

1) Получаем от пользователя границы диапазона

2) Если диапазон содержит значений больше, чем количество элементов в массиве, то результат функции истина, что означает – диапазон задан верно, в противном случае результат функции – ложь.

Текст функции

{ввод диапазона значений}

function vvdiap(var beg,fin:integer):boolean;

begin

writeln('Начало и конец диапазона значений?');

readln(beg,fin);

if fin-beg+1>=4*n*n

then vvdiap:=true

else vvdiap:=false

end;

Разработка подпрограммы zapoln

Спецификация

1. Назначение: заполнение двумерного массива, содержащего 2*n строк и 2*n столбцов, разными целыми случайными числами из диапазона от beg по fin. Контроль за правильностью ввода диапазона значений элементов двумерного массива

2. Имя: zapoln

3. Вид: процедура

4. Перечень параметров:

Таблица 19.2. Перечень параметров

Статус	Назначение	Имя	Тип	Вид
Вход	Начало диапазона значений	beg	integer	параметр-значение
Вход	Конец диапазона значений	fin	integer	параметр-значение
Выход	Двумерный массив разных целых случайных чисел из заданного диапазона	a	t2n	параметр-переменная-

Примечание: тип t2n и поименованные константы n, mдолжны быть определены до текста подпрограммы

type t2n=array[1..2*n,1..2*n] of integer;

5. Заголовок подпрограммы:  procedure zapoln(beg,fin:integer; var a: t2n);

Метод решения

Формируем все элементы массива. Для этого перебираем все индексы (по строкам и столбцам) - "i:=1(1)2n: "j:=1(1)2n:

Для каждого формируемого элемента (очередной формируемый элемент располагается в строке i и столбце j):

1) устанавливаем флаг (признак) существования значения в массиве в истину

2) пока существует очередное сгенерированное случайное значение в массиве (признак имеет значение истина) повторяем:

а) формируем новое целое случайное значение в интервале от beg по fin, используя формулу

x:=round(random*(fin-beg)+beg);

б) сбрасываем флаг существования значения в массиве (признаку присваиваем значение ложь);

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

" ii:=1(1)i-1:

" jj:=1(1)2n:

Если очередной проверяемый элемент совпадает со сгенерированным значением х, то устанавливаем флаг существования значения в массиве (признаку присваиваем значение истина)

если a[ii,jj]=x => pr:=true;

г) после этого отдельно проверяем i-ую строку массива, так как она заполнена не полностью, а только по j-1 столбец:

" jj:=1(1)j-1:

если a[i,jj]=x => pr:=true

3) завершение цикла пока говорит о том, что последнее сгенерированное случайное значение х не существует в заполненной части двумерного массива, заносим это значение в очередной формируемый элемент массива a[i,j]:=x

Информационная модель

  Таблица 19.3. Информационная модель

Назначение	Имя	Тип
Индекс строки формируемого элемента	i	integer
Индекс столбца формируемого элемента	j	integer
Индекс строки массива при проверке существования значения	ii	integer
Индекс столбца массива при проверке существования значения	jj	integer
Очередное случайное значение	x	integer
Флаг (признак) существования значения	pr	Boolean

Текст процедуры

procedure zapoln(beg,fin:integer; var a: t2n);

var i,ii,j,jj,x:integer;

pr:boolean;

begin

for i:=1 to 2*n

do for j:=1 to 2*n

do begin

     pr:=true;

     while pr

     do begin

          x:=round(random*(fin-beg)+beg);

          pr:=false;

          for ii:=1 to i-1

          do for jj:=1 to 2*n

             do if a[ii,jj]=x

                then pr:=true;

          for jj:=1 to j-1

          do if a[i,jj]=x

             then pr:=true

        end;

     a[i,j]:=x

   end;

end;

Спецификация

1. Назначение: вывод на экран двумерного массива, содержащего 2*n строк и 2*n столбцов целых чисел

2. Имя: vivod

3. Вид: процедура

4. Перечень параметров:

Таблица 19.4. Перечень параметров

Статус	Назначение	Имя	Тип	Вид
Вход	Двумерный массив целых чисел	a	t2n	параметр-переменная

Примечание: тип t2n и поименованная константа n должны быть определены до текста подпрограммы

type t2n=array[1..2*n,1..2*n] of integer;

5. Заголовок подпрограммы: procedure vivod(var a:t2n);

Метод решения

Перебираем строки двумерного массива " i:=1(1)2 n:

Для каждой строки:

1) выводим очередную i строку. Для этого перебираем все столбцы строки и выводим на экран очередной элемент (без перевода курсора в начало следующей строки экрана):

                                         " j:=1(1)2 n: вывод(a [ i, j ])

переводим курсор на экране в начало следующей строки (обращаемся к процедуре writeln без параметров)

Информационная модель

Таблица 19.5. Информационная модель

Назначение	Имя	Тип
Индекс строки	i	integer
Индекс столбца	j	integer

Текст процедуры

procedure vivod(var a:t2n);

var i,j:integer;

begin

for i:=1 to 2*n

do begin

  for j:=1 to 2*n

  do write(a[i,j]:3);

  writeln

end;

end;

Спецификация

1. Назначение: сортировка части одномерного массива (от индекса first по индекс last), содержащего не более, чем 2n элементов

2. Имя: sort

3. Вид: процедура

4. Перечень параметров:

Таблица 19.6. Перечень параметров

Статус	Назначение	Имя	Тип	Вид
Вход/ выход	сортируемый массив	b	t1	параметр-переменная
Вход	Индекс начала диапазона сортировки	first	integer	параметр-значение
Вход	Индекс конца диапазона сортировки	last	integer	параметр-значение
Вход	Признак сортировка (истина – сортировка по возрастанию, ложь – по убыванию)	prs	boolean	параметр-значение

Примечание: тип t1 и поименованная константа n должны быть определены до текста подпрограммы

type t1=array[1..2*n] of integer;

5. Заголовок подпрограммы: procedure sort(var b:t1;first,last:integer;prs:boolean);

Метод решения

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

" i:=first(1)last-1:

решаем две задачи:

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

2) перестановку. На место экстремального значения заносим значение с формируемого места. На формируемое место записываем экстремальное значение

Задача 1 сводится к поиску экстремального значения и его местоположения, начиная с формируемого места i по последнее сортируемое место last. При сортировке по возрастанию ищется минимальное значение, по убыванию – максимальное. Метод решения этой задачи выглядит следующим образом:

1) переменной extr, в которой будет сформировано экстремальное значение присваивается первое значение, среди которых ищется экстремальное;

2) фиксируется местоположение экстремального значения в массиве. Для этого во вспомогательную переменную nm заносится индекс элемента, из которого взято значение (в данном случае nm:=i);

3) перебираются все остальные значения:

                                         " j:= i +1(1) last:

Для каждого j значения при сортировке по возрастанию (pr=истина), если очередное j значение меньше хранящегося в extr, а при сортировке по убыванию (pr=ложь) – больше, то

а) переменной extr присваиваем это очередное значение;

б) фиксируем местоположение текущего значения в массиве. Для этого во вспомогательную переменную nm заносится индекс j.

Задача 2 – это перестановка значений. Так как экстремальное значение существует в двух экземплярах (в переменной extr и в массиве на месте с индексом nm), то метод решения состоит из следующих действий:

1)    b[nm]:=b[i];

2)    b[i]:=extr.

Информационная модель

Таблица 19.7. Информационная модель

Назначение	Имя	Тип
Индекс формируемого места	i	integer
Индекс при поиске экстремального	j	integer
Экстремальное значение	extr
Местоположение экстремального значения	nm

Текст процедуры

procedure sort(var b:t1;first,last:integer;prs:boolean);

var i,j,nm:integer;

extr:integer;

begin

for i:=first to last-1

do begin

  extr:=b[i];

  nm:=i;

  for j:=i+1 to last

  do if prs and (b[j]<extr) or not prs and (b[j]>extr)

       then begin

                 extr:=b[j];

                 nm:=j

               end;

  b[nm]:=b[i];

  b[i]:=extr;

end

end;

Спецификация

1. Назначение: сортировка определенной в задании части двумерного массива с использованием подпрограммы sort

2. Имя: sortpart

3. Вид: процедура

4. Перечень параметров:

Таблица 19.8. Перечень параметров

Статус	Назначение	Имя	Тип	Вид
Вход/ выход	сортируемый массив	a	t2n	параметр-переменная

Примечание: тип t2n и поименованная константа n должны быть определены до текста подпрограммы

type t2n=array[1..2*n,1..2*n] of integer;

5. Заголовок подпрограммы: procedure sortpart(var a:t2n);

Метод решения

Для каждой сортируемой строки двумерного массива (с первой по n-ую)

" i:=1 (1) n:

1) переписываем i-ую строку во вспомогательный одномерный массив b. Для этого перебираем все столбцы двумерного массива. Индекс при этом является одновременно индексом одномерного массива и индексом столбца двумерного;

2) обращаемся к процедуре sort сортировки части одномерного массива, задавая границы сортировки. Нижняя граница, исходя из постановки задачи, всегда n+1, а верхняя уменьшается с увеличением номера строки – 2n-i+1 (побочная диагональ);

3) переписываем отсортированный одномерный массив b в i-ую строку двумерного массива.

Информационная модель

Таблица 19.9. Информационная модель

Назначение	Имя	Тип
Номер (индекс) строки двумерного массива	i	integer
Номер столбца (индекс) двумерного массива и номер элемента (индекс) вспомогательного одномерного массива	j	integer
Вспомогательный одномерный массив	b	t1

Примечание: тип t1 определяется следующим образом

type t1=array[1..2*n] of integer;

:где  поименованная константа n должна быть определены до текста подпрограммы

Текст процедуры

procedure sortpart(var a:t2n);

type t1=array[1..2*n] of integer;

var b:t1;

i,j:integer;

begin

for i:=1 to n

do begin

  for j:=1 to 2*n

  do b[j]:=a[i,j];

  sort(b,n+1,2*n-i+1, true);

  for j:=1 to 2*n

  do a[i,j]:=b[j]

end

end;

Спецификация

1. Назначение: заполнение нулями определенной в задании части двумерного массива

2. Имя: zap0

3. Вид: процедура

4. Перечень параметров:

Таблица 19.10. Перечень параметров

Статус	Назначение	Имя	Тип	Вид
Вход/ выход	обрабатываемый массив	a	t2n	параметр-переменная

Примечание: тип t2n и поименованная константа n должны быть определены до текста подпрограммы

type t2n=array[1..2*n,1..2*n] of integer;

5. Заголовок подпрограммы: procedure zap0(var a:t2n);

Метод решения

Перебираем индексы элементов двумерного массива, в которые заносится 0.

Информационная модель

Таблица 19.11. Информационная модель

Назначение	Имя	Тип
Номер (индекс) строки двумерного массива	i	integer
Номер столбца (индекс) двумерного массива	j	integer

Текст процедуры

procedure zap0(var a:t2n);

var i,j:integer;

begin

for i:=1 to n

do begin

  for j:=1 to n

  do a[i,j]:=0;

  for j:=2*n-i+2 to 2*n

  do a[i,j]:=0

end;

for i:= n + 1 to 2*n

do for j:=1 to 2*n

do a[i,j]:=0

end;

Метод решения

1) Повторяем пустой цикл до правильного ввода диапазона значений формируемого случайным образом двумерного массива (результат функции vvdiap – истина, при этом начало диапазона формируется в переменной beg, конец – fin);

2) Выводим на экран сформированный массив (вызов процедуры vivod);

3) Сортируем, определенную заданием, часть двумерного массива (вызов процедуры sortpart);

4) Заполняем нулями, определенную заданием, часть двумерного массива (вызов процедуры zap0);

5)  Выводим на экран сформированный массив в соответствии с заданием (вызов процедуры vivod);

Информационная модель

Таблица 19.12. Информационная модель

Статус	Назначение	Имя	Тип
Вход	начало диапазона значений	beg	integer
Вход	конец диапазона значений	fin	integer
Выход	формируемый массив	a	t2n

Примечание: тип t2n определяется следующим образом:

type t2n=array[1..2*n,1..2*n] of integer;

где n – поименованная константа

Текст программы

program procor;

const n=5;

type t2n=array[1..2*n, 1..2*n] of integer;

 

 

{ввод диапазона значений}

function vvdiap(var beg,fin:integer):boolean;

begin

writeln('Начало и конец диапазона значений?');

readln(beg,fin);

if fin-beg+1>=4*n*n

then vvdiap:=true

else vvdiap:=false

end;

 

{заполнение разными целыми случайными числами в

заданном диапазоне от beg по fin}

procedure zapoln(beg,fin:integer; var a: t2n);

var i,ii,j,jj,x:integer;

  pr:boolean;

begin

for i:=1 to 2*n

do for j:=1 to 2*n

do begin

     pr:=true;

     while pr

     do begin

          x:=round(random*(fin-beg)+beg);

          pr:=false;

          for ii:=1 to i-1

          do for jj:=1 to 2*n

             do if a[ii,jj]=x

                then pr:=true;

          for jj:=1 to j-1

          do if a[i,jj]=x

             then pr:=true

        end;

     a[i,j]:=x

   end;

end;

 

{вывод двумерного массива}

procedure vivod(var a:t2n);

var i,j:integer;

begin

for i:=1 to 2*n

do begin

  for j:=1 to 2*n

  do write(a[i,j]:3);

  writeln

end;

end;

 

{сортировка части}

procedure sortpart(var a:t2n);

type t1=array[1..2*n] of integer;

 

{процедура сортировки части одномерного массива от

элемента с индексом first по элемент с индексом last}

procedure sort(var b:t1;first,last:integer;prs:boolean);

var i,j,nm:integer;

extr:integer;

begin

for i:=first to last-1

do begin

    extr:=b[i];

    nm:=i;

    for j:=i+1 to last

    do if prs and (b[j]<extr) or not prs and (b[j]>extr)

       then begin

               extr:=b[j];

               nm:=j

            end;

    b[nm]:=b[i];

    b[i]:=extr;

end

end{procedure sort};

 

var b:t1;

i,j:integer;

begin

for i:=1 to n

do begin

  for j:=1 to 2*n

  do b[j]:=a[i,j];

  sort(b,n+1,2*n-i+1, true);

  for j:=1 to 2*n

  do a[i,j]:=b[j]

end

end;

 

{заполнение нулями части}

procedure zap0(var a:t2n);

var i,j:integer;

begin

for i:=1 to n

do begin

  for j:=1 to n

  do a[i,j]:=0;

  for j:=2*n-i+2 to 2*n

  do a[i,j]:=0

end;

for i:= n + 1 to 2*n

do for j:=1 to 2*n

do a[i,j]:=0

end;

 

var a:t2n;

beg,fin:integer;

begin

repeat

until vvdiap(beg,fin);

zapoln(beg,fin,a);

writeln('Исходный массив:');

vivod(a);

sortpart(a);

zap0(a);

writeln('Результирующий массив:');

vivod(a)

end.

Процедурно-ориентированное программирование. Пример

Постановка задачи

Заполнить разными случайными целыми числами квадратную матрицу порядка 2n из заданного диапазона значений от beg по fin. В этой матрице отсортировать строки в заштрихованной части по возрастанию, остальные элементы заполнить 0 (рис. 19.1).

Рис. 19.1. – Постановка задачи

Логическая структура программы

Рис. 19.2. – Логическая структура программы

Предлагается задачу разбить на 5 подзадач:

- ввод диапазона значений для заполнения;

- заполнение матрицы разными целыми случайными числами равномерно распределенными в заданном диапазоне;

- вывод на экран матрицы;

- сортировка заштрихованной части матрицы;

- заполнение нулями не заштрихованной части матрицы.

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

Предложенная логическая структура программы приведена на рис. 19.2.