Подпоследовательность – арифметическая прогрессия

Опубликовано Mar 16, 2012 в Массивы и строки | 13 коммент.

, , , ,

Подпоследовательность – арифметическая прогрессия

Дан массив произвольной длины. Определить, с какого его элемента начинается подпоследовательность, которая будучи арифметической прогрессией, имеет максимальную длину.

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

Итак, какие вопросы уместны в данном случае?

1) Разность прогрессии может быть любым или ищем прогрессию максимальной длины с заданной разностью? От ответа, очевидно, зависит алгоритм.

2) Что должна вернуть функция в случае удачи? Имеются два здравых варианта:

  • индексы/итераторы на начало и конец найденной подпоследовательности (begin_pro и end_pro);
  • индекс/итератор на начало найденной подпоследовательности и количество элементов в ней – оба этих варианта присутствуют среди решений (begin_pro и nmax);
  • возможен еще логический выходной параметр с очевидным смыслом (нашли/не нашли).

3) Что должна вернуть функция в случае неудачи, когда в массиве нет подпоследовательности-прогрессии? И что, собственно, такое арифметическая прогрессия – два элемента или больше двух?

  • Разумным кажется рассматривать подпоследовательность больше, чем из двух элементов, как это справедливо замечено в комментариях.  
  • Если такая подпоследовательность отсутствует, то разумно вернуть сочетание выходных параметров из пункта 2), которое однозначно трактуется как то, что прогрессия не найдена.  Например, равные  значения begin_pro и end_pro, указывающие на последний элемент массива, или begin_pro  указывает на последний элемент, а nmax = 0, (1, 2). В вызывающей программе проверка на то, что прогрессия не найдена, должна однозначно выполняться по значениям этих выходных параметров, без вовлечения в if самого массива, поэтому возврат индексов/итераторов за границами массива кажется не самым лучшим вариантом.

4) Что должна вернуть функция, если подпоследовательностей, удовлетворяющих условию больше, чем одна? Например, данные о самой первой или самой последней такой последовательности. Развитием этого сюжета является построение динамической структуры данных, для возврата всех правильных вариантов ответа.

 


Автор публикации: