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

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

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

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

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

Пример 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]);