Автор Тема: Игральные кости. Определение количества сочетаний для суммы на верхних гранях  (Прочитано 708 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн pyramidka

  • Пользователь
  • Сообщений: 7
    • Просмотр профиля
Здравствуйте.

Прошу помощи в решении следующей задачи.

Имеются четыре девятигранных игральных кости (\( 4D9 \)) (\( D \) - dice (англ. игральные кости)). Необходимо для любой суммы \( S \) в пределах \( 4≤S≤36 \) определить количество таких комбинаций, чтобы числа на верхних гранях каждой кости были отсортированы в неубывающем порядке.

То есть для суммы 10 подходят: 1-1-1-7, 1-1-2-6, 1-1-3-5, 1-1-4-4, 1-2-2-5, 1-2-3-4 и т. д. и не подходят 7-1-1-1, 6-2-1-1, 3-1-5-1 и т. п.

К чему я пришёл сам: общее число удовлетворяющих условию комбинаций от 1-1-1-1 до 9-9-9-9 находится по формуле для сочетаний с повторениями. Их 495. На этом, пожалуй, всё. :(

1. Интересует как подойти к решению задачи в общем виде для любых \( xDy \), где \( x \) - количество игральных костей, \( y \) - количество граней.
2. Из первого следует, что вариант с составлением таблиц комбинаций не подходит.

С уважением,
pyramidka
С уважением,
pyramidka
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Кое-какое отношение к вашей задачи имеет эта статья
https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0
Но там нет ограничения на сами слагаемые, а у вас оно есть.
Почему-то мне кажется, что ваша задача имеет более простое решение именно в силу этого ограничения.
Но сейчас время позднее, голова клонится, ничего вразумительного сказать не могу... :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin, pyramidka

Оффлайн pyramidka

  • Пользователь
  • Сообщений: 7
    • Просмотр профиля
Байт, спасибо за ответ. Ознакамливаюсь с темой, предложенной вами.

Появилась мысль: можно ли со стороны распределения вероятностей подойти к решению? Признаюсь, в этом я не силён, но теорию предложил как таковую, что кажется мне связанной с темой.
С уважением,
pyramidka
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
можно ли со стороны распределения вероятностей подойти к решению?
Имхо, нет смысла. Ибо Тервер основан на комбинаторике, а не наоборот.
Однако, ночные раздумья ни к чему не привели. Можно составить рекурентную формулу. Это не очень сложно. По ней можно вычислить количество комбинаций для конкретной пары x, y.
Можно составить небольшую программку.
Но конечной формулы я не вижу (это вовсе не значит, что ее нет :) )

Вот что. Попробуйте обратиться с этим вопросом на dxdy.ru
Там народ довольно козюлистый, но соображают здорово.
Если и там ничего не придумают - тогда только программки писать...
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн pyramidka

  • Пользователь
  • Сообщений: 7
    • Просмотр профиля
Байт, благодарю за ваш ответ.

Вы подошли вплотную к сути проблемы. Дело в том, что программу-то и надо написать. И я её таки написал. Но! Даже после многочисленных оптимизаций для количества костей 7 время отработки для всего диапазона сумм на моём железе приблизительно 15.5 с. Для ≥8 костей время становится уже совсем неприличным. Как сделать лучше у меня мысль имеется, но пока не осилил. Потому, решил подойти к вопросу со стороны использования математического аппарата, а не подбора, как есть сейчас.

Можно составить рекурентную формулу. Это не очень сложно. По ней можно вычислить количество комбинаций для конкретной пары x, y.

Если вы имеете в виду \( xDy \), то я уже обнаружил как искать: сочетания с повторениями из \( y \) по \( x \). Если нет, то будьте любезны поподробнее.
С уважением,
pyramidka
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
И я её таки написал. Но! Даже после многочисленных оптимизаций для количества костей 7 время отработки для всего диапазона сумм на моём железе приблизительно 15.5 с. Для ≥8 костей время становится уже совсем неприличным.
Осмелюсь предположить, что вы генерируете все возможные комбинации. Угадал? Но это совершенно ни к чему. Возможны другие подходы.
Попробуйте скинуть вашу программку в заархивированном виде. Правда, не знаю, дает ли этот форум такую возможность, я ей никогда не пользовался.
Ага, есть! Надо перейти в "Предварительный просмотр" и там есть  кнопочка "Вложения"
Я со своей стороны попробую набросать программку на Си.
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Цитировать
Я выявил математическую закономерность генерации первой и последней комбинации для любых суммы и количества игральных костей. Так как в задании речь ведётся только о xD9, то и генерация производится по сценарию шаганий по -9 от большего числа к меньшему с двумя проверками: 1) является ли каждый символ левее не более того, что правее и, если первая пройдена, 2) проверка суммы цифр на соответствие заданной.
Значит, я не угадал. Но все-таки покажите. Имхо, рекурсивный алгоритм, как я его вижу, должен дать неплохой результат.
И еще вопрос. Вас интересует количество вариантов именно для конкретного значения суммы? Или хотелось бы получить это количество для всех возможных сумм?
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн pyramidka

  • Пользователь
  • Сообщений: 7
    • Просмотр профиля
