Найти число сочетаний из N элементов по K - с помощью рекуррентного соотношения

@asdgF333 · Регистрация: 25.10.2020

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

Описать рекурсивную функцию Combin1 (N, K) целого типа, находящую C (N, K) - число сочетаний из N элементов по K - с помощью рекуррентного соотношения: C (N, 0) = C (N, N) = 1, C (N, K) = C (N - 1, K) + C (N - 1, K - 1) при 0 <K <N. Параметры функции - целые числа; N> 0, 0 ≤ K ≤ N. Дано число N и пять различных значений K. Вывести числа C (N, K) вместе с количеством рекурсивных вызовов функции Combin1, необходимых для их нахождения.

Python
1
2
3
4
5
6
7
8
9
10
11
12
def Combin1 (N, K):
    num = 0
    if K == 0 or K == N:
        C = 1
    else:
        C = Combin1(N-1, K)+Combin1(N-1, K-1)
        num += 1
 
if __name__ == '__main__':
    N = int(input("N= "))
    K = int(input("K= "))
    print(Combin1 (N, K))

Здесь вроде всё правильно, но почему-то выбивает ошибку из-за + в функции.

@Welemir1 · 10.04.2021, 12:23

asdgF333, смысл то в чем? функция ничего не возвращает, чего ты там ее принтишь тогда?

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

но почему-то выбивает ошибку из-за + в функции.

и ошибка конечно секретная?

@Arsegg · 10.04.2021, 12:28

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

Здесь вроде всё правильно, но почему-то выбивает ошибку из-за + в функции.

Дай угадаю:

Найти число сочетаний из N элементов по K - с помощью рекуррентного соотношения

RuntimeError: maximum recursion depth exceeded.

@Dax · 10.04.2021, 12:33

Arsegg, Вы не внул -ли той самой Ванги))?

@asdgF333 · 10.04.2021, 12:33 **[ТС]**

Вот такая ошибка
C = Combin1(N-1, K)+Combin1(N-1, K-1)
[Previous line repeated 1 more time]
TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

@Arsegg · 10.04.2021, 12:41

Не по теме:

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

Вы не внул -ли той самой Ванги))?

Тогда уж реинкарнация, т. к. болгар в роду вроде не припомню))

Добавлено через 1 минуту

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

TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

Что будет None + None?

@asdgF333 · 10.04.2021, 12:49 **[ТС]**

None, как это исправить

@Dax · 10.04.2021, 12:50

Не по теме:

Миль пардон за дублирование, только что восстановился доступ к форуму из ошибки 502.

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

None + None?

Предсказываю , что None также вижу, что следует читать о глубине рекрусии в python

@iSmokeJC · 10.04.2021, 12:53

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

None, как это исправить

Очевидно, что-то нужно возвращать из функции.

@Dax · 10.04.2021, 12:56

https://neopythonic.blogspot.c... ation.html

@Arsegg · 10.04.2021, 13:02

Если я правильно понял условие задачи:

Python
1
2
3
4
5
6
7
def Combin1(n, k):
    calls = 0
    def inner(n, k):
        nonlocal calls
        calls += 1
        return 1 if k == 0 or n == k else inner(n - 1, k) + inner(n - 1, k - 1)
    return inner(n, k), calls

@Catstail · 10.04.2021, 15:45

Arsegg, это неэффективный алгоритм. Гораздо лучше использовать рекуррентное соотношение, основанное на треугольнике Паскаля и считать сразу все коэфф. C(n,k) при k от 0 до n

Python
1
2
3
4
5
6
7
8
9
10
11
def comb(n):
    if n==0:
        return [1]
    else:
        tmp=comb(n-1)
        res=[]
        for i in range(1,len(tmp)):
            res.append(tmp[i-1]+tmp[i])
        return [1]+res+[1]
        
print(comb(100))

Результат:

Кликните здесь для просмотра всего текста

