Циклы на практике: алгоритмы — поиск максимума/минимума, подсчёт элементов, проверка на простоту, Фибоначчи, факториал, разворот числа

Финальный урок модуля — применяем все знания о циклах для решения реальных задач. Разберём классические алгоритмы, которые встречаются в реальных программах и на собеседованиях.

Зачем изучать алгоритмы?

Циклы — это инструмент. А алгоритмы — это рецепты. Зная рецепты, вы сможете решать типичные задачи, не изобретая велосипед каждый раз.

В этом уроке мы разберём 6 классических задач, которые используют циклы. Каждая из них — это строительный блок, из которого складываются более сложные программы.

1. Поиск максимума и минимума

Задача: найти最大的 число в массиве. Идея: запомнить первый элемент как максимум, затем сравнить с каждым следующим. Если текущий элемент больше — обновляем максимум.

int[] numbers = {23, 7, 89, 12, 56, 34, 11, 67};

int max = numbers[0];
int min = numbers[0];

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

System.out.println("Максимум: " + max);
System.out.println("Минимум: " + min);

Вывод:

Максимум: 89
Минимум: 7

Почему мы начинаем с numbers[0], а не, например, с 0? Потому что 0 может быть больше всех элементов (если все отрицательные), или меньше (если массив начинается с большого числа). Первый элемент — safest choice.

2. Подсчёт элементов по условию

Задача: посчитать количество чётных чисел в массиве. Используем счётчик и оператор %:

int[] numbers = {12, 7, 23, 8, 45, 16, 31, 42};
int evenCount = 0;

for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] % 2 == 0) {
        evenCount++;
    }
}

System.out.println("Количество чётных: " + evenCount);

Вывод:

Количество чётных: 4

Можно посчитать и другие условия: положительные, отрицательные, делящиеся на 3, больше 100 и т.д.

3. Проверка числа на простоту

Задача: определить, является ли число простым. Простое число — это число, которое делится только на 1 и на себя.

int number = 29;
boolean isPrime = true;

if (number <= 1) {
    isPrime = false;
} else {
    for (int i = 2; i * i <= number; i++) {
        if (number % i == 0) {
            isPrime = false;
            break;
        }
    }
}

if (isPrime) {
    System.out.println(number + " — простое число");
} else {
    System.out.println(number + " — составное число");
}

Вывод:

29 — простое число

Ключевые моменты:

• Числа 0 и 1 — не простые по определению
• Нам не нужно проверять делители больше корня из числа. Если i * i > number, значит, мы уже проверили все возможные делители
• break останавливает поиск сразу, как только найден делитель

4. Числа Фибоначчи

Последовательность Фибоначчи: каждое число — сумма двух предыдущих. Начало: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

int n = 15;
int a = 0;
int b = 1;

System.out.println("Первые " + n + " чисел Фибоначчи:");

for (int i = 1; i <= n; i++) {
    System.out.print(a + " ");
    int temp = a + b;
    a = b;
    b = temp;
}

System.out.println();

Вывод:

Первые 15 чисел Фибоначчи:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Как это работает:

• a — текущее число, b — следующее
• Печатаем a, затем сдвигаем: a = b, b = a + b
• Используем временную переменную temp, чтобы не потерять значение

5. Факториал

Факториал числа n (n!) = 1 × 2 × 3 × ... × n. Мы уже делали это в уроке 1, но давайте обобщим:

int n = 10;
long factorial = 1;

for (int i = 2; i <= n; i++) {
    factorial *= i;
}

System.out.println(n + "! = " + factorial);

Вывод:

10! = 3628800

Мы начинаем с 2, потому что 0! = 1! = 1, и умножение на 1 не меняет результат.

6. Разворот числа

Задача: перевернуть число (12345 → 54321). Идея: последовательно извлекаем последнюю цифру и добавляем к результату:

int number = 12345;
int reversed = 0;

while (number > 0) {
    int digit = number % 10;
    reversed = reversed * 10 + digit;
    number /= 10;
}

System.out.println("Развёрнутое число: " + reversed);

Вывод:

Развёрнутое число: 54321

Пошагово:

1. number = 12345, digit = 5, reversed = 5
2. number = 1234, digit = 4, reversed = 54
3. number = 123, digit = 3, reversed = 543
4. number = 12, digit = 2, reversed = 5432
5. number = 1, digit = 1, reversed = 54321
6. number = 0 → цикл завершается

