Основы алгоритмов в программировании на Java. Практические Задания

Девять практических заданий закрепляют алгоритмы из курса: сортировки, вычисление среднего, числа Фибоначчи, оценку сложности по O-нотации, обмен значений (swap), разворот массива и поиск элемента. Каждое задание опирается на конкретный урок и предлагает разобрать код в отладчике, заполнить таблицу трассировки или доработать реализацию.

1. Debug сортировки пузырьком.

1. Создать табличку для любого массива, в котором последовательно прописать значения i, j и массива для каждого цикла алгоритма сортировки пузырька.
2. Используйте debugger.
3. Например, для массива 0 2 5 3 4:

   Шаги дебага

   i	j	Значение массива	Выполнился ли блок if?
   0	4	0 2 5 3 4	-
   0	3	0 2 3 5 4	+
   0	2	0 2 3 5 4	-
   0	1	0 2 3 5 4	-
   1	4	0 2 3 4 5	+
   1	3	0 2 3 4 5	-
   1	2	0 2 3 4 5	-
   2	4	0 2 3 4 5	-
   2	3	0 2 3 4 5	-
   3	4	0 2 3 4 5	-
   4	-	0 2 3 4 5	-

2. Модифицировать сортировку пузырьком.

1. Изменить программу сортировки пузырьком: 
   а) добавить возможность досрочного окончания сортировки; 
   б) программа написана таким образом, что минимальный элемент "всплывает" в начало массива. Измените программу так, чтобы минимальный элемент "всплывал" в конец массива (внутренний цикл for должен перебирать элементы не с конца, а с начала).

   public class BubbleSorter {
       public static void sort(int[] array) {
           for (int i = 0; i < array.length; i++) {
               for (int j = array.length - 1; j > i; j--) {
                   if (array[j - 1] > array[j]) {
                       int tmp = array[j - 1];
                       array[j - 1] = array[j];
                       array[j] = tmp;
                   }
               }
           }
       }
   }

3. Debug сортировки выбором.

Сделать задание 1 для алгоритма сортировки выбора.

1. Изменить сортировку выбором - исключите обмен значений, если найденный минимальный элемент уже находится на своем месте.

   public class SelectionSorter {
       public static void sort(int[] array) {
           for (int i = 0; i < array.length; i++) {    // i - номер текущего шага
               int pos = i;
               int min = array[i];
               // цикл выбора наименьшего элемента
               for (int j = i + 1; j < array.length; j++) {
                   if (array[j] < min) {
                       pos = j;    // pos - индекс наименьшего элемента
                       min = array[j];
                   }
               }
               array[pos] = array[i];
               array[i] = min;    // меняем местами наименьший с array[i]
           }
       }
   }

4. Найти ошибку в подсчёте среднего арифметического

Дан метод, который должен считать среднее арифметическое элементов массива int[]:

public class AverageCalculator {
    public static double average(int[] array) {
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        int count = array.length;
        return sum / count;
    }
}

1. Запустите метод для массива {1, 2, 3, 4}. Ожидаемый результат — 2.5, но программа вернёт 2. Найдите причину с помощью debugger, проверив, каким получается результат деления sum / count до присвоения переменной типа double.
2. Исправьте ошибку, опираясь на раздел про целочисленное деление в уроке «Среднее арифметическое».
3. Добавьте проверку на пустой массив (array.length == 0): метод не должен выбрасывать ArithmeticException, а должен возвращать 0.

5. Сравнить рекурсию и цикл для чисел Фибоначчи

1. Возьмите рекурсивный метод и метод через цикл для вычисления чисел Фибоначчи из урока «Числа Фибоначчи в Java».
2. Замерьте время выполнения (System.currentTimeMillis() до и после вызова) для n = 30, n = 35 и n = 40 для обеих реализаций. Запишите результаты в таблицу.

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

   n	Рекурсия	Цикл
   30
   35
   40

3. Объясните результат: почему рекурсивная реализация резко замедляется с ростом n? Свяжите ответ со сложностью O(2^n) и O(n), рассмотренной в уроке.
4. Добавьте в рекурсивный метод мемоизацию (кэширование уже посчитанных значений в HashMap<Integer, Long>) и повторите замер для n = 40.

6. Определить сложность алгоритма по коду

Для каждого метода определите сложность по O-нотации, опираясь на урок «Сложность алгоритма и O-нотация», и обоснуйте ответ одним предложением.

// A
public static int first(int[] array) {
    return array[0];
}

// B
public static int sum(int[] array) {
    int s = 0;
    for (int x : array) {
        s += x;
    }
    return s;
}

// C
public static boolean hasDuplicate(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] == array[j]) {
                return true;
            }
        }
    }
    return false;
}

// D
public static int binarySearch(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

1. Заполните таблицу.

   Сложность методов A–D

   Метод	O-нотация
   A
   B
   C
   D

2. Проверьте себя: замерьте время выполнения метода hasDuplicate для массивов из 1 000, 10 000 и 100 000 элементов и убедитесь, что рост времени соответствует вашей оценке сложности.

7. Доказать, что метод swap не работает для примитивов

1. Напишите метод swap(int a, int b) из урока «Метод swap в Java: обмен значениями двух переменных» и вызовите его для двух локальных переменных. С помощью debugger (или вывода в консоль до и после вызова) убедитесь, что значения переменных в вызывающем методе не поменялись.
2. Объясните почему — опираясь на то, как Java передаёт параметры примитивных типов: по значению, а не по ссылке.
3. Напишите метод swap(int[] array, int i, int j), который меняет местами два элемента массива по индексам, и докажите, что в этом случае обмен работает: параметр-ссылка указывает на тот же массив, а меняются его элементы, а не сам параметр.
4. Используйте написанный swap для массива внутри собственной реализации сортировки пузырьком или сортировки выбором вместо обмена через временную переменную "в лоб".

8. Трассировка алгоритма разворота массива

1. Возьмите метод разворота массива на месте (два указателя left и right) из урока «Как перевернуть (развернуть) массив в Java».
2. Для массива {1, 2, 3, 4, 5} заполните таблицу шагов, как в задании 1, отмечая значения left, right и состояние массива на каждой итерации цикла.

   Шаги разворота массива

   left	right	Значение массива

3. С помощью debugger проверьте, сколько итераций цикла потребовалось для массива из 5 и из 6 элементов, и объясните разницу для чётной и нечётной длины массива.
4. Напишите вариант метода, который не изменяет исходный массив, а возвращает новый перевёрнутый массив, и сравните расход памяти (space complexity) с версией "на месте".

9. Сравнить линейный и бинарный поиск

1. Возьмите реализации линейного и бинарного поиска из урока «Поиск элемента в массиве в Java».
2. Добавьте в оба метода счётчик сравнений (int comparisons) и выведите его значение после завершения поиска.
3. Создайте отсортированный массив из 100 элементов и найдите в нём: первый элемент, последний элемент и элемент, которого в массиве нет. Заполните таблицу количеством сравнений для каждого случая.

   Количество сравнений

   Что ищем	Линейный поиск	Бинарный поиск
   Первый элемент
   Последний элемент
   Элемент, которого нет

4. Объясните, почему количество сравнений в бинарном поиске почти не меняется с ростом массива, а в линейном — растёт пропорционально. Свяжите ответ с уроком «Сложность алгоритма и O-нотация».

При написании программ обращайте внимание на рекомендации по оформлению кода.