Оценивание: творческая задача, 30 баллов.
Вам необходимо реализовать некоторую коллекцию индексированных данных некоторого типа T, выглядящую как несколько необычный массив. Вместо операции присваивания значения элементу массива в нём имеется операция присваивания одинаковых значений всем элементам для некоторого диапазона индексов. Также и операции поиска минимума и максимума должны работать для некоторого диапазона значений индексов. Полностью интерфейс SegmentedArray выглядит так.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/** * An array with special operations. * @param <T> the type of elements in this array * * @author Igor Mazurok */ public interface SegmentedArray<T> { /** * <p>Get value by element index</p> * @param index index of element. * @return Value of element with specified index. */ T get(int index); /** * <p>Set the same value for all elements in the specified index range</p> * @param start the beginning index, inclusive. * @param end the ending index, exclusive. * @param value value for. * @return This object. */ SegmentedArray<T> set(int start, int end, T value); /** * <p>Returns the index within this array of the first occurrence of the specified value, * starting at the specified index. If no such value of k exists, then -1 is returned.</p> * @param value the T-based value for which to search. * @param fromIndex the index from which to start the search. * @return the index within this array of the first occurrence of the element with specified value, * starting at the specified index. */ int indexOf(T value, int fromIndex); /** * <p>Find minimum value in the specified indexes range</p> * @param start the beginning index, inclusive. * @param end the ending index, exclusive. * @return Minimum value. */ T minValue(int start, int end); } |
При написании класса, реализующего данный интерфейс необходимо стремиться к максимальной эффективности выполнения наиболее частых операций и учитывать особенности использования отражённые в следующей таблице с заданиями:
| Big array |
Small |T| |
Often | Student | |||
|---|---|---|---|---|---|---|
| get() | set() | indexOf() | min()/max() | |||
| 1 | 1 | 0 | 1 | 0 | 0 | Куленюк |
| 1 | 0 | 1 | 0 | 0 | 0 | Карташов |
| 0 | 0 | 1 | 1 | 0 | 0 | Денисова |
| 0 | 1 | 0 | 1 | 0 | 0 | Марченко |
| 1 | 0 | 0 | 0 | 1 | 0 | Швандт |
| 0 | 0 | 0 | 0 | 0 | 1 | Сорокина |
| 1 | 0 | 1 | 0 | 0 | 1 | Осецимский |
| 0 | 0 | 1 | 1 | 1 | 1 | Иванов |
| 1 | 1 | 0 | 1 | 1 | 0 | Вустянюк |
Для каждого из разработанных алгоритмов необходимо определить и обосновать асимптотическую оценку вычислительной сложности. Для функций, которые в Вашем варианте задания будут вызываться часто, вычислительная сложность алгоритмов должна быть как можно более низкой.
Пример тестирующего метода для полученной структуры:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
public static void testSegmentedArray1(SegmentedArray<Integer> arr) { long start = System.nanoTime(); //Предположим, что параметром метода является //нулевой массив размера 1000 if (arr.get(30)!=0) System.out.println("Non zero element in empty array"); if (arr.minValue(0,1000)!=0) System.out.println("Non zero minimum in empty array"); arr.set(0,200,1); arr.set(100,300,2); arr.set(150,160,1); if (arr.get(30)!=1) System.out.println("Element is not set"); if (arr.get(300)!=0) System.out.println("End should be exclusive"); if (arr.get(125)!=2) System.out.println("Element is not set (2 assigments)"); if (arr.get(150)!=1) System.out.println("Element is not set (3 assigments)"); if (arr.minValue(100,300)!=1) System.out.println("Wrong minimum calculation (two values)"); if (arr.minValue(100,301)!=0) System.out.println("Wrong minimum calculation (two values and zero)"); if (arr.minValue(155,156)!=1) System.out.println("Wrong minimum calculation (single element)"); long finish = System.nanoTime(); System.out.println("Test 1 (small array) completed!"); System.out.format("Time elapsed: %.3f ms", (finish-start)/1e6); // ns -> ms } |
Представлен наиболее простой и универсальный проверочный метод, хорошо тестирует он разве что структуру, характеризуемую набором (0, 1, 0, 0, 0, 0) — маленький массив, редкие операции. В действии пример можно увидеть здесь.
Вариант интерфейса для групп Антоненко А.С.:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
/** * An integer array with special operations. * * @author Igor Mazurok * @author Alexander Antonenko */ public interface IntSegmentedArray { /** * <p>Get size of array</p> * @return Size of array. */ int size(); /** * <p>Get value by element index</p> * @param index index of element. * @return Value of element with specified index. */ int get(int index); /** * <p>Set the same value for all elements in the specified index range</p> * @param start the beginning index, inclusive. * @param end the ending index, exclusive. * @param value value for. * @return This object. */ SegmentedArray set(int start, int end, int value); /** * <p>Add some value to all elements in the specified index range * (for binary task adding modulo 2).</p> * @param start the beginning index, inclusive. * @param end the ending index, exclusive. * @param value value for adding. * @return This object. */ SegmentedArray add(int start, int end, int value); /** * <p>Find minimum value in the specified indexes range</p> * @param start the beginning index, inclusive. * @param end the ending index, exclusive. * @return Minimum value. */ int minValue(int start, int end); } |
| Big array |
Binary | Often | Student | |||
|---|---|---|---|---|---|---|
| get() | set() | add() | min()/max() | |||
| 1 | 1 | 1 | 1 | 0 | 0 | Илларионова |
| 0 | 0 | 1 | 1 | 0 | 1 | Фесенко |
| 1 | 0 | 1 | 0 | 0 | 0 | Сиренко |
| 0 | 1 | 0 | 0 | 1 | 1 | Кваша |
| 1 | 0 | 0 | 0 | 0 | 1 | Григорян |
| 0 | 1 | 1 | 1 | 0 | 0 | Зелинский |
| 1 | 0 | 1 | 0 | 0 | 0 | Ковальский |
| 0 | 0 | 0 | 0 | 1 | 0 | Калачёв |
| 1 | 1 | 0 | 0 | 0 | 1 | Бровко |
| 0 | 0 | 1 | 1 | 1 | 0 | Байков |
| 1 | 1 | 1 | 0 | 0 | 1 | Недомовный |