Разбор задач виртуального собеседования
t.me/main_ds_kz/889
flexiquiz.com/SC/N/c247d732-bc8e-42ca-a9f1-8df8d6ea264c
Часть IV. Код
Реккурентная последовательность (1 балл)
Пусть последовательность задана следующим образом:
a[1] = 1
a[2] = 7
a[k] = a[k-1] + a[k-2], k > 2
Найдите сумму цифр 2019го члена данной последовательности
(Забавный факт: сумма цифр 2019 числа Фиббоначи равна 2018)
Code Snippet
def fibbonaci(n_iter: int, prev: int = 1, current: int = 1) -> int:
if n_iter == 1:
return prev
if n_iter == 2:
return current
for _ in range(n_iter - 2):
prev, current = current, prev + current
return current
fib = fibbonaci(2019, 1, 7)
sum_digits = sum(map(int, str(fib)))
print(sum_digits)
190710
Проверить забавный факт
fib = fibbonaci(2019, 1, 1)
sum_digits = sum(map(int, str(fib)))
print(sum_digits)
2018
Простые числа (3 балла)
Посчитайте число простых чисел, меньших чем число 201920190, в записи которых нет цифры 7
Решение
По сути просто гуглим алгоритм решета Эрастофена и немного адоптируем под нашу задачу
Например:
geeksforgeeks.org/python-program-for-sieve-of-eratosthenes/
Интуиция алгоритма: перебирать простые числа и сразу вычеркивать все кратные ему из списка претендентов. Каждую следующую итерацию начинать с наименьшего из претендентов.
Code snippet
def find_prime_numbers(num):
prime = [True for i in range(num+1)]
p = 2
while (p * p <= num):
if (prime[p] == True):
for i in range(p * p, num+1, p):
prime[i] = False
p += 1
prime_numbers = [i for i in range(2, num+1) if prime[i] and '7' not in str(i)]
return prime_numbers
prime_numbers = find_prime_numbers(201920190)
len(prime_numbers)
4033301
На этом разбор первого раунда виртуального собеседования подходит к конце, ставьте огоньки, репостите задачки тем, кто проходит собесы и ждите следующего раунда ;)