[1, 100, 4950, 161700, 3921225, 75287520, 1192052400, 16007560800, 186087894300, 1902231808400, 17310309456440, 141629804643600, 10504210511067
00, 7110542499799200, 44186942677323600, 253338471349988640, 1345860629046814650, 6650134872937201800, 30664510802988208300, 132341572939212267
400, 535983370403809682970, 2041841411062132125600, 7332066885177656269200, 24865270306254660391200, 79776075565900368755100, 24251926972033712
1015504, 699574816500972464467800, 1917353200780443050763600, 4998813702034726525205100, 12410847811948286545336800, 29372339821610944823963760
, 66324638306863423796047200, 143012501349174257560226775, 294692427022540894366527900, 580717429720889409486981450, 10950671531879628864611650
20, 1977204582144932989443770175, 3420029547493938143902737600, 5670048986634686922786117600, 9013924030034630492634340800, 1374623414580281150
1267369720, 20116440213369968050635175200, 28258808871162574166368460400, 38116532895986727945334202400, 49378235797073715747364762200, 6144847
1214136179596720592960, 73470998190814997343905056800, 84413487283064039501507937600, 93206558875049876949581681100, 98913082887808032681188722
800, 100891344545564193334812497256, 98913082887808032681188722800, 93206558875049876949581681100, 84413487283064039501507937600, 7347099819081
4997343905056800, 61448471214136179596720592960, 49378235797073715747364762200, 38116532895986727945334202400, 28258808871162574166368460400, 2
0116440213369968050635175200, 13746234145802811501267369720, 9013924030034630492634340800, 5670048986634686922786117600, 3420029547493938143902
737600, 1977204582144932989443770175, 1095067153187962886461165020, 580717429720889409486981450, 294692427022540894366527900, 14301250134917425
7560226775, 66324638306863423796047200, 29372339821610944823963760, 12410847811948286545336800, 4998813702034726525205100, 19173532007804430507
63600, 699574816500972464467800, 242519269720337121015504, 79776075565900368755100, 24865270306254660391200, 7332066885177656269200, 2041841411
062132125600, 535983370403809682970, 132341572939212267400, 30664510802988208300, 6650134872937201800, 1345860629046814650, 253338471349988640,
44186942677323600, 7110542499799200, 1050421051106700, 141629804643600, 17310309456440, 1902231808400, 186087894300, 16007560800, 1192052400,
75287520, 3921225, 161700, 4950, 100, 1]

@Arsegg · 10.04.2021, 15:48

Catstail, не подскажете, возможно ли здесь применить быстрое возведение в степень матрицы? По аналогии с задачей на вычисление n-го элемента последовательности Фибоначчи?

@Catstail · 10.04.2021, 17:05

Arsegg, надо подумать!

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	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 была полностью переписана на Си, в. . .

@Dax 1356 / 653 / 207 Регистрация: 23.03.2014 Сообщений: 3,057
	10.04.2021, 12:33
	Arsegg, Вы не внул -ли той самой Ванги))? 0

@asdgF333 0 / 0 / 0 Регистрация: 25.10.2020 Сообщений: 168
	10.04.2021, 12:33 [ТС]
	Вот такая ошибка C = Combin1(N-1, K)+Combin1(N-1, K-1) [Previous line repeated 1 more time] TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType' 0

@asdgF333 0 / 0 / 0 Регистрация: 25.10.2020 Сообщений: 168
	10.04.2021, 12:49 [ТС]
	None, как это исправить 0

@Dax 1356 / 653 / 207 Регистрация: 23.03.2014 Сообщений: 3,057
	10.04.2021, 12:56
	https://neopythonic.blogspot.c... ation.html 0

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	10.04.2021, 15:48
	Catstail, не подскажете, возможно ли здесь применить быстрое возведение в степень матрицы? По аналогии с задачей на вычисление n-го элемента последовательности Фибоначчи? 0

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,705 Записей в блоге: 14
	10.04.2021, 17:05
	Arsegg, надо подумать! 0