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

16. Задан массив, не содержащий нулевых значений. Найти в нем:

а) самую длинную подпоследовательность значений одного знака:

б) самую длинную знакопеременную подпоследовательность.

17. Задан массив натуральных чисел. Найти в нем самую длинную группу элементов,

а) стоящих на последовательных четных местах и имеющих нечетные значения:

б) стоящих на последовательных нечетных местах и имеющих четные значения.

18. Дан целочисленный массив. Найти в нем подпоследовательность максимальной длины, представляющую собой арифметическую прогрессию.

19. * Задан числовой массив A из n элементов. Ступенькой назовем такие элементы A[i], A[i+1], ..., A[j], что:

1) A[k]<A[k+1], k=i, i+1, ..., j-1;

2) A[i-1]>=A[i], если i>1 и A[j]>=A[j+1], если j<n.

Высотой ступеньки назовем разность A[j]-A[i], а длиной – количество элементов массива, входящих в ступеньку. Вычислить:

1) высоту и длину каждой из ступенек;

2) высоту самой длинной ступеньки;

3) длину самой высокой ступеньки.

20. *Задан целочисленный массив A длиной n. Убывающей "пилой" назовем такую последовательность A[i], … , A[j], что для каждой тройки элементов последовательности A[k], A[k+1], A[k+2] выполняется одно из условий:

1) A[k]<A[k+1]>A[k+2] и A[k]>A[k+2];

2) A[k]>A[k+1]<A[k+2] и A[k]>A[k+2].

Глубиной "пилы" назовем разность между максимальным и минимальным элементами массива в ней. Найти самую глубокую "пилу".

21. *Задан целочисленный массив A длиной n. Возрастающей "пилой" назовем такую последовательность A[i], … , A[j], что для каждой тройки элементов последовательности A[k], A[k+1], A[k+2] выполняется одно из условий:

1) A[k]<A[k+1]>A[k+2] и A[k]<A[k+2];

2) A[k]>A[k+1]<A[k+2] и A[k]<A[k+2].

Длиной "пилы" назовем количество элементов в ней. Найти самую длинную "пилу".

22. * Задан целочисленный массив X. Найти в нем все такие подпоследовательности X[i], X[i+1], ... , X[i+s], для которых выполняется:

X[i] + X[i+1] + ... + X[i+s] = X[i+s+1] при s > 0.

Определить среди них:

а) подпоследовательность максимальной длины;

б) подпоследовательность, имеющую максимальную сумму элементов.

Примечание: подпоследовательности могут перекрываться.

23. * Задана ломаная линия набором n точек плоскости в виде массивов координат {X[1], Y[1]}, … , {X[n], Y[n]}. Часть ломаной с i-й точки по j-ю, для которой выполнено условие:

{X[i]<=X[i+1], Y[i]<=Y[i+1]}, …, {X[j-1]<=X[j], Y[j-1]<=Y[j]}

назовем восходящей трассой, а евклидово расстояние между i-й и j-й точками – длиной восходящей трассы. (Расстояние между точками равно квадратному корню из суммы квадратов разностей координат). Вывести длину и точки каждой трассы.

24. * Задана ломаная линия набором n точек плоскости в виде массивов координат {X[1], Y[1]}, …, {X[n], Y[n]}. Часть ломаной с i-й точки по j-ю, для которой выполнено условие:

{X[i]<=X[i+1], Y[i]>=Y[i+1]}, … , {X[j-1]<=X[j], Y[j-1]>=Y[j]}

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

{X[i]<=X[i+1], Y[i]<= Y[i+1]}, … , {X[j-1]<=X[j], Y[j-1]<=Y[j]}

– восходящей трассой, а количество точек трассы – мощностью трассы. Вывести точки линии по трассам, вначале для нисходящих трасс, а затем для восходящих трасс.

25. ** Задан целочисленный массив A из n элементов. Найти самую длинную группу элементов массива A с равными значениями, которые расположены на одинаковых расстояниях друг от друга:

A[i] = A[i + k] = ... = A[j].

26. * Задан числовой массив A из n элементов, расположенных по возрастанию. Из этих элементов сформировать такую арифметическую прогрессию максимальной длины, чтобы:

1) 1-й элемент прогрессии совпадал с элементом A[1],

2) 2-й и последующие элементы прогрессии совпадали с некоторыми из элементов массива A,

3) разность между A[n] и последним элементом прогрессии была меньше разности между соседними элементами прогрессии.

27. * Задан числовой массив A из n положительных элементов, расположенных по убыванию. Из этих элементов сформировать такую геометрическую прогрессию максимальной длины, чтобы:

1) 1-й элемент прогрессии совпадал с элементом A[1],

2) 2-й и последующие элементы прогрессии совпадали с некоторыми из элементов массива A,

3) отношение между A[n] и последним элементом прогрессии было больше отношения между соседними элементами прогрессии.