Как найти последовательность чисел в массиве

Поиск последовательности в массиве

// допускаем, что данные всегда передаются валидные
// src_array - исходный массив
// len - его длина
// sindex, eindex - результат поиска - начальный и 
// конечный индексы последовательности
void sub_array(int *src_array, int len, 
                int &sindex, int &eindex)
{
   int sum = src_array[0];
   sindex = 0;
   eindex = 0;
      // проверяем наличие положительных значений
   bool has_positive = false;
   for(int i=0;i < len;i++)
      if(src_array[i]>0)
      {
         has_positive = true;
         break;
      }
   for(int i=0;i < len;i++)
   {
      int ssum = src_array[i];
      if(has_positive && ssum < 0) continue;



  


                       
  



      for(int j=i;j < len;j++)
      {
         ssum += j>i?src_array[j]:0;
         if(ssum>=sum)
         {
            sum = ssum;
            sindex = i;
            eindex = j;
         }
      }
   }
}

Необходимо найти и вывести на экран все последовательности длины N из чисел 1,2,...,M. Это одна из типовых задач программирования, с которой, думаю, каждый хотя бы раз в том или ином виде сталкивался или столкнется при работе над каким-либо проектом. И в этой статье, посвященной различным алгоритмам, реализованным на языке C# мы и решим эту саму задачу о поиске всех возможных последовательностей.

Задача

Пользователь вводит с клавиатуры два числа: N — длину каждой последовательности, M — последнее число из ряда 1...M. Программа должна составить N последовательностей длиной N из ряда чисел 1..M.

Суть решения задачи

Чтобы понять, как должен выглядеть результат, представим задачу с конкретными значениями, например, N = 4, M = 3. Тогда наша программа должна составить и вывести следующие последовательности:

(1,1,1,1) (1,1,1,2) (1,1,1,3) (1,1,2,1) (3,1,3,3) (3,2,1,1)....(3,3,3,3)

Количество таких последовательностей всегда будет равно M^N.

Для решения задачи нам понадобятся следующие знания: что такое массив и работа с циклами.

Ниже представлен код программы на C#, реализующий поиск и вывод всех последовательностей длиной N из ряда чисел 1..M

class Program
 {
     static void Main(string[] args)
     {
         byte m;
         byte n;
         byte[] Sequence;
         int counter = 1;

         Console.WriteLine("Введите количество элементов последовательности (N) и нажмите Enter");
         n = byte.Parse(Console.ReadLine());
         Console.WriteLine("Введите последнее число из ряда (1..M) и нажмите Enter");
         m = byte.Parse(Console.ReadLine());

         Sequence = new byte[n]; //массив в котором будет храниться очередная последовательность

         bool yes;
        
         void Next(byte[] sequence)
         {
             int i = n - 1;
             while ((i > -1) && (sequence[i] == m))
             {
                 sequence[i] = 1;
                 i--;
             }
             yes = i > -1;
             //если очередной элемент в последовательности можно нарастить
             if (yes)
             {
                 sequence[i]++;
             }
         }

         //задаем первую последовательность, например, (1,1,1,1)
         for (int i = 0; i < n; i++)
         {
             Sequence[i] = 1;
         }

         //пробуем перебрать все последовательности
         do
         {
             //выводим счётчик очередной последовательности (стартуем с 1)
             Console.Write($"{counter}: ");
             counter++;
             //выводим на экран очередную последовательность
             for (int i = 0; i < n; i++)
             {
                 Console.Write($"{Sequence[i]} ");
             }
             Console.WriteLine();
             //пробуем найти следующую последовательность
             Next(Sequence);
         }
         while (yes);

     }
 }

Результат работы программы представлен ниже:

Как видите, программа вывела ровно M^N (2^3 = 8) последовательностей.

Готовый проект C# вы можете скачать из нашего репозитория на GitHub.

Итого

Сегодня мы научились искать все последовательности заданной длины состоящие из чисел от 1 до M. В работе мы использовали массивы, циклы for, while и do..while и для вывода строк воспользовались интерполяцией.

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

Типовые задачи на поиск
элемента в массиве:

·      
поиск максимального или минимального
элемента;

·      
поиск элемента, имеющего конкретное
значение.

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

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

·      
запишем результат и номер первого
участника, полагая, что он победит;

·      
далее, пока не закончатся участники, мы
будем делать следующее:

·      
смотреть сколько раз участник попал в
кольцо;

