Question

Задача на python срочно! Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей. Ограничения: 2 <= K <= 10, N + K <= 18. Формат входных данных Числа N и K в десятичной записи, разделенные пробелом или переводом строки. Формат выходных данных Искомое число в десятичной записи.

Answer 1

n, k = map(int, input().split())

x, y = 1, 0

for i in range(n):

   x, y = (k-1) * (x + y), x

print(x)

Answer 2

Давайте решим данную задачу. Мы можем использовать динамическое программирование для нахождения количества N-значных чисел в системе счисления с основанием K, удовлетворяющих условию.

pythonCopy code
def count_numbers(N, K):
    if N == 1:
        return K
    
    ending_in_zero = [0] * (N + 1)
    not_ending_in_zero = [0] * (N + 1)
    
    ending_in_zero[1] = not_ending_in_zero[1] = K - 1
    
    for i in range(2, N + 1):
        ending_in_zero[i] = not_ending_in_zero[i - 1]
        not_ending_in_zero[i] = (K - 1) * (ending_in_zero[i - 1] + not_ending_in_zero[i - 1])
    
    return ending_in_zero[N] + not_ending_in_zero[N]

# Чтение входных данных
N, K = map(int, input().split())

# Вызов функции и вывод результата
result = count_numbers(N, K)
print(result)

Вызов функции count_numbers(N, K) вычислит количество N-значных чисел в системе счисления с основанием K, удовлетворяющих заданному условию, и вернет это число. Важно, чтобы N + K <= 18, как указано в ограничениях.

Просто введите числа N и K через пробел или перевод строки, и скрипт выведет количество искомых чисел в десятичной записи.