Посчитать количество маршрутов

@Arina26 · Регистрация: 06.12.2017

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

Лестница имеет определенное количество ступенек N. Кенгуру может одним
прыжком преодолеть не более К ступенек. Кенгуру пытается каждый раз найти
новый путь к вершине лестницы. Сколько различных способов есть у кенгуру
добраться до вершины лестницы при заданных значениях K и N. Например, если
K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1,
2+2, 1+3, 3+1. Программа должна выводить в файл количество способов добраться
и сами способы.

@IRIP · 07.10.2018, 21:02

Arina26, полная лекция (сначала ее изучите)

@Arina26 · 08.10.2018, 09:14 **[ТС]**

Не открывается видео

@IRIP · 08.10.2018, 14:31

Arina26, https://youtu.be/EdhN_gEDfUM вот, тогда, по ссылке...

Добавлено через 1 минуту
Вам ответ можно здесь написать, но лучше, когда вы основы поймете, а потом уже ответить на вопросы

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

vic5710 · 09.10.2018, 04:10

Arina26, задача скорее на комбинаторику. примерно так

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import itertools
from math import ceil
 
N = 5
K = 3
n_min = ceil(N/K)
out = []
for i in range(n_min,N + 1): 
    c = itertools.combinations_with_replacement(range(1,K + 1),i)
    for item in c:
        if sum(item) == N :
            p = itertools.permutations(item,i)
            for j in p:
                if not j in out: out.append(j)
print(len(out),out)

Добавлено через 6 часов 0 минут
более быстрый вариант

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
from itertools import combinations_with_replacement as combi, permutations
 
N = 5
K = 5
out = set()
for i in range(N//K, N):
    for j in combi(range(1,K+1), i): 
        if sum(j) == N:
            for k in permutations(j): 
                out.add(k)
 
out.add(tuple([1]*N))
print(len(out),sorted(out))

@Arina26 · 09.10.2018, 20:00 **[ТС]**

Большое спасибо за помощь!

Новые блоги и статьи Все статьи Все блоги /
1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .

@Arina26 0 / 0 / 0 Регистрация: 06.12.2017 Сообщений: 24

	Посчитать количество маршрутов 07.10.2018, 18:20. Показов 2881. Ответов 5 Метки нет (Все метки) Лестница имеет определенное количество ступенек N. Кенгуру может одним прыжком преодолеть не более К ступенек. Кенгуру пытается каждый раз найти новый путь к вершине лестницы. Сколько различных способов есть у кенгуру добраться до вершины лестницы при заданных значениях K и N. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Программа должна выводить в файл количество способов добраться и сами способы. 0

@IRIP 514 / 146 / 28 Регистрация: 18.04.2015 Сообщений: 1,904 Записей в блоге: 16
	07.10.2018, 21:02
	Arina26, полная лекция (сначала ее изучите) 0

@Arina26 0 / 0 / 0 Регистрация: 06.12.2017 Сообщений: 24
	08.10.2018, 09:14 [ТС]
	Не открывается видео 0

@IRIP 514 / 146 / 28 Регистрация: 18.04.2015 Сообщений: 1,904 Записей в блоге: 16
	08.10.2018, 14:31
	Arina26, https://youtu.be/EdhN_gEDfUM вот, тогда, по ссылке... Добавлено через 1 минуту Вам ответ можно здесь написать, но лучше, когда вы основы поймете, а потом уже ответить на вопросы Ваш вопрос относится к вычислению, которое лучше сделать через рекурсию (это не сложно) и начинать нужно с определения последнего прыжка... 0

@Arina26 0 / 0 / 0 Регистрация: 06.12.2017 Сообщений: 24
	09.10.2018, 20:00 [ТС]
	Большое спасибо за помощь! 0

Посчитать количество маршрутов

Решение