·      
если участник попал меньше или столько же
раз, как и тот, результат которого мы записали до этого – его номер мы не
записываем;

·      
если участник попал в кольцо большее
количество раз, чем тот, номер которого записан, – мы зачеркнём записанный
номер и запишем новый и предположим, что этот участник победит.

Таким образом, в конце у нас будет записан номер
участника, который попал в кольцо наибольшее количество раз.

Запишем данный алгоритм в форме программы. Назовём
программу sorevnovanie.
Нам понадобится переменная n,
которая будет хранить количество участников, переменная i,
которая будет хранить номер текущего участника и переменная r, которая будет хранить номер
предполагаемого победителя. А также массив результатов a. Все данные задачи будут
принадлежать к целочисленному типу integer.

Между служебными словами begin и end запишем тело программы.
Вначале выведем на экран поясняющее сообщение о том, что это программа
определения победителя в соревнованиях по броскам мяча в корзину, а также
запрос на ввод количества участников. Считаем переменную n с переходом на следующую строку.
Запишем цикл for
i:=1
to
n
do,
в котором будут команды вывода на экран запроса на ввод результата i-того
участника, а так же считывания i-того элемента массива a.

После цикла будет следовать команда r:=1,
т. е. мы полагаем, что победит первый участник.

Далее, так как результат первого участника уже
сохранен, начнём просматривать результаты со второго. При помощи цикла for i:=2
to
n
do,
мы будем сравнивать результат предполагаемого победителя с последующими, и если
i-тый участник попал в кольцо большее
количество раз – он становится предполагаемым победителем, то есть присвоим
переменной r
значение i.
В конце выведем поясняющее сообщение с текстом «Победил участник под номером»,
и значение переменной r.

Исходный
код программы

Запустим программу на выполнение. Пусть было пятеро
участников. Первый попал в кольцо десять раз, второй – семь, третий –
одиннадцать, четвёртый – пятнадцать и пятый – восемь. Таким образом,
результатом должна быть победа четвёртого участника.

Результат
работы программы

Результат работы программы соответствует ожидаемому –
следовательно, задача решена верно.

Еще
одним типом задач являются задачи на поиск элемента в массиве по указанному
значению.

Задача: Определить, есть
ли в последовательности n
случайных
чисел от 1 до 100 число равное k. Если есть – вывести номер, под которым оно
встречается впервые, а если нет – вывести слово «Нет».

Для решения данной задачи нам понадобится
последовательность чисел, хранящаяся в массиве a, длина данной последовательности n, номер текущего элемента
последовательности i, искомое число k.

Составим блок-схему алгоритма решения данной задачи.

Для начала необходимо ввести длину последовательности
чисел, а также искомое число. Затем будут следовать циклы для генерации
последовательности случайных чисел длины n и
для вывода её элементов на экран.

Теперь перейдём к поиску. Для этого переменной i
присвоим значение 1 и будем перебирать элементы пока они не закончатся или пока
не найдём искомый. Цикл поиска будет содержать всего одну команду – увеличения i
на 1. Таким образом, в конце нам достаточно будет проверить, равен ли i-тый элемент массива a заданному k. Если равен, выведем поясняющее
сообщение «Номер искомого элемента последовательности» и значение i.
Если же не равен, выведем слово «Нет». В конце блок-схемы следует блок «Конец».

Блок-схема
алгоритма

Запишем программу по данной блок-схеме. Назовём её poisk. В разделе описания переменных будет массив из ста
элементов типа integer,
а также переменные n,
i
и k
типа integer.

Запишем тело программы. Выведем с переходом на
следующую строку поясняющее сообщение о том, что это программа поиска элемента k в
последовательности из n
случайных чисел. Теперь выведем запрос на ввод n и считаем её, то же сделаем и для k. Запишем цикл for i:=1
to
n
do,
который будет содержать команду присваивания i-тому элементу массива a, суммы случайного числа от 0 до 99 и
1. Теперь запишем такой же цикл for i:=1 to n do, который будет содержать одну
команду вывода i-того элемента массива a через пробел.

Теперь выполним поиск в последовательности случайных
чисел элемента равного k.
Для этого, согласно блок-схеме, мы будем перебирать элементы, пока они не
закончатся, или пока не найдём равный k. Для этого присвоим i:=1
и запишем цикл while
с условием i<n и a[i]<>k, содержащий команду увеличения i
на 1.