Вас интересует количество вариантов именно для конкретного значения суммы? Или хотелось бы получить это количество для всех возможных сумм?
Интересует колиство вариантов для каждых суммы и количества костей конкретно. Но если функцию запускать последовательно для каждой суммы из диапазона (начало, конец) или для сумм из какой-либо выборки, то она выдаст последовательно результат для каждой суммы из диапазона (выборки). То есть программа в данном виде удовлетворяет ТЗ но не удовлетворяет времени выполнения.
С уважением,
pyramidka
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Для 19 костей с 19-ю гранями считает за пару минут. Сразу все возможные суммы. Сейчас сменю кодировку и выложу.
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Вот. Только экзешник 16-битовый и для Винды (для ДОСа, в самом деле)
Но исходник есть и вы с ним можете делать, что хотите. Хоть переписать на свою любимую змеюку.
Если что непонятно - спрашивайте.
В самом деле там используется(моделируется) G-ичная система счисления и генерируются все числа длины K с неубыванием цифр. Нечто похожее делается и в вашей программе, как я понял.
Программа получилась не очень длинная.... :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: pyramidka

Оффлайн pyramidka

  • Пользователь
  • Сообщений: 7
    • Просмотр профиля
Благодарю за уделённое время. Ныряю изучать внутренности, ибо мне всё равно надо на Python реализацию делать.

Вопросы - задам, по окончании - отпишусь. Спасибо.  :)
С уважением,
pyramidka
 

Оффлайн pyramidka

  • Пользователь
  • Сообщений: 7
    • Просмотр профиля
Что я могу сказать. Ваша программа без преувеличения гениальна, ибо согласно утилите time время выполнения вашей для \( 9D9 \) 0.005 c, моей для \( 7D9 \) >14 c.  :o

В С не разбираюсь совсем, но вопросы не стану пока задавать. Повчитываюсь в циклы и попытаюсь понять заполнение разрядов. Кстати, благодаря вам научился компилировать *.c вообще и под UNIX в частности. Ещё раз благодарю за ваше время.  :)
С уважением,
pyramidka
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 942
  • Поблагодарили: 675 раз(а)
    • Просмотр профиля
Ваша программа без преувеличения гениальна,
Доброе слово и кошке приятно :)
моей для 7D9 >14 c. 
Кстати, это не может быть еще связано с тем, что Питон - интерпретируемый язык (кажется)?
Хотя это нисколько не умаляет моей гениальности! Как говорят у нас в деревне - "Я еще и не так могу!" :)
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 

Оффлайн pyramidka

  • Пользователь
  • Сообщений: 7
    • Просмотр профиля
Итоги подведём. (с)  :)

На основе идей и стараниями Байта написал подходящую для моего задания и более быстродейственную относительно моей предыдущей программу. Ещё раз спасибо вам за помощь. Ваша на С будет всё равно шустрее в виду того, что Python - интерпретированный язык, и того, что у вас классный выверенный алгоритм. Программой для Python делюсь в прикреплённом файле. Вдруг кому-то понадобится.

Жаль, что не удалось понять как подсчитать количество сочетаний для суммы без генерации таковых программным методом. Но, вероятно, такой метод имеется и если кто-либо, оказавшись в этой теме, решит им поделиться, то это будет прекрасно.
С уважением,
pyramidka