Была там задача, вот краткое условие: "У чисел от 1 до 1000, у каждого посчитали сумму цифр, и расставили по возрастанию (если у чисел одинаковая сумма цифр, то выбирается большее изначально, 19, 91, 46, то будет по порядку 19, 46, 91). На каком месте стоит число 997? "
Изичная задача, у 997 сумма 25, и чисел с большей суммой цифр всего 5, 998, 989, 899, и 999. Значит 997 стоит на 1000 - 5 ом месте, то есть на 995.
Окей, но сегодня я подумал, что это очень годная задача. Если взять другое число, которое нельзя так просто найти, допустим 717 (чисто на рандом взял), там уже не получится просто с конца или с начала. Ну и как его найти? Алсо, скинул другу методисту,
но ему нужно решение. А оно мне непонятно, вообще.
Собсна, если это возможно решить, то напишите решение, или накидайте статьи по этой фигне. Если думаете что это нерешаемо, то напишите почему? Доказательство того что задача нерешаемая, тоже является решением.
У 717 сумма 15, а всего у нас сумм от 1 до 27
Тогда нужно посчитать сколько у нас представлений каждого числа от 16 до 27 (от 1 до 14) в виде суммы 3 натуральных чисел <10 (пусть f(n)=(n+1)*(n+2)/2, тогда это будет f(n)-g(n) если нигде не ошибся)
Тогда
1: 3 + 1
2: 6
...
9: 55
10: 66 - 3
11: 78 - 9
...
14: 120 - (15+12+9+6+3)
это всё суммируется, после чего мы находим и прибавляем порядковый номер 717 относительно чисел с суммой 15. Этот же алгоритм годится и для любых других чисел из интервала [1; 1000
Хотя я бы посчитал на пеке и не парился)
извиняюсь что не подробно, просто я уже спать собирался
Исторически в позиционных системах очень много смысла, потому что они удобны для записи, чтения и счёта. Математически - ну, p-адические числа довольно удобно определять похожим способом, так что, глядишь, и не зря придумали.
Спасибо, еще вопрос, можно ли сделать что либо такое же, но если сумма не складывается, а перемножается?
Можно, для этого надо найти сколькими способами можно представить число n как произведение 3 натуральных чисел <10 (учитывая порядок)
>>65342
Сколько у нас способов представить число n как сумму 2 натуральных чисел (учитывая порядок)? Вот и иди от этого.
или гугли представление чисел в виде слагаемых через многочлены
Прости, может я слишком тупой, но как кол-во вариантов представления числа суммой двух связано с самой задачей?
Первое.
4=0+4=1+3=2+2=3+1=4+0
5=1+s(4)=1+0+4=1+1+3=1+2+2=1+3+1=1+4+0
5=s(4)+1=0+4+1=1+3+1=2+2+1=3+1+1=4+0+1
...
S(5) = (5+s(0)) + (4+s(1)) + (3+s(2)) +...+ (0+s(5)) = f(5)
s(n) - представление суммой двух
S(n) - представление суммой 3-х
Но не исключено что и я нигде не ошибся, лень перепроверять.
Я думаю ты обсчитался. Смотри, комплюхтер считает, что для того же 5 кол-во вариантов - 21.
5--1
14--2
23--3
32--4
41--5
50--6
104--7
113--8
122--9
131--10
140--11
203--12
212--13
221--14
230--15
302--16
311--17
320--18
401--19
410--20
500--21
Вот, вроде ничего не пропустил.
S(5)=(5)+(4+2)+(3+3)+(2+4)+(1+5)+(5)=34. Если я сам нигде не обсчитался, и правильно понял про что ты говоришь.
И все же, что такое g(n). Все твои ответы совпадают с комплюхтерными, так что если сможешь обьяснить, то я буду очень благодарен.
g(n) - это количество представлений числа n в виде суммы 3 слагаемых, где хотя бы одно слагаемое > 9.
15 = 15 + a + b = a + 15 + b = a + b + 15 (отсюда множитель 3)
15 = 14 + a + b = a + 14 + b = a + b + 14 итд. до 10
Тогда g(15) = 3 (1 + s(0)) + 3 (1 + s(1)) +...+ 3 (1 + s(5))
В общем виде g(n) = 3 (n - 9) * (n - 8) / 2 для n > 9
и g(n) = 0 для n < 10
>>Я думаю ты обсчитался
Скорее опечатался. Надо было так:
S(5) = (1+s(0)) + (1+s(1)) + (1+s(2)) +...+ (1+s(5)) = f(5)
Т.е. кол-во способов представить 5 одним слагаемым + s(0)
кол-во способов представить 4 одним слагаемым + s(1)
Итд.
Так, я хотя бы понял что значит f(n) и g(n).
Но можешь ли ты обьяснить как ты получаешь эти значения?
C S() и s() вообще ничего не понял.
Заранее спасибо, что хотя бы пытаешься обьяснить
Нет, ничего я "обьяснять" больше не буду. Тут и так разжеванно так, что даже ежу станет понятно. Ты либо знаешь
- комбинаторику
- сумму арифметической прогрессии
либо нет. Если последнее, возьми учебник и повтори. Всё.
Анон, последний вопрос.
Все понял уже, но с чего 15 сначала =15+а+б и перестановки этого, а потом становится =14+а+б?
И почему кол-во сумма способов представить от n до 1 одним слагаемым и кол-во способов представить от n до 1 двумя слагаемым равняется кол-ву вариантов представления n тремя числами?