Теперь для вывода ответа мы должны перейти на
следующую строку – для этого достаточно записать оператор writeln
без параметров. Для проверки того, нашли ли мы нужный элемент, запишем условный
оператор с условием, что a[i]=k, в случае выполнения условия выведем
на экран значение i, в противном случае
выведем слово «Нет».

Исходный
код программы

Запустим программу на выполнение и введём длину
последовательности, равную 15 и k, равное 3. В
последовательности, сгенерированной программой, есть элемент равный 3 на первой
позиции, программа вывела число 1. Ещё раз запустим программу на выполнение и
введём длину последовательности, равную 10, и искомый элемент, равный 70. В
последовательности, сгенерированной программой, элемента с таким значением нет,
и программа вывела слово «Нет». Программа работает правильно. Задача решена.

Результаты
работы программы

Также при поиске удобно использовать цикл с пост
условием repeat,
который записывается в следующей форме. Записывается служебное слово repeat, после которого идёт
тело цикла, то есть последовательность команд, которая будет повторяться. После
чего записывается служебное слово until, после
которого идёт условие, при выполнении которого цикл прекратит работу. Обратим
внимание, что при записи тела цикла repeat служебных слов begin и end не требуется, а условие,
в отличии от цикла while,
проверяется после выполнения тела цикла.

Изменим текст нашей программы. До поиска элемента
программа будет такой же. Перед циклом поиска нужно присвоить переменной i
значение 0, так как условие будет проверяться уже после увеличения i
на 1. Вместо строки while
с условием запишем служебное слово repeat, а после тела цикла – служебное слово until. Цикл будет выполняться,
пока i-тый элемент массива a не будет равен k или пока i не станет равным n.

Исходный
код изменённой программы

Ещё раз запустим программу на выполнение. Введём длину
последовательности, равную 20, и k, равное 7. В сгенерированной программой
последовательности такого элемента нет, и программа вывела на экран слово
«нет». Ещё раз запустим программу на выполнение и введём длину
последовательности, равную 10 и k, равное 40. В последовательности случайных чисел
число сорок находится на второй позиции, и программа вывела на экран число 2.
Программа работает верно.

Результаты
работы изменённой программы

Важно запомнить:

Типовые задачи на поиск
элемента в массиве:

·      
найти элемент, сравнивая его с другими
элементами массива;

·      
найти элемент, равный определённому
значению.

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

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

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

Для полноценного понимания темы рекомендую просмотреть следующие статьи:

1. Анализ сложности алгоритмов. Примеры
2. Примеры анализа сложности алгоритмов
3. Структуры данных. Деревья

А для продолжения изучения — выбрать себе какую-нибудь книгу по алгоритмам.

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

Рассмотрим сначала нюансы реализации “технических” задач поиска, которые встречаются в различных алгоритмах. Начнем с, казалось бы, тривиальной задачи поиска элемента в неупорядоченном массиве. Во всех примерах, относящихся к поиску в одномерном массиве будем использовать следующую переменную a:

a:array[0..N] of <скалярный тип>;

при этом собственно элементы массива, которые мы будем рассматривать, пронумерованы от 1 до N, а нулевой элемент будем использовать как вспомогательный в случае необходимости. Конкретный же тип элемента в большинстве описываемых алгоритмов не важен, он может быть как любым числовым, так и символьным или даже строковым. Алгоритм поиска в массиве элемента, значение которого равно K, может выглядеть так:

i:=0;
repeat
  i:=i+1
until (i=N) or (a[i]=K);

if a[i]=K then 
  write(i)
else 
  write(0)

{следующее неверно (!!!):
if i=N then 
  write(0)
else 
  write(i) 
}

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

a[0]:=K;
i:=N;
while (a[i]<>K) do
  i:=i-1;
write(i)

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

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

imax:=1;
imin:=1;
for i:=2 to N do
  if a[i]<a[imin] then 
    imin:=i
  else
    if a[i]>a[imax] then 
      imax:=i

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

max:=-MaxInt-1;  {это минимальное число типа integer}
min:=MaxInt;  {это максимальное число типа integer}
for i:=1 to N do
  if a[i]<min then 
    min:=a[i] 
  else
    if a[i]>max then  
      max:=i

