Алгоритмы на Kotlin — часть 1

kotlin алгоритмы

Привет. Сегодня будет небольшой пост про алгоритмы Kotlin, а конкретно мы рассмотрим простые задачки, которые встречаются на собеседовании на разработчика Kotlin (или на разраба любого другого языка).

Факториал Kotlin sequence

Последовательности в Kotlin — классная штука. Не знаю, есть ли они в Java, но ежели их там нет (или аналогов), то определенно стоит добавить. Детально на них я останавливаться не буду, подробнее про это можно узнать в официальной документации.

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

val factorial = sequence {

    var fn = 1
    var res: BigInteger = BigInteger.ONE

    while (true) {
        yield(res) // 3
        fn++ // 1
        res = res.multiply(fn.toBigInteger()) // 2
    }
}

Объявляем переменную factorial и присваиваем ей билдер sequence. Эта лямбда возвращает последовательность. У нас есть переменная-счетчик fn, и переменная, возвращающая результат — res. В бесконечном цикле while(true) мы увеличиваем на единицу число (1) и вычисляем результат с помощью умножения (2). Не забываем простой Int привести к Biginteger.

Тип BigInteger выбран не зря, потому что после значения примерно в 13! — 14! начинаются ошибки, диапазона обычного Int просто не хватает. BigInteger.ONE — константа в классе BigInteger и равна единице.

Генератор yield(res) выдает нам наш результат и приостанавливает работу (3), то есть цикл не работает постоянно.

fun main() {
    println(factorial.take(10).toList())
}

// [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

Чтобы получить результат 10! можно у нашей переменной типа Sequence вызвать метод take(n), где n — количество итераций работы yield. Если хотите получить только 1 число, то можно сделать так — factorial.take(10).toList().last()

Конечно, можно получить результат с помощью простого цикла или рекурсии, как сделано в этой статье. Однако, факториал на Kotlin с помощью sequence мне кажется более легким и элегантным способом.

Числа Фибоначчи — Sequence

Задачка, которую спрашивают довольно часто. Итак, как говорит Википедия, числа Фибоначчи — это элементы числовой последовательности, в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. По факту, мы имеем формулу Fn = (Fn — 1) + (Fn — 2), где F0 = 0, F1 = 1

Давайте снова возьмем sequence и генератор yield.

val fib = sequence {

    val fb = mutableListOf<Int>()
    var i = 2
    fb.add(0) // 1
    fb.add(1) // 1

    while (true) {
        fb.add(fb[i-1] + fb[i-2]) // 2
        yield(fb[i-2]) // 3
        i++
    }

}

Создадим переменную fib с типом mutableList, которая будет возвращать нашу последовательность с числами. Первые два числа нам известны — это 0 и 1, поэтому добавим их сразу (1). Затем, в бесконечном цикле будем вычислять каждое число (2) и возвращать его в последовательность.

fun main() {
    println(fib.take(10).toList())
    println(fibonacci.take(10).toList())
}

// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Все работает отлично. Как и в примере выше, чтобы получить одно число, можно вызвать метод last() у списка. Но не только с помощью списков можно вычислить числа Фибоначчи. Для упрощения получения результата и сокращения количества кода можно взять Pair.

val fibonacci = sequence {
    var start = Pair(0,1)

    while (true) {
        yield(start.first)
        start = Pair(start.second, start.first + start.second)
    }
}

Результат будет аналогичным, а кода станет меньше. В принципе, можно решить эту задачку через цикл, или рекурсию (потребление памяти будет выше).

Минимальный элемент в массиве

Достаточно простая задачка на поиск минимального элемента в массиве, которую нам давали еще на первом курсе. Язык был Delphi, толи 6, толи 7 версия — точно не вспомню. Данный пример мы решим с помощью Котлин.

fun minArr(array: ArrayList<Int>): Int {
    var result = array[0] // 1

    for (n in 1 until array.size) {
        if (result > array[n]) { // 2
            result = array[n]
        }
    }
    return result
}

Алгоритм простой. Мы берем первый элемент в массиве и записываем его в переменную result (1). Затем, сравниваем его с остальными поочередно. Далее проходимся циклом по массиву. Если result больше элемента массива, то берем его и записываем в result (2).

fun main() {
    val arr = arrayListOf(43, 2, 1, 98, 123, 31, 11, 27, 0, 16)
    println(minArr(arr))
}
// 0

На выходе получаем наш результат. Можно конечно не мудрить ничего с циклом и просто вызвать метод minOrNull() у списка, но тогда смысл задания теряется.

Поиск простых чисел

Теперь на очереди достаточно распространенная задачка на собеседовании — поиск простых чисел. Википедия на говорит, что простое число — это натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя.

fun isPrime(n: Int): Boolean {
    var s = true
    loop@ for(number in 2 until n) { // 1
        if (n % number == 0) { // 2
            s = false
            break@loop
        }
    }
    return s
}

Алгоритм решения таков. Мы берем последовательность чисел (1) и проверяем делители каждого (2) от 2 до n-1. В итоге, наша функция isPrime() вернет true если число простое и false — если нет. Теперь с помощью filter() мы можем получить последовательность простых чисел.

В цикле есть небольшая оптимизация — метка @loop. Если наше проверяемое число делится без остатка на другое (2), которое больше 1 и меньше самого числа, то обход значений в цикле приостанавливается с помощью break@loop, ибо считать далее смысла нет.

fun main() {
    val primeNumbers = (1..100).filter { isPrime(it) }
    println(primeNumbers)
}
// [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

P.S.

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

Всем пока, и удачи в освоении Kotlin.

Оставить ответ