Напишите рекурсивную функцию, которая вычисляет число сочетаний из N по K (биномиальный коэффициент C(n, k), который вы

@zidaneskills · Регистрация: 22.09.2022

Студворк — интернет-сервис помощи студентам

Напишите рекурсивную функцию, которая вычисляет число сочетаний из N по K (биномиальный коэффициент C(n, k)), который вычисляется по формулам:
C(0, n) = 1
C(n, n) = 1
C(k, n) = C(k, n-1) + C(k-1, n-1)

Используйте словарь для кэширования вычисленных значений. Это позволит исключить повторное вычисление значений.

Вашей программе подается сначала число K а затем через пробел число N.

Sample Input:

2 6
Sample Output:

15

ПОМОГИТЕ РЕШИТЬ? PYTHON

@Alexarh · 22.09.2022, 16:34

Python
1
2
3
4
5
6
7
8
def f(k, n):
    if k == 0 or k == n:
        return 1
    return f(k, n - 1) + f(k - 1, n - 1)
 
 
x, y = map(int, input().split())
print(f(x, y))

@dondublon · 22.09.2022, 16:41

Сообщение от Alexarh

return f(k, n - 1) + f(k - 1, n - 1)

Без кеша же. Сдохнет быстро.

@Alexarh · 22.09.2022, 16:49

Или так, если со словарем, но я не уверен, может кто опытнее подскажет, чтобы я сам знал )

Python
1
2
3
4
5
6
7
8
9
10
11
12
def f(k, n):
    if k == 0 or k == n:
        return 1
    d[(k, n - 1)] = d.get((k, n - 1), f(k, n - 1))
    d[(k - 1, n - 1)] = d.get((k - 1, n - 1), f(k - 1, n - 1))
 
    return d[(k, n - 1)] + d[(k - 1, n - 1)]
 
 
d = {}
x, y = map(int, input().split())
print(f(x, y))

Добавлено через 6 минут
Тут ерунда какая-то похоже )

@dondublon · 22.09.2022, 17:06

Ээээ... Тут явно должен быть if

на то, что вытащили из кеша.
И да, ключ - без f в своём составе.

@Alexarh · 22.09.2022, 17:23

dondublon,
если правильно понял замечание, то тут dict.get() заменяет это. Если по ключу ничего нет в словаре, то вставляем это значение туда, которое get() вернула по умолчанию, а это вычисление функции.

@Catstail · 22.09.2022, 17:32

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def comb(n,k,d={}):
    if (n == k) or (k == 0):
        return 1
    if d.get((n,k)) is None:
        tmp=comb(n-1,k,d)+comb(n-1,k-1,d)
        d[(n,k)]=tmp
        return tmp
    else:
        return d[(n,k)]
 
n=int(input("n="))
k=int(input("k="))
 
print(comb(n,k))

@eaa · 22.09.2022, 17:41

Python
1
from functools import cache

@Alexarh · 22.09.2022, 19:18

Catstail, что-то не работает, даже на данных из первого поста.

@Catstail · 22.09.2022, 19:31

Alexarh, Пробуйте

Добавлено через 2 минуты
Alexarh, у ТС все вывернуто (n и к перепутаны). вводите n=6 k=2 Ответ 15

@Alexarh · 22.09.2022, 19:33

Не по теме:

Catstail, тогда работает.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@zidaneskills 0 / 0 / 0 Регистрация: 22.09.2022 Сообщений: 5

	Напишите рекурсивную функцию, которая вычисляет число сочетаний из N по K (биномиальный коэффициент C(n, k), который вы 22.09.2022, 16:19. Показов 1582. Ответов 10 Метки python (Все метки) Напишите рекурсивную функцию, которая вычисляет число сочетаний из N по K (биномиальный коэффициент C(n, k)), который вычисляется по формулам: C(0, n) = 1 C(n, n) = 1 C(k, n) = C(k, n-1) + C(k-1, n-1) Используйте словарь для кэширования вычисленных значений. Это позволит исключить повторное вычисление значений. Вашей программе подается сначала число K а затем через пробел число N. Sample Input: 2 6 Sample Output: 15 ПОМОГИТЕ РЕШИТЬ? PYTHON 0

@dondublon 4652 / 2072 / 366 Регистрация: 17.03.2012 Сообщений: 10,182 Записей в блоге: 6
	22.09.2022, 17:06
	Ээээ... Тут явно должен быть if на то, что вытащили из кеша. И да, ключ - без f в своём составе. 0

@Alexarh 2431 / 1474 / 633 Регистрация: 01.11.2021 Сообщений: 2,269
	22.09.2022, 17:23
	dondublon, если правильно понял замечание, то тут dict.get() заменяет это. Если по ключу ничего нет в словаре, то вставляем это значение туда, которое get() вернула по умолчанию, а это вычисление функции. 0

@Alexarh 2431 / 1474 / 633 Регистрация: 01.11.2021 Сообщений: 2,269
	22.09.2022, 19:18
	Catstail, что-то не работает, даже на данных из первого поста. 0

@Catstail Супер-модератор 38171 / 21106 / 4307 Регистрация: 12.02.2012 Сообщений: 34,699 Записей в блоге: 14
	22.09.2022, 19:31
	Alexarh, Пробуйте Добавлено через 2 минуты Alexarh, у ТС все вывернуто (n и к перепутаны). вводите n=6 k=2 Ответ 15 1

@Alexarh
	22.09.2022, 19:33
	Не по теме: Catstail, тогда работает. 0

Напишите рекурсивную функцию, которая вычисляет число сочетаний из N по K (биномиальный коэффициент C(n, k), который вы

Решение