Казалось бы на этом рассмотрение алгоритмов поиска в неупорядоченном массиве можно завершить. Однако именно с одновременного поиска минимума и максимума можно начать класс алгоритмов поиска, более эффективных, чем приведенные выше стандартные алгоритмы. Причем именно при решении олимпиадных задач их знание может пригодиться в первую очередь. Итак, в приведенном выше алгоритме поиска максимального и минимального элемента в массиве в худшем случае выполняется 2N – 2 сравнений. Покажем, что ту же задачу можно решить за 3*round(N/2) – 2 сравнения. Пусть у нас имеется четное число элементов. Разобьем их на пары и в каждой из N/2 пар за одно сравнение определим, какой элемент больше, а какой меньше. Тогда максимум можно искать уже любым способом только из наибольших элементов в парах, а минимум — среди наименьших. Общее число сравнений при этом равно N/2 + 2(N/2 – 1) = 3N/2 – 2. Для нечетного числа элементов — элемент, не попавший ни в одну из пар, должен участвовать как в поиске максимума, так и минимума.

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

Еще большей эффективности можно добиться при одновременном поиске максимального и второго по величине числа. Для этого организуем поиск максимума по схеме “теннисного турнира”, а именно: разобьем элементы на пары и определим в каждой из пар больший элемент, затем разобьем на пары уже эти элементы и т.д. В “финале” и будет определен максимум. Количество сравнений в таком алгоритме, как и в традиционной схеме, равно N – 1. Однако, максимальный элемент участвовал при этом в round(log2(N)) сравнениях, причем одно из них проходило обязательно со вторым по величине элементом. Таким образом, теперь для поиска этого элемента потребуется всего round(log2(N)) – 1 сравнение. Попробуйте самостоятельно построить эффективный алгоритм для поиска уже первых трех по величите элементов.

В данном контексте можно поставить также задачу поиска i-го по счету элемента, называемого i-ой порядковой статистикой. Кроме максимума и минимума, специфической порядковой статистикой является медиана — элемент с номером (N + 1)/2 для нечетных N и два соседних элемента для четных. Конечно, задачу поиска любой порядковой статистики можно решить, предварительно отсортировав массив. Но, как будет показано ниже, оптимальные по количеству сравнений универсальные (то есть пригодные для произвольных массивов) алгоритмы сортировки выполняют порядка Nlog2N сравнений. А задачу поиска i-ой порядковой статистики можно решить, производя O(N) сравнений. Алгоритм, который гарантирует эту оценку достаточно сложен, он подробно изложен в [1, 2, 3]. Мы же приведем схему алгоритма, который в худшем случае не является линейным, однако на практике работает существенно быстрее, следовательно именно его и нужно использовать в практике реального программирования, в том числе и олимпиадных задач:

Алгоритм Выбор(A, L, R, i)
{выбирает между L-ым и R-ым элементами массива A
 i-ый по счету в порядке возрастания элемент}

1. if L=R then 
     результат = A[L], конец;
2. Q:=L+random(R-L+1) {Q – случайный элемент между L и R}
3. Переставляем элементы от L до R в A так, чтобы сначала шли элементы, меньшие A[Q], а затем все остальные, первый элемент во второй группе обозначим K.
4. if i<=(K-L) then 
     Выбор(A, L, K-1, i)
   else 
     Выбор(A, K, R, i-(K-L))
5. конец.

Оптимальную реализацию пункта 3 можно заимствовать из алгоритма так называемой быстрой сортировки (смотри по ссылкам, приведенным в начале статьи).

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

S:=0;
for i:=1 to N do
begin
  read(a); S:=S+a
end;
writeln(N*(N + 1) div 2 – S)

Данную программу легко переписать так, чтобы она работала и для значений N, превосходящих максимальное представимое целое число. Для этого следует использовать переменные типа extended, а цикл for заменить на while. Используя аналогичный прием попробуйте решить следующую задачу. Пусть N — количество чисел, нечетно и известно, что среди вводимых чисел каждое имеет ровно одно, равное себе, а одно число — нет. Найдите это число. (Указание. В данном случае можно воспользоваться свойством логической функции “исключающее или”, обозначаемой в Паскале как xor: a xor b xor b = a).

Поиск в упорядоченных массивах

Под упорядоченными в дальнейшем будут пониматься неубывающие массивы, если не оговорено иное. То есть, a[1] <= a[2] <= … <= a[N].

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

L:=1; R:=N+1;
while L<R do
begin
  m:=(L+R)div 2;
  if a[m]<K then 
    L:=m+1
  else 
    R:=m
