Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пазл с прикольным решением / 25 сообщений из 47, страница 1 из 2
  1  все
27.09.2021, 16:00
    #40100249
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Дано натуральное N. Выяснить, у какого целого числа из отрезка 1...N будет наибольшая сумма делителей.

время работы O(N), то есть линейное.

Про память не сказано, но чем меньше тем лучше. Насчет размерности чисел не заморачиваемся, полагаем что любое число поместится в некую "числовую переменную", размер и все операции с которой - О(1)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 16:22
    #40100254
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Мне кажется что если игнорировать полные переборы то.

Код: sql
1.
2.
3.
4.
5.
sum(f(256)) = 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 = 16

sum(f(254)) = 127 + 2 = 129

sum(f(250)) = 5 + 5 + 2 + 5 = 17



Оптимальная стратегия - может быть такая. Искать при набольшем N, наименьшее число делителей.
Глазами видно что 254 выгоднее чем 256 т.к. первый имеет один делитель равный половине числа N.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 16:43
    #40100258
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
mayton
Код: sql
1.
f(256)) = 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 = 16

что это??

на всякий: для каждого числа подразумевается сумма всех его делителей. То есть, к примеру, число 12: делители: 2, 3, 4, 6, 12, их сумма равна 27
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 16:46
    #40100260
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
А.... у меня голова забита факторизацией. Сорян. В руке молоток - и вижу кругом гвозди.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 19:08
    #40100309
exp98
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
В любом случае, при N=256 оно и будет ответом. А также при любых N= K^M. Очевидно, что и при простом N. Также очевидно, что ни один делитель N не будет ответом.
Для остальных N на глаз и не скажу. Можно попробовать многочлены Sum(x10^y).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 20:22
    #40100326
exp98
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Как всегда поспешил выше. Простое N ответом не всегда будет.))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 20:42
    #40100333
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Имя пользователя1,

Если N нечетное, то N-1. Иначе N.

Пример:
N=16, делители: (8,2) и (4,4). С наибольшей суммой делителей: 8+2=10
N=17, нечетное, простое, смотри N=16
N=18, делители: (9,2) и (6,3). С наибольшей суммой делителей: 9+2=11
N=19, нечетное, простое, смотри N=18
N=20, делители: (10,2) и (4,5). С наибольшей суммой делителей: 10+2=12
N=21, нечетное, делители: (7,3). С наибольшей суммой делителей: 7+3=10, смотри N=20
....
N=256, делители: (128,2), (64,4), (32,8) и (16,16). С наибольшей суммой делителей: 8+2=10


Время работы O(1) :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 20:45
    #40100334
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Если я правильно понял, то все возможные делители надо складывать, т.е. для степеней двойки ответ будет N*2-2
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 22:58
    #40100349
Соколинский Борис
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Имя пользователя1
на всякий: для каждого числа подразумевается сумма всех его делителей. То есть, к примеру, число 12: делители: 2, 3, 4, 6, 12, их сумма равна 27
4 для 16 дважды учитывается?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 23:06
    #40100350
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Корявенько поставлена задача. Надо добавить что делать с составными делителями.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.09.2021, 23:13
    #40100352
booby
booby
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
mayton,

то, о чем пишет топикстартер, называется аликвотная сумма ( с точностью до почему-то забытой единицы).
Определения здесь
https://ru.wikipedia.org/wiki/Функция_делителей
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 09:37
    #40100393
Gennadiy Usov
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Имя пользователя1
Дано натуральное N. Выяснить, у какого целого числа из отрезка 1...N будет наибольшая сумма делителей.
время работы O(N), то есть линейное.
Про память не сказано, но чем меньше тем лучше. Насчет размерности чисел не заморачиваемся, полагаем что любое число поместится в некую "числовую переменную", размер и все операции с которой - О(1)
У числа N есть n простых делителей.
Делителями числа N будут различные комбинации этих простых делителей.
Но, если будут одни двойки. то комбинации повторяются.
Следовательно, простые делители должны быть разными.

Тогда больше всего будет делителей у числа, которое есть Р! (факториал).
Не совсем, лучше N - произведение различных минимальных простых чисел.
А дальше можно думать о сумме этих делителей, в том числе 1 и N.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 10:24
    #40100395
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Соколинский Борис
4 для 16 дважды учитывается?
один раз. Каждый делитель числа X попадает в сумму делителей числа Х по одному разу.
mayton
Надо добавить что делать с составными делителями.
то же, что и с простыми. Добавлять в сумму делителей числа.
booby
с точностью до почему-то забытой единицы
можно добавить и эту единицу - на решение это не влияет.

прикольность известного мне прикольного решения в том, что там по ходу пьесы мы узнаем сумму делителей для каждого числа от 1 до N, причем на всё про всё нужно O(N) времени. То есть - О(1) на число.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 11:31
    #40100414