7. Палиндром

Палиндром — число или слово, которое читается одинаково в обе стороны (121, 1331, «мадам»):

int number = 12321;
int original = number;
int reversed = 0;

while (number > 0) {
    reversed = reversed * 10 + number % 10;
    number /= 10;
}

if (original == reversed) {
    System.out.println(original + " — палиндром");
} else {
    System.out.println(original + " — не палиндром");
}

Вывод:

12321 — палиндром

8. НОД (Наибольший общий делитель)

Алгоритм Эвклиста — классический способ найти НОД двух чисел:

int a = 48;
int b = 18;

while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
}

System.out.println("НОД = " + a);

Вывод:

НОД = 6

Алгоритм: на каждом шаге заменяем (a, b) на (b, a % b), пока b не станет 0. Тогда a — это НОД.

9. Сумма цифр числа

int number = 9876;
int sum = 0;
int temp = number;

while (temp > 0) {
    sum += temp % 10;
    temp /= 10;
}

System.out.println("Сумма цифр числа " + number + " = " + sum);

Вывод:

Сумма цифр числа 9876 = 30

10. Количество цифр

int number = 1234567;
int count = 0;
int temp = number;

while (temp > 0) {
    count++;
    temp /= 10;
}

System.out.println("В числе " + number + " " + count + " цифр(а).");

Вывод:

В числе 1234567 7 цифр(а).

11. Проверка на совершенное число

Совершенное число — это число, которое равно сумме всех своих делителей (кроме самого себя). Например, 6 = 1 + 2 + 3.

int number = 28;
int sum = 0;

for (int i = 1; i < number; i++) {
    if (number % i == 0) {
        sum += i;
    }
}

if (sum == number) {
    System.out.println(number + " — совершенное число");
} else {
    System.out.println(number + " — несовершенное число");
}

Вывод:

28 — совершенное число

12. Генерация всех комбинаций

Выведем все пары (i, j), где i от 1 до 3, j от 1 до 4:

for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 4; j++) {
        System.out.println("(" + i + ", " + j + ")");
    }
}

Вывод:

(1, 1)
(1, 2)
(1, 3)
(1, 4)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 1)
(3, 2)
(3, 3)
(3, 4)

13. Поиск простых чисел до N (Решето Эратосфена)

Эффективный алгоритм поиска всех простых чисел до N:

int limit = 30;
boolean[] isPrime = new boolean[limit + 1];

for (int i = 2; i <= limit; i++) {
    isPrime[i] = true;
}

for (int i = 2; i * i <= limit; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= limit; j += i) {
            isPrime[j] = false;
        }
    }
}

System.out.println("Простые числа до " + limit + ":");
for (int i = 2; i <= limit; i++) {
    if (isPrime[i]) {
        System.out.print(i + " ");
    }
}
System.out.println();

Вывод:

Простые числа до 30:
2 3 5 7 11 13 17 19 23 29

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

14. Объединение алгоритмов

Давайте объединим несколько алгоритмов в одну программу — найти простые числа в массиве и посчитать их сумму:

int[] numbers = {2, 7, 12, 13, 17, 20, 23, 29};
int primeSum = 0;

for (int i = 0; i < numbers.length; i++) {
    int num = numbers[i];
    boolean isPrime = true;

    if (num <= 1) {
        isPrime = false;
    } else {
        for (int j = 2; j * j <= num; j++) {
            if (num % j == 0) {
                isPrime = false;
                break;
            }
        }
    }

    if (isPrime) {
        primeSum += num;
    }
}

System.out.println("Сумма простых чисел: " + primeSum);

Вывод:

Сумма простых чисел: 88

Здесь используется тройная вложенность: for (перебор массива) → if (проверка на простоту) → for (перебор делителей).

Совет: когда решаете задачу с циклами, начните с маленького примера (3-5 элементов), пройдите по шагам, убедитесь, что работает, а потом протестируйте на больших данных.

Итоги урока

• Циклы — основа алгоритмического мышления
• Поиск максимума/минимума: запоминаем первый элемент, сравниваем с остальными
• Подсчёт по условию: счётчик + if
• Простота числа: проверяем делители до корня из числа
• Фибоначчи: два предыдущих элемента + временная переменная
• Факториал: произведение всех чисел от 1 до N
• Разворот числа: извлекаем цифры через % 10 и / 10
• Комбинируйте алгоритмы для решения более сложных задач

