Меню
Главная

Статистика

 

 


Упражнение #1.

Информация из школьного классного журнала размещается в трехмерном массиве: внешние компоненты - это страницы журнала, "средние" компоненты - строки на странице, и наконец, "внутренние" компоненты - оценки в строке. Притом, каждая страница, помимо строк, содержит еще и ключевое символьное поле Page - название предмета. Соответственно, ключевое поле Name - фамилию ученика - имеют и страницы. Оцените размеры памяти, необходимые для хранения массива, если заданы количество страниц NumPage, число строк на каждой странице NumLine, количество оценок в каждой строке NumMark, а также длина символьных строк-названий, соответственно, Length(Name) и Length(Page).


Упражнение #2.

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

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

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

Алгоритм E1-1

  • index¬left

  • обработкаMas[index]

  • index¬index + 1

  • if index>right then Exit

  • переход к шагу 2

где left и right, соответственно, индексы левого и правого элементов линейной развертки входного массива Mas.

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

Пример #1.

Разместить в ячейках вектора заданной длины N (пусть, для определенности, N=100) натуральные числа от 1 до N в обратном порядке. Учитывая возможность использовать конструкцию цикла с параметром языка паскаль, одним из возможных вариантов решения будет следующая процедура, непосредственно "переписанная" из приведенного выше алгоритма: 

const N=100;
type
  index1 = 0..N-1;
  massive1 = array [index1] of byte;

procedure InitArray1 (var Mas: massive1);
var i: index1;
begin
  for i:= 0 to N-1 do
    Mas[i]:= N-i;
end;
                
type
  index1 = 0..N-1; {N > 1}
  Programmer = record of
    Name: string; Number: byte; Time: word
  end;
var Results = array [index1] of Programmer;
        
type
  index1 = 0..N-1; {N > 1}
  massive1 = array [index1] of item;

function Search2 (Mas: massive1;
  left, right: index; sample: item): boolean;
var l, r, middle: index1;
begin
  l := left; r:= right;
  while l<r do begin
    middle:= (l+r) div 2;
    if Mas[middle] < sample then l:= middle + 1
    else r := middle
  end;
  if M[l] = sample then Search2:= true
  else Search2:= false
end;
            
type
  index1 = 0..N-1; {N>1}
  massive1 = array [index1] of item;

procedure SelectionSort (var Mas: massive1);
var i: index1;
begin
  for i := (N-1) downto 1 do
    Swap(Mas[i], Mas[IndexMax(Mas,0,i)]);
end;


Упражнение #3.

Напишите процедуру инициализации линейного массива случайными числами из заданного интервала. Повторение значений в разных ячейках допускается.


Упражнение #4.

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

Назад