Gennadiy Usov
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Имя пользователя1
прикольность известного мне прикольного решения в том,
что там по ходу пьесы мы узнаем сумму делителей для каждого числа от 1 до N,
причем на всё про всё нужно O(N) времени. То есть - О(1) на число.
Зачем давать ходу пьесе?
Ищется произведение простых чисел:2, 3, 5, 7, 11, и т.д.
До тех пор, пока это произведение будет меньше N.

Максимальным таким числом будет число М, M < N.

Вот и ответ на 22376429 с учётом 22376695 .
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 11:40
    #40100416
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Gennadiy Usov
Имя пользователя1
прикольность известного мне прикольного решения в том,
что там по ходу пьесы мы узнаем сумму делителей для каждого числа от 1 до N,
причем на всё про всё нужно O(N) времени. То есть - О(1) на число.
Зачем давать ходу пьесе?
Ищется произведение простых чисел:2, 3, 5, 7, 11, и т.д.
До тех пор, пока это произведение будет меньше N.

Максимальным таким числом будет число М, M < N.

Вот и ответ на 22376429 с учётом 22376695 .

Не сработает. Например N = 2048 = 2 11 , сумма получается 4094
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 11:59
    #40100423
Gennadiy Usov
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Dima T
Не сработает. Например N = 2048 = 2 11 , сумма получается 4094
Если
N = 2*3* 5* 7 *11 = 2310
то сумма всех делителей равна 6026:
(1, N, по 1, по 2, по 3, по 4)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 12:00
    #40100424
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Gennadiy Usov
Dima T
Не сработает. Например N = 2048 = 2 11 , сумма получается 4094
Если
N = 2*3* 5* 7 *11 = 2310
то сумма всех делителей равна 6026:
(1, N, по 1, по 2, по 3, по 4)

По условию N любое, так почему бы не 2048 ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 12:34
    #40100430
Gennadiy Usov
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Dima T
Gennadiy Usov
пропущено...
Если
N = 2*3* 5* 7 *11 = 2310
то сумма всех делителей равна 6026:
(1, N, по 1, по 2, по 3, по 4)

По условию N любое, так почему бы не 2048 ?
Согласен, для 2048 лучше 2-ки.
А для 2400?

Получается 2 решения или больше?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 12:37
    #40100432
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Gennadiy Usov
Dima T
пропущено...

По условию N любое, так почему бы не 2048 ?
Согласен, для 2048 лучше 2-ки.
А для 2400?

Получается 2 решения или больше?

Не знаю, просто привел пример что это 22376801 неверное решение.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 12:38
    #40100433
Gennadiy Usov
Gennadiy Usov
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
А для троек - N = 2187 будет 3277.
Тоже решение!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 14:16
    #40100459
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
ИМХО не уверен, но такое решение просится: раскладываем N на простые множители и то число у которого простых множителей больше - будет иметь большую итоговую сумму. Если простых множителей одинаково, то берем то, где сумма простых множителей больше которое больше.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 14:21
    #40100464
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Имя пользователя1

прикольность известного мне прикольного решения в том, что там по ходу пьесы мы узнаем сумму делителей для каждого числа от 1 до N, причем на всё про всё нужно O(N) времени. То есть - О(1) на число.

Давай сюда своё "прикольное" решение. Посмотрим на его прикольность.

Но может так оказаться что факторизация о которой мы говорим - всё равно серебрянная пуля.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 14:53
    #40100470
Никанор Кузьмич
Никанор Кузьмич
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Утверждение автора:
Имя пользователя1
прикольность известного мне прикольного решения в том, что там по ходу пьесы мы узнаем сумму делителей для каждого числа от 1 до N, причем на всё про всё нужно O(N) времени. То есть - О(1) на число.


Gennadiy Usov
Ищется произведение простых чисел:2, 3, 5, 7, 11, и т.д.
Поиск простых от 1 до N - это больше, чем O(N).

Dima T
такое решение просится: раскладываем N на простые множители
Это тоже больше, чем O(N).

mayton
Давай сюда своё "прикольное" решение. Посмотрим на его прикольность.
Присоединяюсь к вопросу. Что-то не верится в существование возможности оценки суммы множителей за "О(1) на число".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 16:25
    #40100503
kealon(Ruslan)
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
Имя пользователя1,

вроде как задача на динамическое программирование, т.е. ответ должен следовать из знания решений для меньших аргументов
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.09.2021, 20:33
    #40100542
Имя пользователя1
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пазл с прикольным решением
kealon(Ruslan),

это само собой.
дельная мысль.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пазл с прикольным решением / 25 сообщений из 47, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]