3. Основы Kotlin. Рекурсии и циклы

Последовательная проверка условий

Рассмотрим теперь несколько более сложный пример. Пусть нам требуется написать функцию, проверяющую натуральное число на простоту. Напомним, что число называется простым (prime), если оно делится нацело только на единицу и на себя, и составным, если у него есть и другие делители (единица обычно не считается ни простым, ни составным числом).

Прямолинейная проверка предполагает деление заданного числа n последовательно на числа в интервале от 2 до n-1. Чтобы проверить, делится ли число n нацело на другое число m, достаточно сравнить остаток от деления n % m с нулём. Если хотя бы раз мы успешно поделили нацело — исходное число n не является простым.

fun isPrime(n: Int): Boolean {
    if (n < 2) return false // Необходимо, так как 1 -- не простое число
    for (m in 2..n - 1) {
        if (n % m == 0) return false
    }
    return true
}

Обратите внимание, что, найдя делитель, мы сразу сообщаем о том, что результат — false — при этом прерывается как выполнение цикла, так и выполнение функции, поскольку результат уже определён. Чтобы доказать, что число является составным, нам достаточно найти хотя бы ОДИН делитель от 2 до n-1. Однако о результате true мы можем сообщить только после окончания цикла, проверив ВСЕ делители: чтобы доказать простоту числа, надо убедиться, что НИ ОДНО число от 2 до n-1 не является делителем. Начинающие часто делают вот такую ошибку:

    for (m in 2..n - 1) {
        if (n % m == 0) return false
        else return true
    }

что, конечно, неверно. Такой цикл будет выполнен только один раз, результат будет true для нечётных и false для чётных чисел.

В тестовой функции мы можем проверить, что числа 2, 5 и 11 являются простыми, а числа 1, 4, 9 и 15 — составными. Мы можем также написать более сложную проверку, использовав тот факт, что первые 1000 простых чисел лежат в интервале от 2 до 7919 — см. https://en.wikipedia.org/wiki/List_of_prime_numbers.

    @Test
    fun isPrime() {
        var count = 0
        for (n in 2..7919) {
            if (isPrime(n)) {
                count++
            }
        }
        assertEquals(1000, count)
    }

Мы в цикле проверяем числа от 2 до 7919 на простоту. Каждый раз, когда число оказывается простым, мы выполняем оператор count++ — сокращённая форма записи count = count + 1 или count += 1, так называемый оператор инкремента (существует также оператор --, или оператор декремента).

Попробуем теперь с помощью isPrime узнать, сколько существует простых чисел, меньших десяти миллионов (для этого достаточно заменить в приведённом участке кода 7919 на 10000000). Если запустить такую функцию на выполнение, оно займёт довольно много времени. Всё дело в том, что наша функция isPrime(n: Int) выполняет лишние проверки. В частности, достаточно проверить делимость числа n на все числа в интервале от 2 до n/2, так как на большие числа n всё равно делится не будет. Более того, достаточно ограничится интервалом от 2 до √n — если n и делится на какое-то большее √n число (например, 50 делится на 10), то оно будет делится и на какое-то меньшее число (в данном случае, 50 делится на 5=50/10).

fun isPrime(n: Int): Boolean {
    if (n < 2) return false // Необходимо, так как 1 -- не простое число
    for (m in 2..sqrt(n.toDouble()).toInt()) {
        if (n % m == 0) return false
    }
    return true
}

Обратите внимание, что перед вычислением квадратного корня мы были вынуждены воспользоваться функцией n.toDouble() для получения вещественного числа из целого, а после вычисления — функцией .toInt() для получения целого числа из вещественного. Обе эти встроенные в Котлин функции имеют необычную для начинающих форму записи, которая читается как “n преобразовать к Double”, “…​ преобразовать к Int”. Вместо того, чтобы записать аргумент внутри круглых скобок toDouble(n), мы записываем его перед именем функции, отделяя его от имени символом точки. Подобный аргумент функции называется её получателем (receiver), в будущем мы ещё неоднократно столкнёмся с подобной формой записи.

Прерывание и продолжение цикла

При программировании циклов часто встречаются ситуации, когда необходимо прервать выполнение цикла досрочно, или же досрочно перейти к началу его следующей итерации. Для этой цели в Котлине используются операторы break и continue.

Продемонстрируем их на примере. Совершенным числом называется такое натуральное число, которое равно сумме всех своих делителей, кроме себя самого. В частности, 6 = 1 + 2 + 3 и 28 = 1 + 2 + 4 + 7 + 14 — совершенные числа. Напишем функцию, определяющую, является ли заданное число n совершенным.

fun isPerfect(n: Int): Boolean {
    var sum = 1
    for (m in 2..n/2) {
        if (n % m == 0) {
            sum += m
            if (sum > n) break
        }
    }
    return sum == n
}

Данная функция перебирает все возможные делители числа n от 2 до n/2 (единицу перебирать бессмысленно, поскольку на неё делится любое число — поэтому мутирующая переменная sum изначально равна 1, а не 0). Каждый найденный делитель прибавляется к сумме. Если в какой-то момент набранная сумма оказалась больше n — цикл можно прервать с помощью break, так как последующие делители могут только увеличить её ещё больше. После прерывания цикла выполняется следующий за ним оператор, в данном случае return.

Другой вариант записи той же самой функции использует оператор продолжения continue:

fun isPerfect(n: Int): Boolean {
    var sum = 1
    for (m in 2..n/2) {
        if (n % m > 0) continue
        sum += m
        if (sum > n) break
    }
    return sum == n
}

Здесь вместо того, чтобы проверить, что n делится на m, мы проверяем обратное условие — что n НЕ ДЕЛИТСЯ на m. Если оно верно, выполняется оператор continue, при этом остаток данной итерации цикла пропускается, происходит увеличение значения m на 1 и переход к следующей итерации. Обе реализации isPerfect равнозначны, применение той или другой из них — дело вкуса.