Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 2 |
[ Сообщений: 16 ] | На страницу 1, 2 След. |
|
Автор | Сообщение | |
---|---|---|
bmhmg |
|
|
Буду рад любой помощи и подсказкам. |
||
Вернуться к началу | ||
Kirill1986 |
|
|
Мне очень стыдно, но, признаться, Вы меня загрузили. Я не могу найти приемлемого комбинаторного решения этой задачи. Поэтому все, что я могу Вам предложить, это подойти к большой доске и нарисовать дерево возможных комбинаций наподобие того, что прикреплено в файле. У Вас будет всего два дерева. Одно начинается с буквы b, другое - с с. Третье дерево получится из второго заменой c на d и наоборот. Возможности бумаги не позволяют рисовать такие большие деревья. Для доски это будет возможно. Но вот если бы у Вас было не 7 символов, а, скажем, 70, то я на данный момент пас. Могучие и великие участники форума, буду благодарен Вам лично за решение этой бросающей всем нам вызов задачи! Я готов признаться, что плохо знаю комбинаторику, но хочу знать, как решается эта задача.
|
||
Вернуться к началу | ||
Kirill1986 |
|
|
Не могу прикрепить файл. Как файл здесь прикреплять?
|
||
Вернуться к началу | ||
swan |
|
|
Пусть [math]x_{k,b}, \, x_{k,c}, \, x_{k,d}[/math] - количество наборов с данным свойством из [math]k[/math] символов и с последним символом b, c, d соответственно.
Тогда справедливо [math]x_{k+1,d}=x_{k,b}+x_{k,d}[/math] [math]x_{k+1,c}=x_{k,b}+x_{k,c}[/math] [math]x_{k+1,b}=x_{k,b}+x_{k,c}+x_{k,d}[/math] [math]x_{1,b}=x_{1,c}=x_{1,d}=1[/math] Можно еще чуть упростить, если заметить, что в силу симметрии [math]x_{k,c}= x_{k,d}[/math] |
||
Вернуться к началу | ||
За это сообщение пользователю swan "Спасибо" сказали: Kirill1986 |
||
Kirill1986 |
|
|
swan, т. е. Вы предлагаете рекуррентными соотношениями довести задачу до ответа? Но, позволю спросить, если [math]k[/math] очень большое, то никаких других рецептов, дающих ответ в явной форме нет, что ли? Интересно самому стало.
|
||
Вернуться к началу | ||
Kirill1986 |
|
|
Вернуться к началу | ||
swan |
|
|
Почему так не любите рекуррентные формулы?
Уверяю вас, на практике решение комбинаторных задач через них наиболее просто и эффективно. По алгоритму, подобному вычислению чисел Фибоначчи можно найти за [math]\log k[/math] шагов. То есть быстрее, чем, скажем, вычислить [math]\sin k[/math]. По поводу конкретно данной задачи. Я стал выписывать значения [math]x_{k,b}[/math] и [math]x_{k,c}[/math]. И что-то смутно знакомое бросилось в глаза. Залез в OEIS и точно. Наши [math]x_{k,b}[/math] и [math]x_{k,c}[/math] есть ни что иное как числитель и знаменатель подходящей дроби к [math]\sqrt 2[/math]. Соответственно можете ознакомиться с цепными дробями и прочитать про методы их вычисления. |
||
Вернуться к началу | ||
За это сообщение пользователю swan "Спасибо" сказали: Kirill1986 |
||
Kirill1986 |
|
|
Если воспользоваться рекуррентными соотношениями, которые предложил swan, то для данной конкретной задачи у меня получилось:
[math]x_{7,b}=239[/math], [math]x_{7,c}=169[/math], [math]x_{7,d}=169[/math]. Общее число способов: [math]x_{7}= x_{7,b}+x_{7,c}+x_{7,d}=577[/math]. swan, большое спасибо! Но в общем случае задача какая-то мутноватая... |
||
Вернуться к началу | ||
Kirill1986 |
|
|
Беру свои слова про мутноватую задачу обратно! Просто я подзабыл теорию чисел...
|
||
Вернуться к началу | ||
ivashenko |
|
|
Я посчитал за 2 минуты в уме, но наверное неправильно, получилось 2*80+113= 273.
|
||
Вернуться к началу | ||
На страницу 1, 2 След. | [ Сообщений: 16 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Число комбинаций | 4 |
283 |
22 фев 2019, 21:28 |
|
Просчет количества комбинаций
в форуме Комбинаторика и Теория вероятностей |
5 |
481 |
25 июл 2016, 15:46 |
|
Количество комбинаций пароля
в форуме Комбинаторика и Теория вероятностей |
12 |
444 |
25 янв 2021, 15:27 |
|
какова вероятность комбинаций ?
в форуме Комбинаторика и Теория вероятностей |
7 |
523 |
06 авг 2018, 19:02 |
|
Расчет числа комбинаций | 6 |
261 |
23 июн 2022, 15:49 |
|
Вероятность симметничных комбинаций
в форуме Теория вероятностей |
6 |
424 |
10 авг 2014, 13:37 |
|
Перебор k комбинаций из n шаров в b корзинах
в форуме Комбинаторика и Теория вероятностей |
9 |
222 |
24 мар 2022, 22:40 |
|
Как вычислить число уникальных комбинаций
в форуме Теория вероятностей |
13 |
691 |
12 апр 2023, 22:18 |
|
Комбинаторика и количество подсчета комбинаций
в форуме Комбинаторика и Теория вероятностей |
14 |
137 |
09 янв 2024, 16:53 |
|
Как рассчитать количество вариантов комбинаций?
в форуме Комбинаторика и Теория вероятностей |
2 |
1089 |
29 июл 2016, 05:09 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |