Pascal. Поиск в массиве.

Записывать данные в массива можно и без помощи readln, достаточно простой команды read. Приведём простой пример где считываем данные из массива и выводим:

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

Это было простое повторение. А теперь давайте попробуем написать программу, которая ищет в массиве число k, и если оно есть, то выводит yes или no:

for i:=1 to n do
 if a[i]=k then
  q:=1;
if q=1 then
 write('Yes')
else
 write('No');

Эту программу все всегда пишут с первого раза именно в таком виде.

Какие тут могут быть ошибки?

Ошибки довольно таки простые:

Например переменная q и так может быть равна 1, так как в разных средах Ваша программа будет воспринимать всё по разному. Тогда онулируем переменную в самом начале:

q:=0;
for i:=1 to n do
 if a[i]=k then
  q:=1;
if q=1 then
 write('Yes')
else
 write('No');

И видно что программа будет работать очень долго, если у нас будет массив из миллиарда элементов, так как наш цикл сначала проверит весь массив и только потом выдаст результат, что нам не нужно. Тогда ускорить программу нам поможет замена цикла на цикл с условием — while:

q:=0; i:=1;
while (q<>1) and (i<=n) do
begin
 if a[i]=k then
  q:=1;
 i:=i+1;
end;
if q=1 then 
 write('Yes')
else
 write('No');

Теперь программа стала работать быстрее, так как после нахождения нужного нам числа, цикл остановится, но эта программа ещё далека от совершенства. Теперь давайте попробуем вида-изменить цикл while, и убрать переменную q:

i:=1;
while (a[i]<>k) and (i<=n) do
 i:=i+1;
if q=1 then 
 write('Yes')
else
 write('No');

Наш цикл стал немного лучше, но всё же в нём есть грубые ошибки, и эти ошибки именно в цикле, а не в условии, так как мы его пока затрагивать не собираемся. И так какую же ошибку мы можем сейчас изменить? Ошибка очень проста, достаточно посмотреть на условие цикла, и всё станет понятно — мы говорим о том, что сначала цикл проверяет совпадение, а потом кончился ли цикл или нет, что может выдать ошибку.

То есть если у нас в программе строгие проверки с количеством элементов в массиве, то ошибка будет видна нам сразу, а так мы её и не заметим, то есть цикл может быть переполненным — значение i станет равно n+1, что нам не нужно, тогда достаточно просто поменять условия местами, и как известно в pascal — если одно условие не сработает, то и другое проверятся не будет:

i:=1;
while (i<=n) and (a[i]<>k) do
 i:=i+1;
if q=1 then 
 write('Yes')
else
 write('No');

Мы можем ещё упростить верхнюю часть:

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

Это самый последний элемент массива, добавленный вручную, который имеет искомое значение, то есть мы добавим искомое значение в конец массива, и при проверки условия будет проверять именно это — имеет ли переменная i значение n+1:

i:=1;
a[n+1]:=k;
while a[i]<>k do
 i:=i+1;
if i=n+1 then  write('No')
else write('Yes');

Мы добавили одну ячейку памяти и при этом ускорили программу вдвое.

Теперь перейдём к следующему:

Второй максимум.

То есть мы будем искать в массиве второй максимум, второй максимум — это число, которое меньше максимума, но больше других чисел.

Сначала напишем программу, которая просто находит максимальное число в массиве:

max:=a[1];
for i:=2 to n do
 if a[i]>max then
  max:=a[i];

Как видим — максимум у нас равен первому элементу, который мы будем сравнивать со всеми другими элементами.

До этого мы представляли себе — если у нас много чисел, то всех их нужно загонять в массив, но это не так — представьте себе что в Вашей программе нельзя использовать массивы, то как сделаете Вы?

Самое простое решение — это использование одной переменной для хранения всех значений:

readln(k);
max:=k
for i:=2 to n do
begin
 readln(k);
  if k>max then
   max:=k;
end;

Теперь перейдём к решению задачи со вторым максимумом.

Представим что изначально переменные max и max2 равны минус бесконечности.

Теперь изменим код предыдущей программы именно так, что бы он искал max2 и не было ни каких ошибок:

readln(k);
max:=k;
for i:=2 to n do
begin
 readln(k);
  if k>max then
  begin
   max2:=max;
   max:=k;
  end else
   if (k>max2) and (k<max) then
    max2:=k;
end;

В этой программе мы всё учли, даже то, что max может изначально иметь максимальное значение.

Представьте себе задачу подсчитать сколько максимумов в массиве, то как бы Вы реализовали её?

Мы предлагаем ввести в программу счётчик, который увеличивался на 1 при новом максимуме или числу равному максимуму. Увеличивать мы будем не по старинке — i:=i+1, а при помощи функции increment, сокращённо inc, и в скобках уже пишем имя переменной, эта функция увеличивает переменную на единицу. Также есть и функция, которая уменьшает значение на единицу — decrement, сокращённо dec.

Теперь давайте напишем нашу программу:

readln(k);
max:=k;
maxcount:=0;
for i:=2 to n do
begin
 readln(k);
  if k>max then
  begin
   inc(maxcount);
   max2:=max;
   max:=k;
  end else
   if (k>max2) and (k<max) then
    max2:=k
   else
    if max=k then
     inc(maxcount);
end;

Рейтинг
( Пока оценок нет )
Загрузка ...