> For the complete documentation index, see [llms.txt](https://letas-organization.gitbook.io/letaats-lessons-online/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://letas-organization.gitbook.io/letaats-lessons-online/kolledzh-top/razdel-1/glava-11.-bazovye-algoritmy.md).

# Глава 11. Базовые алгоритмы

### 11.1. Что такое алгоритм в коде

Алгоритм — это не просто текстовое описание шагов. В программе алгоритм превращается в конкретный код.

Например, алгоритм поиска максимума:

```
1. Взять первый элемент как максимум.
2. Пройти по остальным элементам.
3. Если найден элемент больше максимума, заменить максимум.
4. Вернуть максимум.
```

Java-код:

```java
int max = numbers[0];

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i] > max) {
        max = numbers[i];
    }
}
```

***

### 11.2. Почему важно изучать простые алгоритмы

Можно подумать: “Зачем писать поиск максимума вручную, если есть готовые методы?”

Потому что простые алгоритмы учат:

* проходить по данным;
* сравнивать значения;
* накапливать результат;
* работать с условиями;
* видеть структуру задачи.

Если студент не может найти максимум в массиве, ему рано писать сложное Android-приложение. И нет, кнопка на экране это не исправит.

***

### 11.3. Алгоритм суммы

Задача: найти сумму всех элементов массива.

Идея:

```
Создать переменную sum.
Пройти по массиву.
Каждый элемент прибавить к sum.
```

Код:

```java
int sum = 0;

for (int i = 0; i < numbers.length; i++) {
    sum += numbers[i];
}
```

***

### 11.4. Алгоритм среднего значения

Среднее = сумма / количество.

```java
int sum = 0;

for (int i = 0; i < numbers.length; i++) {
    sum += numbers[i];
}

double average = (double) sum / numbers.length;
```

Важно проверить, что массив не пустой. Для обычного массива фиксированной длины это обычно известно заранее. Для `ArrayList` такая проверка будет особенно важна.

***

### 11.5. Алгоритм максимума

```java
int max = numbers[0];

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i] > max) {
        max = numbers[i];
    }
}
```

Почему цикл начинается с 1?

Потому что элемент с индексом 0 уже взят как начальный максимум.

***

### 11.6. Алгоритм минимума

```java
int min = numbers[0];

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i] < min) {
        min = numbers[i];
    }
}
```

***

### 11.7. Поиск элемента

Задача: найти, есть ли число в массиве.

```java
int target = 10;
boolean found = false;

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] == target) {
        found = true;
        break;
    }
}
```

Если элемент найден, можно завершить цикл через `break`.

***

### 11.8. Подсчёт элементов

Задача: посчитать, сколько чисел больше 0.

```java
int count = 0;

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] > 0) {
        count++;
    }
}
```

***

### 11.9. Фильтрация данных

Фильтрация — выбор только тех элементов, которые подходят под условие.

Например, нужно вывести только чётные числа:

```java
for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] % 2 == 0) {
        System.out.println(numbers[i]);
    }
}
```

Позже похожая идея будет использоваться с `ArrayList` и `Stream API`.

***

### 11.10. Поиск второго максимума

Это задача сложнее обычного максимума.

Идея:

* хранить максимум;
* хранить второй максимум;
* при проходе обновлять оба значения.

Пример:

```java
int max = Integer.MIN_VALUE;
int second = Integer.MIN_VALUE;

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] > max) {
        second = max;
        max = numbers[i];
    } else if (numbers[i] > second && numbers[i] != max) {
        second = numbers[i];
    }
}
```

`Integer.MIN_VALUE` — минимально возможное значение `int`. Его удобно использовать как стартовое значение.

***

### 11.11. Разворот массива

Задача: развернуть массив.

Было:

```
1 2 3 4
```

Стало:

```
4 3 2 1
```

Алгоритм:

* взять левый индекс;
* взять правый индекс;
* поменять элементы местами;
* сдвинуть индексы к центру.

Код:

```java
int left = 0;
int right = numbers.length - 1;

while (left < right) {
    int temp = numbers[left];
    numbers[left] = numbers[right];
    numbers[right] = temp;

    left++;
    right--;
}
```

***

### 11.12. Палиндром

Палиндром — строка, которая читается одинаково слева направо и справа налево.

Примеры:

```
казак
level
madam
```

Алгоритм:

* сравнивать первый символ с последним;
* второй с предпоследним;
* двигаться к центру.

Код:

```java
String text = "level";
boolean palindrome = true;

for (int i = 0; i < text.length() / 2; i++) {
    if (text.charAt(i) != text.charAt(text.length() - 1 - i)) {
        palindrome = false;
        break;
    }
}
```

***

### 11.13. Подсчёт символов

Задача: посчитать количество букв `a` в строке.

```java
String text = "banana";
int count = 0;

for (int i = 0; i < text.length(); i++) {
    if (text.charAt(i) == 'a') {
        count++;
    }
}
```

Результат:

```
3
```

***

### 11.14. Сортировка пузырьком

Сортировка — упорядочивание элементов.

Пузырьковая сортировка сравнивает соседние элементы и меняет их местами, если они стоят неправильно.

```java
for (int i = 0; i < numbers.length - 1; i++) {
    for (int j = 0; j < numbers.length - 1 - i; j++) {
        if (numbers[j] > numbers[j + 1]) {
            int temp = numbers[j];
            numbers[j] = numbers[j + 1];
            numbers[j + 1] = temp;
        }
    }
}
```

Это не самая эффективная сортировка, но она хорошо показывает работу вложенных циклов.

***

### 11.15. Линейный поиск

Линейный поиск — проход по элементам по очереди.

```java
int target = 7;
int index = -1;

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] == target) {
        index = i;
        break;
    }
}
```

Если `index == -1`, элемент не найден.

***

### 11.16. Частотный подсчёт через HashMap: идея на будущее

Если нужно посчитать, сколько раз встречается каждое число, удобно использовать `HashMap`.

```java
HashMap<Integer, Integer> map = new HashMap<>();

for (int number : numbers) {
    if (map.containsKey(number)) {
        map.put(number, map.get(number) + 1);
    } else {
        map.put(number, 1);
    }
}
```

Если `HashMap` ещё не изучен глубоко, можно пока воспринимать его как “таблицу соответствий”:

```
число → сколько раз встретилось
```

***

### 11.17. Алгоритмы в Android

Алгоритмы в Android обычно не видны пользователю напрямую. Пользователь видит кнопку и результат. Но внутри приложение всё равно выполняет алгоритм.

Пример приложения “Статистика оценок”:

* пользователь вводит оценки;
* программа хранит их в списке;
* считает средний балл;
* ищет максимальную оценку;
* показывает результат.

Java-логика та же самая:

```java
sum
average
max
count
filter
```

Меняется только интерфейс.

***

### 11.18. Типичные ошибки новичков

#### Ошибка 1. Начинать максимум с 0

Если числа отрицательные, результат будет неправильный.

***

#### Ошибка 2. Забыть `break` при поиске

Иногда это не ошибка, но если нужно найти первый подходящий элемент, `break` экономит время.

***

#### Ошибка 3. Неправильно менять элементы местами

Плохо:

```java
a = b;
b = a;
```

Оба значения станут одинаковыми.

Правильно:

```java
int temp = a;
a = b;
b = temp;
```

***

#### Ошибка 4. Путаться во вложенных циклах

Во вложенных циклах важно понимать, какой счётчик за что отвечает.

***

### 11.19. Как могут спросить на экзамене

#### Вопрос

Как найти максимальный элемент массива?

#### Хороший ответ

> Нужно взять первый элемент массива как текущий максимум, затем пройти по остальным элементам циклом и сравнивать каждый элемент с максимумом. Если найден элемент больше, обновить максимум.

***

#### Вопрос

Что такое линейный поиск?

#### Хороший ответ

> Линейный поиск — это алгоритм, при котором элементы просматриваются по очереди до тех пор, пока нужный элемент не будет найден или пока список не закончится.

***

#### Вопрос

Зачем нужна временная переменная при обмене значений?

#### Хороший ответ

> Временная переменная нужна, чтобы не потерять одно из значений при обмене. Если сразу присвоить `a = b`, старое значение `a` исчезнет.

***

### 11.20. Практические задания

#### Задание 1

Найдите сумму массива.

***

#### Задание 2

Найдите среднее значение массива.

***

#### Задание 3

Найдите максимальный и минимальный элемент.

***

#### Задание 4

Посчитайте количество чётных чисел.

***

#### Задание 5

Проверьте, есть ли в массиве число, введённое пользователем.

***

#### Задание 6

Разверните массив без создания нового массива.

***

#### Задание 7

Проверьте, является ли строка палиндромом.

***

#### Задание 8

Отсортируйте массив пузырьком.

***

#### Задание 9

Найдите второе по величине число.

***

#### Задание 10

Посчитайте, сколько раз в строке встречается заданный символ.

***

### 11.21. Вопросы для самопроверки

1. Что такое алгоритм в программе?
2. Почему важно уметь писать базовые алгоритмы?
3. Как найти сумму массива?
4. Как найти среднее?
5. Как найти максимум?
6. Как найти минимум?
7. Что такое линейный поиск?
8. Как поменять два значения местами?
9. Что такое палиндром?
10. Как работает пузырьковая сортировка?
11. Зачем нужны вложенные циклы?
12. Где алгоритмы используются в Android?