Skip to content

Latest commit

 

History

History
83 lines (54 loc) · 5.88 KB

README.md

File metadata and controls

83 lines (54 loc) · 5.88 KB

GetEqlElemsForMinOpers

Решение задачи программирования на тему "Минимальное число шагов для обеспечения равенства всех элементов массива" на языке Java

ФОРМУЛИРОВКА ЗАДАЧИ:

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

ПРОГРАММНЫЙ КОД:

Исходный программный код содержится в файле src\GetEqlElemsForMinOpers.java.

НАЗНАЧЕНИЕ:

Класс GetEqlElemsForMinOpers реализует

  • метод CalcEqlElemsForMinOpers, который решает следующую задачу: "Дан массив целых чисел длины N и целое число K. Разрешена операция удаления первого элемента массива с записью в его конец K-го элемента. Какое минимальное число шагов потребуется для того, чтобы сделать все элементы массива одинаковыми? -1, если это невозможно.";
  • метод main, обеспечивающий консольный интерфейс взаимодействия с пользователем, контроль корректности вводимых пользователем данных, вызов метода CalcEqlElemsForMinOpers, вывод результатов работы приложения в консоль.

АЛГОРИТМ:

Необходимо проверить равенство всех элементов массива с индексами >= K. Если равенство не выполняется, то перестроение требуемого массива невозможно. Если выполняется, то необходимо рассчитать минимально необходимое количество шагов перестроения массива, проверяя уже выстроенные и еще не выстроенные элементы массива с индексами < K.

СЛОЖНОСТЬ:

В приложении реализован алгоритм с линейной временной сложностью O(n), определяемой размером n входного массива данных.

РЕАЛИЗАЦИЯ:

Java version "11.0.1", использованы стандартные возможности JDK.

ОГРАНИЧЕНИЯ:

Приложение допускает ввод и обработку чисел типа Integer, которые могут быть заданы во входном массиве.

ТЕСТИРОВАНИЕ:

Количество шагов перестроения тестовых массивов с N элементами для различных номеров K переставляемых элементов в массиве представлены в таблице:

массив N K = 1 K = 2 K = 3
0 0
0 1 -1 1
1 1 0 0
0 0 1 -1 -1 2
0 1 0 -1 -1 2
0 1 1 -1 1 1
1 1 1 0 0 0

КОНТРОЛЬНЫЙ ПРИМЕР выполнения приложения:

<Минимальное число шагов для обеспечения равенства всех элементов массива> NesioIV, 2022

Текущее состояние массива: [ ]
Добавить элемент массива (Y - да / N - нет)? Y
Введите элемент массива (целое число 2147483648 <= A <= 2147483647): -2
Текущее состояние массива: [-2]
Добавить элемент массива (Y - да / N - нет)? Y
Введите элемент массива (целое число -2147483648 <= A <= 2147483647): -1
Текущее состояние массива: [-2, -1]
Добавить элемент массива (Y - да / N - нет)? Y
Введите элемент массива (целое число -2147483648 <= A <= 2147483647): 0
Текущее состояние массива: [-2, -1, 0]
Добавить элемент массива (Y - да / N - нет)? Y
Введите элемент массива (целое число -2147483648 <= A <= 2147483647): 1
Текущее состояние массива: [-2, -1, 0, 1]
Добавить элемент массива (Y - да / N - нет)? N

Введите номер переставляемого элемента массива (целое число 1 <= K <= 4): 4

ВЫПОЛНЯЕТСЯ РАСЧЕТ минимального количества шагов для обеспечения равенства всех элементов массива...

Исходное состояние массива: [-2, -1, 0, 1]
Номер переставляемого элемента массива: 4

ОТВЕТ: 3
// расшифровка: -1 (перестроение невозможно); 0 (перестроение не требуется); N (требуется N шагов перестроения).

Время выполнения, мс: 0

= Выполнение приложения завершено =

Process finished with exit code 0