15. Проверка наAGIC

Армстронга (нарциссическое) число — это число, которое равно сумме своих цифр, каждая возведённая в степень количества цифр. Например, 153 = 1³ + 5³ + 3³ = 1 + 125 + 27 = 153.

int number = 153;
int original = number;
int sum = 0;
int digits = 0;

int temp = number;
while (temp > 0) {
    digits++;
    temp /= 10;
}

temp = number;
while (temp > 0) {
    int digit = temp % 10;
    int power = 1;
    for (int i = 0; i < digits; i++) {
        power *= digit;
    }
    sum += power;
    temp /= 10;
}

if (sum == original) {
    System.out.println(original + " — число Армстронга");
} else {
    System.out.println(original + " — не число Армстронга");
}

Вывод:

153 — число Армстронга

16. Нахождение НОК (Наименьшее общее кратное)

int a = 12;
int b = 18;

int tempA = a;
int tempB = b;

while (tempB != 0) {
    int temp = tempB;
    tempB = tempA % tempB;
    tempA = temp;
}

int nod = tempA;
int nok = (a * b) / nod;

System.out.println("НОД(" + a + ", " + b + ") = " + nod);
System.out.println("НОК(" + a + ", " + b + ") = " + nok);

Вывод:

НОД(12, 18) = 6
НОК(12, 18) = 36

17. Конвертация систем счисления

Переведём число из десятичной системы в двоичную:

int number = 42;
String binary = "";
int temp = number;

while (temp > 0) {
    binary = (temp % 2) + binary;
    temp /= 2;
}

System.out.println(number + " в двоичной = " + binary);

Вывод:

42 в двоичной = 101010

18. Поиск индекса в отсортированном массиве

int[] sorted = {2, 5, 8, 12, 16, 23, 38, 45, 67, 91};
int target = 23;
int left = 0;
int right = sorted.length - 1;
int result = -1;

while (left <= right) {
    int mid = (left + right) / 2;

    if (sorted[mid] == target) {
        result = mid;
        break;
    } else if (sorted[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

System.out.println("Индекс " + target + ": " + result);

Вывод:

Индекс 23: 5

19. Генерация всех троек

for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 3; j++) {
        for (int k = 1; k <= 3; k++) {
            System.out.println("(" + i + ", " + j + ", " + k + ")");
        }
    }
}

Вывод (первые 10 строк):

(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 1)
(1, 2, 2)
(1, 2, 3)
(1, 3, 1)
(1, 3, 2)
(1, 3, 3)
(2, 1, 1)

20. Поиск двух чисел с заданной суммой

int[] numbers = {2, 7, 11, 15, 1, 8, 6};
int targetSum = 9;

boolean found = false;
for (int i = 0; i < numbers.length; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
        if (numbers[i] + numbers[j] == targetSum) {
            System.out.println(numbers[i] + " + " + numbers[j] + " = " + targetSum);
            found = true;
        }
    }
}

if (!found) {
    System.out.println("Пара не найдена");
}

Вывод:

2 + 7 = 9
8 + 1 = 9

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

Итоги урока

• Циклы — основа алгоритмического мышления
• Поиск максимума/минимума: запоминаем первый элемент, сравниваем с остальными
• Подсчёт по условию: счётчик + if
• Простота числа: проверяем делители до корня из числа
• Фибоначчи: два предыдущих элемента + временная переменная
• Факториал: произведение всех чисел от 1 до N
• Разворот числа: извлекаем цифры через % 10 и / 10
• Комбинируйте алгоритмы для решения более сложных задач
• Понимание сложности O(n) и O(n²) важно для выбора эффективного алгоритма

Поздравляем!

Вы завершили модуль «Циклы»! Теперь вы умеете:

• Использовать циклы while, do-while, for
• Управлять потоком выполнения с помощью break и continue
• Работать с вложенными циклами
• Решать классические алгоритмические задачи
• Понимать разницу между O(n), O(n²) и O(n³)
• Применять циклы для обработки массивов, строк и матриц

В следующем модуле мы изучим массивы и строки — структуры данных, с которыми циклы работают особенно часто.