1,5 Мб, 2000x2000Сап. Кароче, помогал племяннику решать олимпиадные задачи.
Была там задача, вот краткое условие: "У чисел от 1 до 1000, у каждого посчитали сумму цифр, и расставили по возрастанию (если у чисел одинаковая сумма цифр, то выбирается большее изначально, 19, 91, 46, то будет по порядку 19, 46, 91). На каком месте стоит число 997? "
Изичная задача, у 997 сумма 25, и чисел с большей суммой цифр всего 5, 998, 989, 899, и 999. Значит 997 стоит на 1000 - 5 ом месте, то есть на 995.
Окей, но сегодня я подумал, что это очень годная задача. Если взять другое число, которое нельзя так просто найти, допустим 717 (чисто на рандом взял), там уже не получится просто с конца или с начала. Ну и как его найти? Алсо, скинул другу методисту,
но ему нужно решение. А оно мне непонятно, вообще.
Собсна, если это возможно решить, то напишите решение, или накидайте статьи по этой фигне. Если думаете что это нерешаемо, то напишите почему? Доказательство того что задача нерешаемая, тоже является решением.
Была там задача, вот краткое условие: "У чисел от 1 до 1000, у каждого посчитали сумму цифр, и расставили по возрастанию (если у чисел одинаковая сумма цифр, то выбирается большее изначально, 19, 91, 46, то будет по порядку 19, 46, 91). На каком месте стоит число 997? "
Изичная задача, у 997 сумма 25, и чисел с большей суммой цифр всего 5, 998, 989, 899, и 999. Значит 997 стоит на 1000 - 5 ом месте, то есть на 995.
Окей, но сегодня я подумал, что это очень годная задача. Если взять другое число, которое нельзя так просто найти, допустим 717 (чисто на рандом взял), там уже не получится просто с конца или с начала. Ну и как его найти? Алсо, скинул другу методисту,
но ему нужно решение. А оно мне непонятно, вообще.
Собсна, если это возможно решить, то напишите решение, или накидайте статьи по этой фигне. Если думаете что это нерешаемо, то напишите почему? Доказательство того что задача нерешаемая, тоже является решением.
Всегда считал, что задачи где фигурируют суммы цифр каких то чисел это какой-то астрологический магический нумерологический рак. Позиционные системы счисления это чисто человеческая отсебятина для удобства записи количеств и в природе аналогов хоть сколько нибудь этой природе полезных они не имеют. Это как искать в Войне и Мире скрытые стихотворения перебирая слова рандомно или в какой-то закономерности.
>>315 (OP)
У 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
Хотя я бы посчитал на пеке и не парился)
извиняюсь что не подробно, просто я уже спать собирался
У 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
Хотя я бы посчитал на пеке и не парился)
извиняюсь что не подробно, просто я уже спать собирался
>>325
Исторически в позиционных системах очень много смысла, потому что они удобны для записи, чтения и счёта. Математически - ну, p-адические числа довольно удобно определять похожим способом, так что, глядишь, и не зря придумали.
Исторически в позиционных системах очень много смысла, потому что они удобны для записи, чтения и счёта. Математически - ну, p-адические числа довольно удобно определять похожим способом, так что, глядишь, и не зря придумали.
>>326
Спасибо, еще вопрос, можно ли сделать что либо такое же, но если сумма не складывается, а перемножается?
Спасибо, еще вопрос, можно ли сделать что либо такое же, но если сумма не складывается, а перемножается?
>>337
Можно, для этого надо найти сколькими способами можно представить число n как произведение 3 натуральных чисел <10 (учитывая порядок)
>>342
Сколько у нас способов представить число n как сумму 2 натуральных чисел (учитывая порядок)? Вот и иди от этого.
или гугли представление чисел в виде слагаемых через многочлены
Можно, для этого надо найти сколькими способами можно представить число n как произведение 3 натуральных чисел <10 (учитывая порядок)
>>342
Сколько у нас способов представить число n как сумму 2 натуральных чисел (учитывая порядок)? Вот и иди от этого.
или гугли представление чисел в виде слагаемых через многочлены
>>348
Прости, может я слишком тупой, но как кол-во вариантов представления числа суммой двух связано с самой задачей?
Прости, может я слишком тупой, но как кол-во вариантов представления числа суммой двух связано с самой задачей?
>>351
Первое.
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-х
Но не исключено что и я нигде не ошибся, лень перепроверять.
Первое.
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-х
Но не исключено что и я нигде не ошибся, лень перепроверять.
>>362
Я думаю ты обсчитался. Смотри, комплюхтер считает, что для того же 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). Все твои ответы совпадают с комплюхтерными, так что если сможешь обьяснить, то я буду очень благодарен.
Я думаю ты обсчитался. Смотри, комплюхтер считает, что для того же 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). Все твои ответы совпадают с комплюхтерными, так что если сможешь обьяснить, то я буду очень благодарен.
>>371
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)
Итд.
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)
Итд.
>>380
Так, я хотя бы понял что значит f(n) и g(n).
Но можешь ли ты обьяснить как ты получаешь эти значения?
C S() и s() вообще ничего не понял.
Заранее спасибо, что хотя бы пытаешься обьяснить
Так, я хотя бы понял что значит f(n) и g(n).
Но можешь ли ты обьяснить как ты получаешь эти значения?
C S() и s() вообще ничего не понял.
Заранее спасибо, что хотя бы пытаешься обьяснить
>>441
Нет, ничего я "обьяснять" больше не буду. Тут и так разжеванно так, что даже ежу станет понятно. Ты либо знаешь
- комбинаторику
- сумму арифметической прогрессии
либо нет. Если последнее, возьми учебник и повтори. Всё.
Нет, ничего я "обьяснять" больше не буду. Тут и так разжеванно так, что даже ежу станет понятно. Ты либо знаешь
- комбинаторику
- сумму арифметической прогрессии
либо нет. Если последнее, возьми учебник и повтори. Всё.
>>380
Анон, последний вопрос.
Все понял уже, но с чего 15 сначала =15+а+б и перестановки этого, а потом становится =14+а+б?
И почему кол-во сумма способов представить от n до 1 одним слагаемым и кол-во способов представить от n до 1 двумя слагаемым равняется кол-ву вариантов представления n тремя числами?
Анон, последний вопрос.
Все понял уже, но с чего 15 сначала =15+а+б и перестановки этого, а потом становится =14+а+б?
И почему кол-во сумма способов представить от n до 1 одним слагаемым и кол-во способов представить от n до 1 двумя слагаемым равняется кол-ву вариантов представления n тремя числами?
>>507
Неа, думай сам, привыкай.
a и b из 15 + a + b и a и b из 14 + a + b это совершенно разные пары чисел. Запись была с "ошибкой" намеренно мне было лень их заменять, думал ты догадаешься.
Неа, думай сам, привыкай.
a и b из 15 + a + b и a и b из 14 + a + b это совершенно разные пары чисел. Запись была с "ошибкой" намеренно мне было лень их заменять, думал ты догадаешься.