a1+a2+...+an=s
0 <= ai <= x
x >= 0
n >= 1
0 <= s <= s * n, естественно...
Нужно найти z - количество уникальных комбинаций для n терминов сложения, которые в сумме дают s. Любой из терминов может иметь значение от 0 до x - целые числа.
Я уже составил программу которая считает z, но методом перебора. А это долго... Очень долго! Хотя программа и дает возможность просмотра всех этих вариантов, но они мне не нужны. Нужно только их количество!
В результате простых анализов мне стало известно следующее:
1) z принимает максимум в случае когда s=x*n/2 (округлить до целого), когда же
s --> 0 или s --> s*n, то z --> 1. Меньше 1-цы быть не может.
2) обнаружил сходство с "триугольником Паскаля" (пирамида Паскаля), где одну сторону от вершины берем за s (где 0<=s<=x*n/2) а другую за n, а на пересечении получаем z. И такой же результат получаем в симетричном отражении s (когда x*n>=s>=x*n/2). Но есть маленькое НО! Когда s --> x*n/2, то z отклоняется от действительности. Т.е. почти до середины все ОК, а когда s близко к x*n/2 - отклонения. Догадываюсь почему так происходит, но незнаю ка объяснить. Могу сказать, что это связанно с ограничением задаваемым числом x.
Вопрос: Вообще выше поставленная задача выполнима или нет?
Плииз, помогите решить - очень нужно...