if a[i]>m then Begin

                                       m:=a[i];

                                       k:=I;

                               end;

       writeln(m,’ ‘,k);

end.

4.3. Задачи поиска

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

Большинство задач поиска сводится к простейшей задаче — найти в таблице элемент с заданным значением.

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

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

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

Вариант 1.

program MAS2_F7;

var

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

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

  i, n,k, p:integer;

Begin

  readln(n);

  for i:=1 to n do 

        read(a[i]);

k:=0;

for i:=1 to n do 

  if (a[i]=0) and (k=0) then  begin writeln(i); k:=1 end;

if k=0 then writeln(‘Net takix elementjb’);

End.

Вариант 2.

program MAS2_F7W;

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

i, n:integer;

begin

readln (n);

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

i:=1;

While (i<= n) and (a[i]<>0)do i:=i+1;

if i>n then writeln('NO') else writeln(i);

end.

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

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

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

program a6;

var

               i, n,b, k1,k2:integer;

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

begin

       readln(n);

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

       i:=1;

  While (i<=n) and ( a[i] <0) do i:=i+1;

        if i>n then writeln('NO')

        else begin

                k1:=i;  i:=n;

While (i>=1) and ( a[i]>0) do  i:=i-1;

        if i<1 then writeln('NO')

else begin

                       k2:=I;

                       b:=a[k1];

                       a[k1]:= a[k2];

                       a[k2]:=b;

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

                       end;

               end;

end.

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

program a3;

var

               i, n,m, k,z:integer;

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

begin

       readln(n);

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

       i:=1;

  While (i<=n) and ( a[i] mod 2<>0) do i:=i+1;

        if i>n then writeln('NO')

        else begin

               m:=a[i]; k:=i; z:=i;

               for i:=z+1 to n do

                if ( a[i] mod 2=0) and(a[i]>m) then

  Begin

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

                end;

                writeln(m,’ ‘,k);

  end;

end.

4.4. Задачи перестановки

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

В качестве примера рассмотрим задачу циклической перестановки.

Пример 1. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Элементы массива циклически перемещаются по следующему правилу: каждый элемент, за исключением начального элемента перемещается в предыдущий по порядку (меньший по индексу) элемент массива.

При этом начальный элемент массива перемещается в последний элемент массива.

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

Алгоритм сдвига всех элементов массива влево циклически:

program SDV_VLEVO;

var

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

  i, n,z:integer;

Begin

  readln(n);

  for i:=1 to n do 

        read(a[i]);

  Z:=a[1];

For i:=1 to n-1 do

  A[i]:=a[i+1];

A[n]:=Z;

for i:=1 to n do 

  write(a[i],’ ‘);

End.

Здесь важно понять необходимость дополнительной переменной для временного хранения одного элемента и правильно организовать заголовок цикла (до n-1, а не до n).

Пример 2. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Элементы массива циклически перемещаются по следующему правилу: каждый элемент, за исключением последнего элемента перемещается в последующий по порядку (меньший по индексу) элемент массива.

При этом начальный элемент массива перемещается в последний элемент массива.

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

Алгоритм сдвига всех элементов массива вправо циклически:

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

program SDV_VPRAVO;

var

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

  i, n,z:integer;

Begin

  readln(n);

  for i:=1 to n do 

        read (a[i]);

Z:=a[n];

For i:=n downto 2 do

  a[i]:=a[i-1];

a[1]:=Z;

for i:=1 to n do 

  write (a[i],’ ‘);

End.

Пример 3. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Выполнить сдвиг элементов массива влево циклически, начиная с К-того до последнего элемента массива.

Вопрос ученикам: Как изменится алгоритм, если выполнить сдвиг элементов массива, начиная с К-того до последнего элемента массива?

program SDV_VLEVO_C_K_elementa;

var

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

  i, n,z, k:integer;

Begin

  readln(n, К);

  for i:=1 to n do 

        read(a[i]);

Z:=a[К];

For i:=К to n-1 do

A[i]:=a[i+1];

A[n]:=Z;

for i:=1 to n do 

write(a[i],’ ‘);

End.

Заметим – изменения выделены жирным шрифтом.

Пример 4. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Выполнить сдвиг элементов массива вправо циклически, начиная с К-того до последнего элемента массива

program SDV_VPRAVO_C_K_elementa;

var

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

  i, n,z, к:integer;

Begin

  readln(n, к);

  for i:=1 to n do 

        read (a[i]);

Z:=a[n];

For i:=n downto К+1 do

  a[i]:=a[i-1];

a[К]:=Z;

for i:=1 to n do 

  write (a[i],’ ‘);

End.

Пример 5. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Удалить элемент массива с заданным номером (К).

Алгоритм данной задачи сводится к сдвигу элементов массива влево, начиная с К-того до последнего элемента массива и уменьшению размерности массива на единицу.

program Udalenie_K_elementa;

var

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

  i, n,k:integer;

Begin

  readln(n, k);

  for i:=1 to n do 

        read(a[i]);

For i:=k to n-1 do

  A[i]:=a[i+1];

n:=n-1;

for i:=1 to n do 

write(a[i],’ ‘);

End.

Пример 6. Пусть дан массив A, состоящий из n элементов: a1, a2, a3, …, an. Вставить заданное число перед или после элемента массива с заданным номером (К).

Алгоритм данной задачи сводится к сдвигу элементов массива вправо, начиная с К-того до последнего элемента массива

program Vstavit_C_Pered_K;

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

i, n, k, c: integer;

begin

readln (n, k, c);

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

for i:=n+1 downto k+1 do  a[i]:=a[i-1];

n:=n+1;  a[k]:=C;

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

end.

program Vstavit_C_Posle_K;

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

i, n, z, k, c: integer;

begin

readln (n, k, c);

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

for i:=n+1 downto k+1 do a[i]:=a[i-1];

n:=n+1;

a[k+1]:=C;

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

end.

Задачи для самостоятельного решения

Далее ученику даются задачи для решения и предлагается самому определять тип задач.

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