Найдите отрезок массива максимальной длины, в котором первое число равно последнему, второе – предпоследнему

@_TheMaster · Регистрация: 29.01.2022

Author24 — интернет-сервис помощи студентам

Перевёртыши

Задан числовой массив a[n]. Найдите отрезок массива максимальной длины, в котором первое
число равно последнему, второе – предпоследнему и так далее.
Если подходящих отрезков несколько, выведите первый по порядку.
Формат ввода: первая строка: n. n ≤ 7000. Вторая строка: элементы
массива. -maxint ≤ a[i] ≤ maxint
Формат вывода: искомый отрезок.
input.txt
9
5 3 4 7 4 3 6 6 3
output.txt
3 4 7 4 3

@gunslinger · 14.06.2022, 08:11

Ниже приведен код ("набросок"), содержащий структуру с двумя полями index (начальный индекс отрезка) и count (общее количество "элементов отрезка"), а также функция, находящая эти значения (index и count) для исходного массива.

C++

struct Segment
{
  unsigned index, count;
};
 
Segment max_segment(int *a, unsigned n)
{
  Segment result, tmp;
  result.index = 0;
  result.count = 1;
  unsigned i, j;
 
  for (i = 0; i < n; i++)
  {
    tmp.index = i;
    tmp.count = 1;
    for (j = 1; j <= i; j++)
    {
      if (a[i + j] == a[i - j])
      {
        tmp.count += 2;
        if (tmp.count > result.count)
        {
          result.index = i - tmp.count / 2;
          result.count = tmp.count;
        }
      }
      else
      {
        tmp.count = 1;
        break;
      }
    }
  }
 
  return result;
}

Для примера, приведенного выше, функция вернет значения 1 (начало отрезка - индекс элемента массива) и 5 (количество элементов).
Нужно только не забыть (если нужно), объявить переменную типа Segment и вывести элементы отрезка.
Вариант кода в билдере:

C++

  const n = 9;
  int a[n] = {5, 3, 4, 7, 4, 3, 6, 6, 3};
 
  Segment result = max_segment(a, n);
 
  String tmp = String(result.index) + " : " + String(result.count);
  ShowMessage(tmp);

Добавлено через 14 минут
Замечу еще, что в условии

C++

17	for (j = 1; j <= i; j++)

нужно дополнительно добавить ограничение, чтобы не было выхода за границы массива.
Это оставляю для самостоятельной работы.

@_TheMaster 0 / 0 / 0 Регистрация: 29.01.2022 Сообщений: 19
		1
	Найдите отрезок массива максимальной длины, в котором первое число равно последнему, второе – предпоследнему 13.06.2022, 22:32. Показов 639. Ответов 1 Метки нет (Все метки) Перевёртыши Задан числовой массив a[n]. Найдите отрезок массива максимальной длины, в котором первое число равно последнему, второе – предпоследнему и так далее. Если подходящих отрезков несколько, выведите первый по порядку. Формат ввода: первая строка: n. n ≤ 7000. Вторая строка: элементы массива. -maxint ≤ a[i] ≤ maxint Формат вывода: искомый отрезок. input.txt 9 5 3 4 7 4 3 6 6 3 output.txt 3 4 7 4 3 0

	14.06.2022, 08:11

Опции темы