Авто
Рейтинг основных форумов
Городские форумы
Городской форум
Городской форум для новичков
Нижегородская политика
Жалобная книга
Бабский форум
Мужской
Анонимный медицинский форум
Дурацкие вопросы
Автофорумы
Автофорум главный
Девушка за рулем
ВАЗ форум
4х4 форум
Жалобный
Шевроле Форум
Такси
Автозапчасти
Гаражный форум
KIA-форум
Рено форум
Hyundai Форум
VAG Форум
Форумы покупок
Центр раздач: информационный форум
Глав-Пристрой (со всех форумов, взрослый)
Совместная покупка
Совместная покупка: центральный
Совместная покупка: взрослый
Совместная покупка: вкусный
Совместная покупка: мама и малыш
Совместная покупка: уютный
Совместная покупка: сбор предоплаты, раздачи
Совместная покупка: услуги
Совместная покупка: область
Совместная покупка: Дзержинск
Совместная покупка: Саров
Зарубежные интернет-покупки
Покупаем вместе
Покупаем Вместе: Основной
Покупаем вместе: БОЛЬШОЙ ШОПИНГ (взрослый)
Покупаем вместе: БЕБИ-ШОП (детский)
Покупаем вместе: ДОМОВОЙ
Покупаем вместе: ГАСТРОНОМ
Покупаем вместе: Сбор предоплаты, раздачи
Покупаем Вместе: пристрой
Покупаем Вместе: услуги
Выгодная покупка
Выгодная покупка - общие вопросы
Выгодная покупка - взрослый
Выгодная покупка - детский
Выгодная покупка - сбор предоплаты, раздачи
Выгодная покупка - объявления
Форум закупок
Мой малыш
Мой малыш - Основной
Мой малыш - Объявления. Общий
Мой малыш - Объявления: детская одежда
Мой малыш - Объявления: детская обувь
Мой малыш - Объявления: детский транспорт, игрушки, мебель
Халявный
Халявный (основной)
Котята и др. животные
Элитный (продажа неликвидных товаров)
Услуги
Домоводство
Полезный форум
Бытовые проблемы
Деревенский форум
Домоводство
Цветочный форум
Форум владельцев кошек
Дачный. Основной.
Бытовая Техника
Творческий
Рукоделие основной
Форумы по интересам
Фиолетовый форум
Сделаны в СССР
Музыкальный
Кино форум
Кладоискатели и коллекционеры
Рыболовный
Охотничий
Стильный форум
Флирт, Любовь, Знакомства
Фотофорум
Здоровье
Развитие Человека
Пивной форум
Кулинарный
Парфюмерный
Парфюмерная Лавка
Собачий форум
Собачий форум: Основной
Собачий форум: пристрой животных
Наши Дети
Наши дети
Школьный форум
Особые дети
Технофорумы
Интернет-НН
GPS форум
Мобильный форум
Техно-форум
Технотуса
Проф. и бизнес форумы
Бизнес форум
Фотография
Недвижимость
Банковский форум
Медицина
Форум трейдеров
Бухучет и аудит
Юридический
Подбор персонала
Разработчики ПО
Строительные форумы
Строительный форум (основной)
Окна
Форум электриков
Мебель
Кондиционирования и вентиляция
Форум строительных объявлений
Форум проектировщиков
Все строительные форумы
Туризм, отдых, экстрим
Туризм, отдых, экстрим
Спортивные форумы
Клуб болельщиков
Спортплощадка
Боевые искусства
Велофорумы Нижнего Новгорода
Велофорум Нижнего Новгорода
Путешествия
Нижегородская область
Недвижимость
Недвижимость
Ипотека
Земельный форум
ТСЖ
Садоводческое товарищество
Жилые районы
Автозаводский район
Сормовский район
Мещерское озеро
Все форумы районов
Форумы домов
Корабли
Новая Кузнечиха
Октава ЖК (ул. Глеба Успенского)
Мончегория ЖК
Аквамарин ЖК (Комсомольская пл.)
Сормовская Сторона ЖК
КМ Анкудиновский парк ЖК
Красная Поляна ЖК (Казанское шоссе)
Времена Года ЖК (Кстовский р-он)
Стрижи ЖК (Богородский р-он)
На Победной ЖК (Победная ул., у дома 18)
Окский берег ЖК (п. Новинки)
Цветы ЖК (ул. Академика Сахарова)
Деревня Крутая кп (Кстовский р-он)
Опалиха кп (Кстовский р-он)
Юг мкр. (Южный бульвар)
Гагаринские высоты мкр.
Бурнаковский мкр.
Белый город мкр. (60-лет Октября ул.)
Зенит ЖК (Гагарина пр.)
Седьмое небо ЖК
Все форумы домов
Частные форумы
Свадебный форум
Саровский Клуб Покупателей
Июньские мамочки
Форум безумных идей
Ночной форум
Королевство кривых зеркал
Ищу вторую половинку!
Лютики-цветочки КУПЛЯ-ПРОДАЖА
Отряд стройности
Пчеловодство
Форум ленивых
Волейбольный клуб туристов
Встречи для секса
Буду мамой!
Алкогольный форум
Лютики-цветочки
Котоводство
Форум сексуального опыта
Свободка
Форум модераторов
Форум забаненных
Новый форум модераторов
Отзывы и предложения (техподдержка)
Задачка про зайчика
Флуд программистов
1181
23
Поделиться
Есть интересная задачка про зайчика. Полный текст:
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек 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. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.
Для проверки: 1 и 3 = 1 вариант, 2 и 7 = 21 вариант, 3 и 10 = 274 варианта
Количество способов я посчитал. Возникла мысль вывести список маршрутов (т.е. 1+1+1+1 и пр.). И вот тут чет приуныл. Есть идеи?
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек 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. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.
Для проверки: 1 и 3 = 1 вариант, 2 и 7 = 21 вариант, 3 и 10 = 274 варианта
Количество способов я посчитал. Возникла мысль вывести список маршрутов (т.е. 1+1+1+1 и пр.). И вот тут чет приуныл. Есть идеи?
А какие средства вывода доступны?
Мне бы алгоритм формирования этого списка.. как выводить неинтересно.
Ааа)) Так "количество способов я посчитал" на форуме разработчиков ПО выглядит, будто алгоритм-то уже есть ;) Как считал, так и формируй, в чём конкретно проблема-то?
Я посчитал количество не формируя сами наборы. Вот код если интересно pastecode.ru/e1a306/
Можно рекурсивно попробовать. Вроде глубина рекурсии будет не больше длины лестницы. При небольших входных данных прокатит (стека хватит) и работать будет относительно быстро.
Значительно медленней - полный перебор ( 2**N вариантов) даже не предлагаю.
Без глубокого погружения предположу примерно такой вариант.
Внешний цикл по i от N до N / K (правильно округлить) - это то, за сколько прыжков заяц до верха доберется.
Потом лестницу представляем как массив ступенек где 0 - заяц не вставал на ступеньку, 1 - вставал пока прыгал до верха. И расставляем i единичек при условии что нет больше и равного K нулей подряд.
Каждый вариант преобразуем в вывод варианта прыжков.
Например, вариант для 6-ти ступенек:
1 0 0 1 0 1
это соответствует выводу 1 + 3 + 2
Значительно медленней - полный перебор ( 2**N вариантов) даже не предлагаю.
Без глубокого погружения предположу примерно такой вариант.
Внешний цикл по i от N до N / K (правильно округлить) - это то, за сколько прыжков заяц до верха доберется.
Потом лестницу представляем как массив ступенек где 0 - заяц не вставал на ступеньку, 1 - вставал пока прыгал до верха. И расставляем i единичек при условии что нет больше и равного K нулей подряд.
Каждый вариант преобразуем в вывод варианта прыжков.
Например, вариант для 6-ти ступенек:
1 0 0 1 0 1
это соответствует выводу 1 + 3 + 2
Значит тебе надо другой способ. А твой старый сродни
umk.portal.kemsu.ru/uch-mathematics/papers/posobie/r2-3.htm
почитай, в будущем сэкономишь время :) Когда надо будет чисто кол-во вычислить. И наглядней будет код.
umk.portal.kemsu.ru/uch-mathematics/papers/posobie/r2-3.htm
почитай, в будущем сэкономишь время :) Когда надо будет чисто кол-во вычислить. И наглядней будет код.
Спасибо, 13 лет спустя тервер наконец пригодился
.
Элементарно. См. динамическое программирование. Перебираешь последний шаг для i=1..К и к нему добавляешь решение для подзадачи при N1 = N-K.
Ага... я вчера тоже прочитав первый пост, минут 10 порисовал, и что-то мне это напомнило из древности - кажется алгоритм Дейкстры, если не ошибаюсь)
Так и получилось в реализации. Решение в последнем элементе массива, каждый элемент массива равен сумме предыдущих.
Да, это идеально и быстро работает, чтобы подсчитать количество вариантов. Но вот чтобы вывести все варианты - тут не все так просто.
Ничего сложного, передавайте рекурсивно уже найденное окончание последовательности.
захардкодить подмаршруты для всех вариантов меньше К,
генерить цепочки маршрутов исходя из количества К в N.
Т.е. 1+1+1 + 1 или 3 + 1 ( где "+ с пробелами по бокам" - разделитель цепочек).
(Предложенный алгоритм не смотрел - исходил из сочетаний шагов в К и сочетаний этих К-сочетаний в N)
генерить цепочки маршрутов исходя из количества К в N.
Т.е. 1+1+1 + 1 или 3 + 1 ( где "+ с пробелами по бокам" - разделитель цепочек).
(Предложенный алгоритм не смотрел - исходил из сочетаний шагов в К и сочетаний этих К-сочетаний в N)
Если в лоб рекурсивно, то как-то так: https://github.com/Labutin/JumpingRabbit/blob/master/Rabbit.go
Сделал добавив в исходный код формирование маршрутов. Всем спасибо :)
Пацаны, что-то сложное накрутили.
весь код в трех строках
from functools import reduce
def S(n,k):
if n >= k: return 2**(k-1)
return reduce(lambda s, i: s + S(n, k - i - 1), range(n), 0)
Проверяем:
>>> S(2,7)
21
>>> S(3,10)
274
>>> S(1,3)
1
>>>
ЗЫ: язык - питон, форум сожрал отступы.
весь код в трех строках
from functools import reduce
def S(n,k):
if n >= k: return 2**(k-1)
return reduce(lambda s, i: s + S(n, k - i - 1), range(n), 0)
Проверяем:
>>> S(2,7)
21
>>> S(3,10)
274
>>> S(1,3)
1
>>>
ЗЫ: язык - питон, форум сожрал отступы.
А S(1,1) == 0?
$ python
>>> from functools import reduce
>>>
>>> def S(n,k):
if n >= k: return 2**(k-1)
return reduce(lambda s, i: s + S(n, k - i - 1), range(n), 0)
>>> S(1,1)
1
>>>
>>> from functools import reduce
>>>
>>> def S(n,k):
if n >= k: return 2**(k-1)
return reduce(lambda s, i: s + S(n, k - i - 1), range(n), 0)
>>> S(1,1)
1
>>>
Да я тупанул немного, ** возведение в степень, а не умножение. Очень лаконичное решение у Вас получилось. А маршруты нарисовать?
Вся магия в том что удалось добавить немного математики и спрятать цикл в reduce.
Если выводить маршруты, то алгоритм будет тот же самый что и выше. Разве что можно еще добавить шаманства за счет питоновских генераторов.
Если выводить маршруты, то алгоритм будет тот же самый что и выше. Разве что можно еще добавить шаманства за счет питоновских генераторов.
Понятие "сложно накрутили" очень относительное.
Я сам в восторге от функционального программирования (Scala, Haskel), но 90% моих знакомых программистов такое никогда не напишут. Поймут конечно, но так писать не смогут. Не то, чтобы не хотят - именно не смогут. Более того, 90% студентов, учащихся на программистов так писать не смогут (я знаю, что говорю). Можно конечно сказать "вон из профессии". Но не всем же быть "художниками"! "Маляры" тоже нужны.
А держать команду, которая умеет так писать "с закрытыми глазами" что-то очень дорогое удовольствие.
Ну это так, офтопик, т.к. глаз зацепился за слово "сложно".
Я сам в восторге от функционального программирования (Scala, Haskel), но 90% моих знакомых программистов такое никогда не напишут. Поймут конечно, но так писать не смогут. Не то, чтобы не хотят - именно не смогут. Более того, 90% студентов, учащихся на программистов так писать не смогут (я знаю, что говорю). Можно конечно сказать "вон из профессии". Но не всем же быть "художниками"! "Маляры" тоже нужны.
А держать команду, которая умеет так писать "с закрытыми глазами" что-то очень дорогое удовольствие.
Ну это так, офтопик, т.к. глаз зацепился за слово "сложно".
Рейтинг основных форумов
Городские форумы
Городской форум
Городской форум для новичков
Нижегородская политика
Жалобная книга
Бабский форум
Мужской
Анонимный медицинский форум
Дурацкие вопросы
Автофорумы
Автофорум главный
Девушка за рулем
ВАЗ форум
4х4 форум
Жалобный
Шевроле Форум
Такси
Автозапчасти
Гаражный форум
KIA-форум
Рено форум
Hyundai Форум
VAG Форум
Форумы покупок
Центр раздач: информационный форум
Глав-Пристрой (со всех форумов, взрослый)
Совместная покупка
Совместная покупка: центральный
Совместная покупка: взрослый
Совместная покупка: вкусный
Совместная покупка: мама и малыш
Совместная покупка: уютный
Совместная покупка: сбор предоплаты, раздачи
Совместная покупка: услуги
Совместная покупка: область
Совместная покупка: Дзержинск
Совместная покупка: Саров
Зарубежные интернет-покупки
Покупаем вместе
Покупаем Вместе: Основной
Покупаем вместе: БОЛЬШОЙ ШОПИНГ (взрослый)
Покупаем вместе: БЕБИ-ШОП (детский)
Покупаем вместе: ДОМОВОЙ
Покупаем вместе: ГАСТРОНОМ
Покупаем вместе: Сбор предоплаты, раздачи
Покупаем Вместе: пристрой
Покупаем Вместе: услуги
Выгодная покупка
Выгодная покупка - общие вопросы
Выгодная покупка - взрослый
Выгодная покупка - детский
Выгодная покупка - сбор предоплаты, раздачи
Выгодная покупка - объявления
Форум закупок
Мой малыш
Мой малыш - Основной
Мой малыш - Объявления. Общий
Мой малыш - Объявления: детская одежда
Мой малыш - Объявления: детская обувь
Мой малыш - Объявления: детский транспорт, игрушки, мебель
Халявный
Халявный (основной)
Котята и др. животные
Элитный (продажа неликвидных товаров)
Услуги
Домоводство
Полезный форум
Бытовые проблемы
Деревенский форум
Домоводство
Цветочный форум
Форум владельцев кошек
Дачный. Основной.
Бытовая Техника
Творческий
Рукоделие основной
Форумы по интересам
Фиолетовый форум
Сделаны в СССР
Музыкальный
Кино форум
Кладоискатели и коллекционеры
Рыболовный
Охотничий
Стильный форум
Флирт, Любовь, Знакомства
Фотофорум
Здоровье
Развитие Человека
Пивной форум
Кулинарный
Парфюмерный
Парфюмерная Лавка
Собачий форум
Собачий форум: Основной
Собачий форум: пристрой животных
Наши Дети
Наши дети
Школьный форум
Особые дети
Технофорумы
Интернет-НН
GPS форум
Мобильный форум
Техно-форум
Технотуса
Проф. и бизнес форумы
Бизнес форум
Фотография
Недвижимость
Банковский форум
Медицина
Форум трейдеров
Бухучет и аудит
Юридический
Подбор персонала
Разработчики ПО
Строительные форумы
Строительный форум (основной)
Окна
Форум электриков
Мебель
Кондиционирования и вентиляция
Форум строительных объявлений
Форум проектировщиков
Все строительные форумы
Туризм, отдых, экстрим
Туризм, отдых, экстрим
Спортивные форумы
Клуб болельщиков
Спортплощадка
Боевые искусства
Велофорумы Нижнего Новгорода
Велофорум Нижнего Новгорода
Путешествия
Нижегородская область
Недвижимость
Недвижимость
Ипотека
Земельный форум
ТСЖ
Садоводческое товарищество
Жилые районы
Автозаводский район
Сормовский район
Мещерское озеро
Все форумы районов
Форумы домов
Корабли
Новая Кузнечиха
Октава ЖК (ул. Глеба Успенского)
Мончегория ЖК
Аквамарин ЖК (Комсомольская пл.)
Сормовская Сторона ЖК
КМ Анкудиновский парк ЖК
Красная Поляна ЖК (Казанское шоссе)
Времена Года ЖК (Кстовский р-он)
Стрижи ЖК (Богородский р-он)
На Победной ЖК (Победная ул., у дома 18)
Окский берег ЖК (п. Новинки)
Цветы ЖК (ул. Академика Сахарова)
Деревня Крутая кп (Кстовский р-он)
Опалиха кп (Кстовский р-он)
Юг мкр. (Южный бульвар)
Гагаринские высоты мкр.
Бурнаковский мкр.
Белый город мкр. (60-лет Октября ул.)
Зенит ЖК (Гагарина пр.)
Седьмое небо ЖК
Все форумы домов
Частные форумы
Свадебный форум
Саровский Клуб Покупателей
Июньские мамочки
Форум безумных идей
Ночной форум
Королевство кривых зеркал
Ищу вторую половинку!
Лютики-цветочки КУПЛЯ-ПРОДАЖА
Отряд стройности
Пчеловодство
Форум ленивых
Волейбольный клуб туристов
Встречи для секса
Буду мамой!
Алкогольный форум
Лютики-цветочки
Котоводство
Форум сексуального опыта
Свободка
Форум модераторов
Форум забаненных
Новый форум модераторов
Отзывы и предложения (техподдержка)
Последние темы форумов
Форум
Тема (Автор)
Ответов
Разработчик .net
Profit Search
70000 -
100000 руб.
100000 руб.
Неполное среднее образование, стаж работы 3-5 лет, полная занятость
Программист-разработчик Full-Stack
ГК "Kolobox"
70000 -
100000 руб.
100000 руб.
Высшее образование, стаж работы более 5 лет, полная занятость
Карта сайта | 18+
ООО «Сеть городских порталов»
© 1999 - 2024
Реклама на NN.RU +7 (831) 261-37-60, reklama52@iportal.ru
Раздел технической поддержки | Для Роскомнадзора и госорганов: juristnn@iportal.ru
Реклама на NN.RU +7 (831) 261-37-60, reklama52@iportal.ru
Раздел технической поддержки | Для Роскомнадзора и госорганов: juristnn@iportal.ru
Т.к. вы неавторизованы на сайте. Войти.
Т.к. вы не трастовый пользователь. Как стать трастовым.
Т.к. тема является архивной.