ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пазл с прикольным решением
25 сообщений из 47, страница 1 из 2
  1  все
Пазл с прикольным решением
    #40100249
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Дано натуральное N. Выяснить, у какого целого числа из отрезка 1...N будет наибольшая сумма делителей.

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

Про память не сказано, но чем меньше тем лучше. Насчет размерности чисел не заморачиваемся, полагаем что любое число поместится в некую "числовую переменную", размер и все операции с которой - О(1)
...
Рейтинг: 0 / 0
27.09.2021, 16:00
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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:22
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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:43
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100260
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А.... у меня голова забита факторизацией. Сорян. В руке молоток - и вижу кругом гвозди.
...
Рейтинг: 0 / 0
27.09.2021, 16:46
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100309
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
В любом случае, при N=256 оно и будет ответом. А также при любых N= K^M. Очевидно, что и при простом N. Также очевидно, что ни один делитель N не будет ответом.
Для остальных N на глаз и не скажу. Можно попробовать многочлены Sum(x10^y).
...
Рейтинг: 0 / 0
27.09.2021, 19:08
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100326
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Как всегда поспешил выше. Простое N ответом не всегда будет.))
...
Рейтинг: 0 / 0
27.09.2021, 20:22
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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:42
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100334
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Если я правильно понял, то все возможные делители надо складывать, т.е. для степеней двойки ответ будет N*2-2
...
Рейтинг: 0 / 0
27.09.2021, 20:45
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100349
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
на всякий: для каждого числа подразумевается сумма всех его делителей. То есть, к примеру, число 12: делители: 2, 3, 4, 6, 12, их сумма равна 27
4 для 16 дважды учитывается?
...
Рейтинг: 0 / 0
27.09.2021, 22:58
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100350
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Корявенько поставлена задача. Надо добавить что делать с составными делителями.
...
Рейтинг: 0 / 0
27.09.2021, 23:06
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100352
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,

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

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

прикольность известного мне прикольного решения в том, что там по ходу пьесы мы узнаем сумму делителей для каждого числа от 1 до N, причем на всё про всё нужно O(N) времени. То есть - О(1) на число.
...
Рейтинг: 0 / 0
28.09.2021, 10:24
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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:31
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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:40
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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, 11:59
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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:00
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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:34
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100432
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy Usov
Dima T
пропущено...

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

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

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

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

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

Но может так оказаться что факторизация о которой мы говорим - всё равно серебрянная пуля.
...
Рейтинг: 0 / 0
28.09.2021, 14:21
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #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, 14:53
| Ответить | Цитировать | Написать  
Пазл с прикольным решением
    #40100503
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Имя пользователя1,

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

это само собой.
дельная мысль.
...
Рейтинг: 0 / 0
28.09.2021, 20:33
| Ответить | Цитировать | Написать  
25 сообщений из 47, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пазл с прикольным решением
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru             Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=2&tid=1339628]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 30ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 58ms
get tp. blocked users:
 2ms
others: 239ms
total:  374ms
созд. / загр.: 374ms
x
x
Закрыть


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