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

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

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

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

НЕ нашли? Не то? Что вы ищете?

Классификация задач, окончательно получаем такие группы задач:

Заполнение Анализ Поиск Перестановка.

Приведем задачи для каждой группы.

Составление алгоритмов для обработки потока данных

4.1. Задачи заполнения

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

По методу решения задачи заполнения можно разделить на несколько групп. Главные из них — прямое заполнение и заполнение с поиском.

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

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

Пример 1. Заполнить таблицу нулями. Это простейший случай прямого заполнения по формуле.

var

a:array[1..100] of integer; 

i, n:integer;

begin

readln(n);

for i:=1 to n do a[i]:=0;

Пример 2. Сделать все элементы таблицы равными х. В отличие от примера 1, здесь появляется дополнительный аргумент — число, которым следует заполнить таблицу.

var

a:array[1..100] of integer; 

i, n,x:integer;

begin

readln(n, x);

for i:=1 to n do a[i]:=x;

Пример 3. Заполнить таблицу квадратами натуральных чисел. Особенность этого примера — использование в формуле заполнения индекса элемента.

var

a:array[1..100] of integer; 

i, n:integer;

begin

readln(n);

for i:=1 to n do a[i]:=i*i;

Пример 4. Заполнить таблицу последовательностью четных чисел.

Этот пример интересен тем, что допускает два решения: с использованием формулы и рекуррентное.

Первое решение использует общую формулу четного числа.

var

a:array[1..100] of integer; 

i, n:integer;

begin

readln(n);

for i:=1 to n do a[i]:=2*i;

Второе решение основано на рекуррентном соотношении: каждое следующее четное число на 2 больше предыдущего.

var

a:array[1..100] of integer; 

i, n,s:integer;

begin

readln(n);

а[1]:=2;

for i:=2 to n do a[i]:=a[i-1]+2;

Пример 5. Заполнить таблицу значениями элементов последовательности Фибоначчи.

Здесь рекуррентное соотношение — наиболее естественный способ решения.

var

a:array[1..100] of integer; 

i, n:integer;

begin

readln(n);

а[1]:=1;

а[2]:=1;

for i:=3 to n do a[i]:=a[i-1]+ a[i-2];

Пример 6. Заполнить таблицу случайными целыми числами из интервала от 1 до К.

randomize;

n:=8;  { или readln(n);}

for i:=1 to n do a[i]:= random(К);

       for i:=1 to n do write(a[i],' ');

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

Дополнительно можно рассмотреть еще два примера, часто используемых при практическом программировании.

Пример 7. Заполнить таблицу, запрашивая значение каждого элемента с клавиатуры. Можно запрашивать и размер таблицы.

var

a:array[1..100] of integer; 

i, n:integer;

begin

readln(n);

for i:=1 to n do 

        read(a[i]);

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

assign(input,'input. txt');

assign(output,'output. txt');

reset(input);        rewrite(output);

readln(n);

for i:=1 to n do read(a[i]);

4.2. Задачи анализа

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

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

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

Алгоритм вычисления суммы элементов массива.

Пример 1. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Нужно найти сумму элементов массива, т. е. S=a1+a2+a3+…+an.

Нахождение суммы есть реализация конструкции «Счетчик», т. е. последовательное нахождение суммы по формулам:

1)S=0  2) S=S+a1  S=S+a2  S=S+a3  …  S=S+ai  …  S=S+an

Алгоритм вычисления суммы удобно организовать циклом, взяв за параметр цикла переменную i, которая меняется от 1 до n с шагом 1, и записав в цикле формулу S=S+ai один раз.

Фрагмент алгоритма:  S=0;  for i:=1 to n do  S=S+a[i];

Алгоритм нахождения среднего арифметического элементов с определенным качеством.

Пример 2. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Нужно найти сумму четных значений элементов массива,.

program a2;

var

               i, n,s, k:integer;

               sr:real;

               a:array[1..100]of integer;

begin

       readln(n);

       for i:=1 to n do read(a[i]);

       for i:=1 to n do

                if a[i] mod 2=0 then begin

                 s:=s+a[i];

                                       k:=k+1;

                               end;

       if k=0 then writeln('NO')

               else begin

                        sr:=s/k;

                        writeln(sr:5:2)

               end;

end.

Алгоритм нахождения индексов каждого элемента массива, значение которого равно нулю.

Пример 3. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Найти индексы всех  элементов массива, значение которых равно нулю.

program MAS2_F6;

var

  a:array[1..100] of integer;

  i, n:integer;

Begin

  readln(n);

  for i:=1 to n do 

        read(a[i]);

for i:=1 to n do 

  if a[i]=0 then write(i,’ ‘);

End.

Алгоритм нахождения максимального элемента массива и его индекса.

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

Решение: Пусть а, в, с — вводимые числа, m — максимальное из них. Сначала предположим, что а — максимальное из чисел (т. е. m: =а ). Затем сравним значение предполагаемого максимума со значениями переменных b и с. Если значение m окажется меньше, чем значение очередной переменной, то изменим значение максимума:

Begin

  Writeln('введите значения а, Ь, с');

  Readln(a, b,с);

  m: =а;

  If m<b Then  m:=b;

  If m<c Then m:=с;

  Writeln('максимальное число - ',m)

End.

Пример 3 Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.

Решение: Используем идею решения предыдущей задачи. Перед началом поиска выберем в качестве максимального первый элемент массива: m:=а [1]. Затем каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение m. После сравнения со всеми элементами массива переменная m содержит значение максимального элемента массива.

Begin

m:=а[1]; 

For i:=2 To 10 Do

  If m<a[i] Then m:=a[i];

Writeln('максимальный элемент массива - ', m);

End;

Нахождения максимального элемента массива и его индекса.

program a3;

var

               i, n,m, k:integer;

               a:array[1..100]of integer;

begin

       readln(n);

       for i:=1 to n do read(a[i]);

       m:=a[1];        k:=1;

       for i:=2 to n do

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4