end;

if a[m]=K then 
  write(m) 
else 
  write(0)

Известно, что алгоритм бинарного поиска, аналогичный приведенному выше, но заканчивающий свою работу в случае досрочного обнаружения элемента, за Q сравнений определил, что искомым является элемент с номером I. Какова могла быть при этом размерность массива (указать все допустимые диапазоны значений N). Несмотря на кажущуюся сложность, при заданных в условии ограничениях задача решалась путем простого перебора различных значений N и обращения с каждым из этих значений к функции бинарного поиска. Конструктивный же подход к решению задачи намного сложнее. Однако и в случае подбора можно использовать немало интересных фактов. Например, длина каждого из диапазонов возможных значений N, является степенью двойки, а каждый следующий диапазон не меньше предыдущего. Это позволяет значительно сократить количество рассматриваемых значений N. Кроме того, максимальное допустимое значение для N легко найти аналитически.

Рассмотрим теперь задачу поиска в упорядоченном массиве наибольшего «равнинного» участка. То есть, требуется найти такое число p, что в массиве имеется последовательность из p равных элементов и нет последовательности из p + 1 равных по значению элементов. Оказывается, существует алгоритм решения этой задачи, количество операций в котором может оказаться существенно меньше, чем N. Так, если мы уже нашли последовательность из p1 равных между собой чисел, то другую последовательность имеет смысл теперь рассматривать только если ее длина не менее p1 + 1. Поэтому, если a[i] — первый элемент предполагаемой новой подпоследовательности, то сравнивать его надо сразу с элементом a[i+p], где p — максимальная величина для уже рассмотренных подпоследовательностей из равных элементов. Приведем фрагмент программы, решающий данную задачу. В качестве результата мы получаем длину максимальной подпоследовательности p, номер элемента, с которого эта подпоследовательность начинается, k и значение элементов в найденной подпоследовательности:

p:=1; k:=1;
i:=1; f:=false;

while i+p<=N do
  if a[i+p]=a[i] then
  begin
    p:=p+1; f:=true
  end
  else 
    if f then 
    begin 
      k:=i; i:=i+p; f:=false 
    end
    else 
      i:=i+1;
writeln(p,’ ’,k, ’ ’,a[k])

Пусть имеются три упорядоченных по алфавиту списка из фамилий людей, получающий пособие по безработице в трех различных местах. Длина каждого из списков может быть как угодно большой (каждый из списков можно хранить в отдельном файле). Известно, что по крайней мере одно лицо фигурирует во всех трех списках. Требуется написать программу поиска такого лица, порядок количества операций в которой не будет больше, чем сумма длин всех трех списков. Приведем фрагмент программы, работающий с тремя файлами, обращение к элементам которых (они могут быть любого типа, в том числе и string, к элементам которого в Паскале применимы операции сравнения, чтения и записи) из программы происходит с помощью файловых переменных x, y, z типа text:

readln(x,p); readln(y,q); readln(z,r);

while not((p=q)and(q=r)) do
begin
  if p<q then 
    readln(x,p)
  else 
    if q<r then 
      readln(y,q)
    else 
      if r<p then
        readln(z,r)
end;

writeln(p);  { p=q=r }

Покажите, что для поставленной задачи чтение из файла всегда будет производиться корректно и на каждом шаге цикла значение одной из трех переменных p, q, r будет изменено. Кроме того докажите, что с помощью этой программы всегда будет найден именно минимальный из элементов, присутствующих во всех трех файлах.

Наконец, рассмотрим задачу поиска элемента, значение которого равно K, в двухмерном массиве, упорядоченном по строкам и столбцам:

a[i,j] <= a [i,j+1], a[i,j] <= a[i+1,j], 1 <= i < N, 1 <= j < M.

Данная задача решается за M + N действий, а не за M*N, как в произвольном массиве. Поиск следует начинать с элемента a[N,1]. Этот элемент самый маленький в своей строке и самый большой в своем столбце (в математике подобные элементы называют “седловыми точками”). Поэтому, если он окажется меньше, чем K, то из рассмотрения первый столбец можно исключить, а если больше — из рассмотрения исключается последняя строка и т. д. Вот возможная реализация этого алгоритма:

i:=N; j:=1;
while (i>0)and(j<M+1)and(a[i,j]<>K) do
  if a[i,j]<K then 
    j:=j+1
  else 
    i:=i-1;
