A322. Максимальная сумма делителей

Задача. Найти натуральное число с максимальной суммой делителей на заданном промежутке.

Входные данные:
— [latex]n[/latex] — промежуток чисел(от 1 до [latex]n[/latex]);

Выходные данные:
— [latex]max[/latex] _ [latex]sum[/latex] — максимальная сумма делителей числа на этом промежутке;
— [latex]max[/latex] _ [latex]number[/latex] — натуральное число с этой суммой;

Тесты:

[latex]n[/latex] [latex]max[/latex] _ [latex]number[/latex] [latex]max[/latex] _ [latex]sum[/latex]
100 96 252
8743 8400 30752
23000 22680 87120

Код на языке с++:

Решение задачи:
Для нахождения суммы делителей используется функция [latex]sum[/latex] _ [latex]dividers[/latex], которая в созданном цикле сначала находит все делители числа, а после суммирует их, присваивая значение переменной [latex]sum[/latex]. Создав в главной функции [latex]main[/latex] еще один цикл со счетчиком от 1 до [latex]n[/latex], подставляю в предыдущую функцию [latex]sum[/latex] _ [latex]dividers[/latex] все натуральные числа на выбранном промежутке. C помощью свободных переменных [latex]max[/latex] _ [latex]sum[/latex] и [latex]max[/latex] _ [latex]number[/latex] нахожу максимальное значение сумм и соответствующее ему натуральное число.

Код программы: Ideone
Условия задачи(стр.134): 322

6 thoughts on “A322. Максимальная сумма делителей

  1. — Я просил выполнять обобщение. Т.е. в данном случае нужно искать не до 10000, а до произвольного заданного во входном потоке числа.
    — Для каждого шага цикла Вы трижды вызываете весьма трудоёмкую функцию подсчета делителей. Зачем? Можно ведь запомнить результат.
    — Можете устно вычислить результат этого участка Вашего кода — «max(n,(n-1))»? Что же больше n или n-1? Не подсказывайте, дайте подумать… Может n? И сама проверка в этой строке лишняя. Всё нужно делать в предыдущем условном операторе — нашли «новый максимум», запомнили и его и число.
    — Больше тестов.

  2. — Вы ошибочно указали исходные данные в качестве результата. Т.е. value это вход, а не выход. Кроме того value не самое удачное название для задания максимального значения целочисленного интервала. Все уже так привыкли обозначать его через n (от 1 до n), что выбор другого имени нуждается в обосновании.
    — Что означает имя функции sum_NOD? По смыслу кода она вычисляет сумму делителей числа.
    — Посмотрите на этот участок кода:

    Здесь дважды вызывается функция sum_NOD от одного и того же аргумента. Зачем повторять дважды весьма трудоемкие вычисления? Нужно просто запомнить в некоторой переменной результат при первом вызове и потом обратиться к запомненному значению.
    — Вы пишите «цикл с счетчиком». Для таких ситуаций есть другая форма союза «с» — «со». Т.е. «цикл со счётчиком». Мелочь, конечно.

  3. Пишу это в отдельном комментарии т.к. это не замечания к вашему решению, а только предложение-идея.
    Для поиска делителей одного числа отлично подходит написанная Вами функция. Но Вам нужно находить делители всех чисел от 1 до n. Т.е. можно завести массив из n элементов для хранения сумм делителей каждого из чисел. Изначально во всех (кроме первого) будет храниться n+1, т.к. каждое число делится на 1 и само на себя. Далее каждый второй счетчик увеличиваем на 2, каждый третий на 3 и т.д. Останется найти максимум в массиве.
    Подумайте, будет ли этот подход менее трудоёмким чем Ваш. Если да, то оцените насколько.

    • Для оценки начнем с подсчета вычислительной сложности моего кода. Так как в функции [latex]main[/latex] я использую два вложенных цикла, сложность которых [latex]O(\sqrt{n})[/latex] и соответственно [latex]O(n)[/latex], имеем общую сложность следующую: [latex]O(\sqrt{n})\cdot O(n)=O(n\sqrt{n})[/latex].
      Рассмотрим Ваш вариант. При заполнении массива сложность составляет всего [latex]O(n)[/latex]. Во время сортировки при использовании библиотечной функции [latex]sort()[/latex] — [latex]O(n\cdot log(n))[/latex]. Так как эти функции будут вызваны последовательно имеем следующую ситуацию [latex]O(n+n\cdot log(n))=O(n\cdot log(n))[/latex]. Естественно, т.к логарифм медленная функция, можно сделать вывод, что Ваш вариант решения данной задачи является более оптимальным.

Добавить комментарий