1. Есть 10 коробок, в каждую из которых входит 10 деревянных блоков. Всего имеем 100 блоков, которые раскрашены в 10 разных цветов. Они могут быть разукрашены в неравных количествах. Нужно доказать, что возможно упаковать все 100 блоков в коробки учитывая, что в одной коробке не будут присутствовать блоки более чем двух цветов.
2. Заяц стоит перед 10-ю ступенями. Умеет прыгать либо на 1 ступень вверх, либо на 2. Нужно найти количество путей, которыми он может добраться до финиша. Пример 221221, 112222, и т.д.
Дополнительно нужно рассмотреть результат, если заяц может прыгать на X ступеней, дополнительно к его первоначальным возможностям.
По поводу первой задачи у меня пока идей нет, а вторую знаю как без проблем решить перебором на с#. Идея в том, что эту задачу можно решить математическим путем, а здесь я не настолько силен.
Подскажите пожалуйста, в какую сторону копать?
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, radzivil, Вы писали:
A>Индукция?
Почитал про математическую индукцию.
Не понимаю только, как этот метод к 1-й задаче можно применить.
По идее можно определить 1- цветов а1, а2 ... а10 и кол-во блоков б1, б2 ... б10.
а1*б1 + а2+б2 + ... + а10*б10 = 100
Допустим мы имеем 91 блоков одного цвета и 9 блоков других разных цветов, в таком случае мы можем разложить все разные цвета в разные коробки и потом добавлять туда блоки одного цвета. Получим в итоге базовый результат, который удовлетворяет условиям.
Если мы меняем цвет одного из 91 блоков на другой, то мы заменяем им блок из соответствующей коробки.
Вроде бы идея такая, но как описать это правильно математически?
Здравствуйте, radzivil, Вы писали:
R>1. Есть 10 коробок...
Ув. adontz уже намекнул
R>2. Заяц стоит перед 10-ю ступенями. Умеет прыгать либо на 1 ступень вверх, либо на 2.
У нас может быть n/2 (для чётных) / (n/2)+1 (для нечётных) способов подняться (без учёта порядка прыжков). Число размещений для каждого способа — x!, в сумме — sum(x: n/2..n) x!
Здравствуйте, radzivil, Вы писали:
R>2. Заяц стоит перед 10-ю ступенями. Умеет прыгать либо на 1 ступень вверх, либо на 2. Нужно найти количество путей, которыми он может добраться до финиша. Пример 221221, 112222, и т.д. R>Дополнительно нужно рассмотреть результат, если заяц может прыгать на X ступеней, дополнительно к его первоначальным возможностям.
R>По поводу первой задачи у меня пока идей нет, а вторую знаю как без проблем решить перебором на с#. Идея в том, что эту задачу можно решить математическим путем, а здесь я не настолько силен. R>Подскажите пожалуйста, в какую сторону копать?
Эта задача эквивалентна задаче подсчёта способов замещения доски 2×n костяшками домино, и рассматривалась с обобщениями Кнутом то ли в "Искусстве программирования", то ли в "Конкретной математике".
Здравствуйте, Qbit86, Вы писали:
R>>2. Заяц стоит перед 10-ю ступенями. Умеет прыгать либо на 1 ступень вверх, либо на 2. Нужно найти количество путей, которыми он может добраться до финиша. Пример 221221, 112222, и т.д. R>>Дополнительно нужно рассмотреть результат, если заяц может прыгать на X ступеней, дополнительно к его первоначальным возможностям.
R>>По поводу первой задачи у меня пока идей нет, а вторую знаю как без проблем решить перебором на с#. Идея в том, что эту задачу можно решить математическим путем, а здесь я не настолько силен. R>>Подскажите пожалуйста, в какую сторону копать?
Q>Эта задача эквивалентна задаче подсчёта способов замещения доски 2×n костяшками домино, и рассматривалась с обобщениями Кнутом то ли в "Искусстве программирования", то ли в "Конкретной математике".
Да, она есть в Конкретной Математике (глава7 про Производящие функции).
Кстати, "один в один" задача про перепрыгивания рассматривается в лекциях по алгоритмам в разделе "Динамическое программирование": http://www.intuit.ru/department/algorithms/basicalgos/3/
(надо зарегиться — оно того стоит!).
Называется "Задача о кузнечике, прыгающем по столбикам.".
По сути динамика — это тоже "перебор", хотя и умный. Достоинство — что метод будет работать и для более сложных вариантов
задачи, когда некоторые позиции для прыжков могут быть запрещены (там же — "Задача о кузнечике и лягушках.").
Здравствуйте, radzivil, Вы писали: R>1. Есть 10 коробок, в каждую из которых входит 10 деревянных блоков. Всего имеем 100 блоков, которые раскрашены в 10 разных цветов. Они могут быть разукрашены в неравных количествах. Нужно доказать, что возможно упаковать все 100 блоков в коробки учитывая, что в одной коробке не будут присутствовать блоки более чем двух цветов.
Эта задача очень тесно связана со структурой данных, которая была предложена товарищем A.J. Walker в статье "An efficient method for generating discrete random variables with general distributions".
Соответственно, простой конструктивный алгоритм (то есть который явно укажет какой блок в какую коробку поместить) можно посмотреть как в оригинальной статье так и в многочисленных популярных статьях, которые на неё ссылаются. Например, этот алгоритм даже пересказан у Кнута в "Искусстве программирования", впрочем у Кнута конкретно твой исходный вопрос, насколько я помню, специально отнесён к упражнениям для самостоятельного решения.
Здравствуйте, Qbit86, Вы писали:
Q>Здравствуйте, radzivil, Вы писали:
R>>2. Заяц стоит перед 10-ю ступенями. Умеет прыгать либо на 1 ступень вверх, либо на 2. Нужно найти количество путей, которыми он может добраться до финиша. Пример 221221, 112222, и т.д. R>>Дополнительно нужно рассмотреть результат, если заяц может прыгать на X ступеней, дополнительно к его первоначальным возможностям.
R>>По поводу первой задачи у меня пока идей нет, а вторую знаю как без проблем решить перебором на с#. Идея в том, что эту задачу можно решить математическим путем, а здесь я не настолько силен. R>>Подскажите пожалуйста, в какую сторону копать?
Q>Эта задача эквивалентна задаче подсчёта способов замещения доски 2×n костяшками домино, и рассматривалась с обобщениями Кнутом то ли в "Искусстве программирования", то ли в "Конкретной математике".
А это не просто Фибоначчи получатся? В смысле что с 10-й ступеньки можно прыгнуть либо на 9-ю, либо на 8-ю, т.е. всего вариантов добраться до финиша с 10-й (обозначим f(10)) будет f(9)+f(8). При этом f(1)=1 и f(2)=2, т.е. f(10) — это 9-е число Фибоначчи.
Здравствуйте, jazzer, Вы писали:
J>А это не просто Фибоначчи получатся? В смысле что с 10-й ступеньки можно прыгнуть либо на 9-ю, либо на 8-ю, т.е. всего вариантов добраться до финиша с 10-й (обозначим f(10)) будет f(9)+f(8). При этом f(1)=1 и f(2)=2, т.е. f(10) — это 9-е число Фибоначчи.
Здравствуйте, jazzer, Вы писали:
R>>>2. Заяц стоит перед 10-ю ступенями. Умеет прыгать либо на 1 ступень вверх, либо на 2. Нужно найти количество путей, которыми он может добраться до финиша. Пример 221221, 112222, и т.д. R>>>Дополнительно нужно рассмотреть результат, если заяц может прыгать на X ступеней, дополнительно к его первоначальным возможностям.
R>>>По поводу первой задачи у меня пока идей нет, а вторую знаю как без проблем решить перебором на с#. Идея в том, что эту задачу можно решить математическим путем, а здесь я не настолько силен. R>>>Подскажите пожалуйста, в какую сторону копать?
Q>>Эта задача эквивалентна задаче подсчёта способов замещения доски 2×n костяшками домино, и рассматривалась с обобщениями Кнутом то ли в "Искусстве программирования", то ли в "Конкретной математике".
J>А это не просто Фибоначчи получатся? В смысле что с 10-й ступеньки можно прыгнуть либо на 9-ю, либо на 8-ю, т.е. всего вариантов добраться до финиша с 10-й (обозначим f(10)) будет f(9)+f(8). При этом f(1)=1 и f(2)=2, т.е. f(10) — это 9-е число Фибоначчи.
Точно, для прыжков на 1+2 ступеньки так оно и будет — рекуррентное соотношение аналогично числам Фибоначчи (об этом кстати, как раз и говорится в лекции в комменте выше).
Но для X ступеней, естественно, соотношение будет другим.
Здравствуйте, andy1618, Вы писали:
J>>А это не просто Фибоначчи получатся? В смысле что с 10-й ступеньки можно прыгнуть либо на 9-ю, либо на 8-ю, т.е. всего вариантов добраться до финиша с 10-й (обозначим f(10)) будет f(9)+f(8). При этом f(1)=1 и f(2)=2, т.е. f(10) — это 9-е число Фибоначчи.
A>Точно, для прыжков на 1+2 ступеньки так оно и будет — рекуррентное соотношение аналогично числам Фибоначчи (об этом кстати, как раз и говорится в лекции в комменте выше).
Надо будет дома посмотреть, у меня с работы доступа нету
A>Но для X ступеней, естественно, соотношение будет другим.