if (i>0)and(j<M+1) then 
  writeln(a[i,j])

Программа могла бы быть еще короче и эффективней, если бы в ней использовался упоминавшийся выше барьерный метод. В данном случае для организации барьера требуется дополнить массив нулевой строкой и m+1-м столбцом. Во все созданные барьерные элементы следует поместить значение K. Тогда условие в цикле можно сократить до следующего: a[i,j]<>K.

Алгоритмы поиска и задачи на взвешивания

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

В качестве примера рассмотрим задачу, предлагавшуюся на теоретическом туре одной из региональных олимпиад по информатике. Пусть у нас имеется 12 монет, одна из которых фальшивая, по весу отличающаяся от остальных монет, причем неизвестно, легче она или тяжелее. Требуется за три взвешивания определить номер фальшивой монеты (попробуйте решить эту задачу самостоятельно и вы убедитесь, что это совсем не просто, а порой вообще кажется невозможным). Введем следующие обозначения. Знаком “+” будем обозначать монеты, которые во время текущего взвешивания следует положить на весы, причем, если монета на весах уже была, то на ту же самую чашу, на которой эта монета находилась во время своего предыдущего взвешивания. Знаком “-“ будем обозначать монеты, которые следует переложить на противоположную чашу весов, по отношению к той, на которой они находились (каждая в отдельности), заметим, что если монета на весах еще не была, то знак “-“ к ней применен быть не может. Наконец, знаком “0” — монеты, которые в очередном взвешивании не участвуют. Тогда, существует 14 различных способов пометки монет для трех взвешиваний:

1 2 3 4 5 6 7 8 9 10 11 12 13 14
+ + + + + + + + +  0  0  0  0  0 — первое взвешивание
+ + + - - - 0 0 0  +  +  +  0  0 — второе взвешивание
+ - 0 + - 0 + - 0  +  -  0  +  0 — третье взвешивание

Из полученной таблицы вычеркнем 2 столбца так, чтобы в каждой из трех строк количество ненулевых элементов оказалось четным (ведь мы не можем во время одного взвешивания положить на две чаши весов нечетное число монет). Это могут быть, например, столбцы 4 и 14. Теперь будем взвешивать 12 монет так, как это записано в оставшихся 12 столбцах. То есть, в первом взвешивании будут участвовать 8 произвольных монет, во втором — три монеты следует с весов убрать, две — переложить на противоположные по отношению к первому взвешиванию чаши весов и три монеты положить на весы впервые (на свободные места так, чтобы на каждой из чаш вновь оказалось по 4 монеты). Согласно схеме проведем и третье взвешивание, опять располагая на каждой чаше весов по 4 монеты. Результат каждого взвешивания в отдельности никак не анализируется, а просто записывается. При этом равновесие на весах всегда кодируется нулем, впервые возникшее неравновесное состояние — знаком плюс, если при следующем взвешивании весы отклонятся от равновесия в ту же самую сторону, то результат такого взвешивания также кодируется плюсом, а если в другую сторону — то минусом. Например, записи “=<<” и “=>>” кодируются как “0++”, а записи “<=>” и “>=<” — как “+0-“. Так как мы не знаем, легче или тяжелее остальных монет окажется фальшивая, то нам важно как изменялось состояние весов от взвешивания к взвешиванию, а не то какая именно чаша оказывалась тяжелее, а какая легче. Поэтому два, на первый взгляд, различных результата трех взвешиваний в этом случае кодируются одинаково. После подобной записи результатов взвешиваний фальшивая монета уже фактически определена. Ею оказывается та, которой соответствует такой же столбец в таблице, как и закодированный нами результат трех взвешиваний. Для первого из примеров это монета, которая участвовала во взвешиваниях по схеме, указанной в 10-м столбце таблицы, а для второго — в 8-м. В самом деле, состояние весов в нашей задаче меняется в зависимости от того, где оказывается фальшивая монета во время каждого из взвешиваний. Поэтому монета, “поведение” которой согласуется с записанным результатом взвешиваний, такой результат и определяет.
Анализ таблицы показывает, что эту задачу можно решить не только для 12, но и для 13 монет. Для этого следует исключить из рассмотрения любой не содержащий нулей столбец, например, все тот же четвертый. В остальном все действия остаются неизменными. Для произвольного числа монет N>2 количество взвешиваний при определяется по формуле round(log3(2*N + 1)) (за одно взвешивание задача не разрешима ни для какого количества монет!!!), но подход к решению задачи при этом не изменится.

