Задача. Найти натуральное число с максимальной суммой делителей на заданном промежутке.
Входные данные:
— [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 |
Код на языке C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <cmath> using namespace std; int sum_dividers(int n){ int sum=0; for(int i=1; i<sqrt(n); i++){ if((n%i)==0)sum+=i+(n/i); } int i=sqrt(n); if(i*i==n)sum+=i; return sum; } int main() { int n; cin>>n; int max_sum=0; int max_number=0; int j; for(j=1; j<=n; j++){ int s=sum_dividers(j); if(max_sum<s){ max_sum=s; max_number=j; } } cout<<max_number<<" "<<max_sum; return 0; } |
Код на языке Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { static int sum_dividers(int n){ int sum=0; for(int i=1; i<Math.sqrt(n); i++){ if((n%i)==0)sum+=i+(n/i); } double i=Math.round(Math.sqrt(n)); if(i*i==n)sum+=i; return sum; } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n=in.nextInt(); int max_sum=0; int max_number=0; int j; for(j=1; j<=n; j++){ int s=sum_dividers(j); if(max_sum<s){ max_sum=s; max_number=j; } } System.out.println(max_number+" "+max_sum); } } |
Решение задачи:
Для нахождения суммы делителей используется функция [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] нахожу максимальное значение сумм и соответствующее ему натуральное число.
Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 322
— Я просил выполнять обобщение. Т.е. в данном случае нужно искать не до 10000, а до произвольного заданного во входном потоке числа.
— Для каждого шага цикла Вы трижды вызываете весьма трудоёмкую функцию подсчета делителей. Зачем? Можно ведь запомнить результат.
— Можете устно вычислить результат этого участка Вашего кода — «max(n,(n-1))»? Что же больше n или n-1? Не подсказывайте, дайте подумать… Может n? И сама проверка в этой строке лишняя. Всё нужно делать в предыдущем условном операторе — нашли «новый максимум», запомнили и его и число.
— Больше тестов.
— Вы ошибочно указали исходные данные в качестве результата. Т.е. value это вход, а не выход. Кроме того value не самое удачное название для задания максимального значения целочисленного интервала. Все уже так привыкли обозначать его через n (от 1 до n), что выбор другого имени нуждается в обосновании.
— Что означает имя функции sum_NOD? По смыслу кода она вычисляет сумму делителей числа.
— Посмотрите на этот участок кода:
Здесь дважды вызывается функция sum_NOD от одного и того же аргумента. Зачем повторять дважды весьма трудоемкие вычисления? Нужно просто запомнить в некоторой переменной результат при первом вызове и потом обратиться к запомненному значению.
— Вы пишите «цикл с счетчиком». Для таких ситуаций есть другая форма союза «с» — «со». Т.е. «цикл со счётчиком». Мелочь, конечно.
Спасибо, исправила.
Пишу это в отдельном комментарии т.к. это не замечания к вашему решению, а только предложение-идея.
Для поиска делителей одного числа отлично подходит написанная Вами функция. Но Вам нужно находить делители всех чисел от 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]. Естественно, т.к логарифм медленная функция, можно сделать вывод, что Ваш вариант решения данной задачи является более оптимальным.
Ясно. Спасибо.
Только не используйте сравнительные степени прилагательного «оптимальный». Это как «максимальнее».