Попробуйте теперь решить задачу, которая предлагалась в 1998 году на уже упоминавшемся выше полуфинале чемпионата мира по программированию среди студенческих команд вузов. В ней также требовалось определить номер фальшивой монеты, вес которой отличался от остальных. Но все взвешивания уже были проведены, а их результаты записаны. Число взвешиваний являлось входным параметром в задаче (оно могло быть и избыточным по сравнению с описанным выше оптимальным алгоритмом определения номера фальшивой монеты). При этом в каждом из взвешиваний могло участвовать любое четное количество имеющихся монет (сколько и какие именно — известно). Результаты записывались с помощью символов “<”, “>” и “=”.

Еще одна задача на взвешивания рассмотрена в [8]. В общем случае в ней требуется найти набор из минимального количества гирь такой, что с его помощью можно взвесить любой груз, весящий целое число килограмм, в диапазоне от 1 кг до N кг. При необходимости гири можно располагать на обеих чашах весов. Так, для N=40 это гири 1, 3, 9 и 27 кг.

Поиск подстроки в строке

Формализовать эту задачу можно следующим образом. Пусть задан массив s из N элементов (строка) и массив p из M элементов (подстрока), причем 0p в s. Эта задача на практике встречается очень часто. Так, в большинстве текстовых редакторов реализована операция поиска по образцу, которая практически полностью совпадает с описанной задачей. Если размер массива s — N не превосходит 255, а тип его элементов — char, то в Турбо Паскале такой поиск можно выполнять с помощью стандартной функции Pos(p,s). Однако, в общем случае ее приходится реализовывать самостоятельно. Прямой поиск, основанный на последовательном сравнении подстроки сначала с первыми M символами строки, затем с символами с номерами 2 — M+1 и т. д., в худшем случае произведет порядка N*M сравнений. Но для этой задачи известен алгоритм Боуера и Мура, который для произвольных строк выполняет не намного более N/M сравнений. То есть разница в вычислительной сложности составляет M^2 Рассмотрим последний алгоритм, на примере которого также можно показать, что использование небольшого количества дополнительной памяти (в данном случае вспомогательного массива, размер которого равен размеру алфавита строк) позволяет существенно ускорить выполнение программы.

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

кокаколулюбитикоала.
коала
коала
коала
коала
коала

Здесь выделены жирным символы, которые участвовали в сравнениях. Сдвиги определялись такими значениями массива d: d['к']=4, d['л']=1, d['ю']=5. Если бы последней в рассматриваемом фрагменте строки оказалась буква а, то величина сдвига была бы равна 2, так как в образце есть еще одна такая буква, отстоящая от конца на 2 символа, а при ее отсутствии сдвиг был бы равен 5. Приведем теперь возможную реализацию описанного алгоритма, для простоты считая, что размер подстроки не превосходит 255, что не снижает общности этой программы:

const nmax=10000;
var p:string; {подстрока}
  s:array[1..nmax]of char; {строка}
  d:array[char]of byte; {массив сдвигов}
  c:char;
  m,i,j,k:integer;
begin
  …{задание строки и подстроки}
  m:=length(p);{длина подстроки}
  for c:=chr(0) to chr(255) do d[c]:=m;
  for j:=1 to m-1 do d[p[j]]:=m-j;
  {массив d определен}
  i:=m+1;
  repeat {выбор фрагмента в строке}
    j:=m+1; k:=i;
    repeat {проверка совпадения}
      k:=k-1; j:=j-1
    until (j<1)or(p[j]<>s[k]);
    i:=i+d[s[i-1]];{сдвиг}
  until (j<1)or(i>nmax+1);
  if j<1 then write(k+1) else write(0)
end.

Приведенный алгоритм не дает выигрыша только в одном случае — когда количество частичных совпадений искомой подстроки с фрагментами текста достаточно велико. Это возможно, например, при чрезвычайной ограниченности алфавита, из символов которого составляются строки. Тогда следует применять алгоритм Кнута-Мориса-Пратта, или комбинацию из двух алгоритмов.

Рассмотренную проблему не следует путать с такой задачей. Пусть задан массив s из N элементов и массив p из M элементов, причем 0<M<=N. Требуется выяснить, можно ли из первого массива вычеркнуть некоторые члены так, чтобы он совпал со вторым. Число операций в данном случае имеет порядок N + M.