Отправлено: 12.12.20 13:09. Заголовок: Время выполнения задачи №25

Коллеги, которые оказывают помощь Полякову К.Ю в разработке задач, предлагаю не создавать больших интервалов исходных данных.
1. Я не думаю, что во всей стране на егэ будут мощные ПК.
2. Когда время ожидания результата будет более минуты, даже используя round(sqrt(n)+1) ) для ускорения, могут быть аппеляции, что потрачены лишние минуты, которых не хватило для решения других задач.
3. Если посмотреть Демо 2021, то разработчики в 25 задаче создали интервал [174457; 174505] . Всего 48 чисел.
4. Даже если создать интервалы в задачах 20000 обрабатываются практически мгновенно. Думаю можно подобрать в условиях задач такие диапазоны, когда ответ появится на экране в течении 30 секунд максимум.
5. Ведь цель на егэ проверить не быстродействие компьтера, а умениие найти верное решение.
6. Конечно, можете возразить: нужно применять более эффективные алгоритмы. Но даже в простых задачах иногда это не спасает.

 Отправлено: 12.12.20 14:00. Заголовок: Вот пример задачи: О..

Вот пример задачи:
Определите количество простых чисел в диапазоне [2; 20000].
Используя стандартный код - 12с;
Используя перебор нечетных - 3 ;
Используя n**0.5 - 1 с;

Увеличиваем диапазон до 50 000.. Получается 113, 22 и 3 с соответственно.
Но в списке задач есть задача №78 - 80.
там числа от 200 000. Первые два алгоритма использовать нельзя по времени. Третий считает 31с (для 200 000)
Для условия 3577000 даже третий алгоритм не спасает

 Отправлено: 12.12.20 18:06. Заголовок: К примеру авторский ..

К примеру авторский код (Б.С.Михлин) http://egekp.unoforum.pro/?1-22-0-00000016-000-0-0-1605379770 на моем компьютере выполняется 61 секунду. При этом программа находит максимальное количество делителей - 80, на отрезке [586132; 586430].

Но стоит уменьшить значения интервала до [50132, 50430] и программа работает всего 5 секунд.

 Отправлено: 13.12.20 20:50. Заголовок: Ну заканчивая обсужд..

Ну заканчивая обсуждение темы с интервалами приведу пример: Стример Информатик Бу решая задачу Е. Джобса №97 https://www.youtube.com/watch?v=ikbkS3aSWtA
Время выполнения задачи на Паскале составило 11 секунд. (смотреть с 1ч 56 мин 35 с).
Я для чистоты эксперемента взял и один в один перебрал код на Python.

 import time 
 start = time.time() 
 for n in range(135790, 163228+1): 
     s = 0 # сумма  
     k = 0 # количество 
     for d in range(2, n//2+1): 
         if n%d == 0: 
             k += 1 
             s += d 
     if s > 460000: 
         print(k, s) 
 print(time.time() - start)

Время выполнения - 1183.68 c

У меня процессор Core i7 - 2.4 Ghz ОЗУ - 12Гб

 Отправлено: 13.12.20 21:00. Заголовок: nikson пишет: Время ..

nikson пишет:

цитата:

Время выполнения - 1183.68 c У меня процессор Core i7 - 2.4 Ghz ОЗУ - 12Гб

Неудачный пример. Если сделать перебор до sqrt(n), время около 2 с на i3 / 4Гб.

 Отправлено: 15.12.20 00:36. Заголовок: Поляков пишет: Неуд..

Поляков пишет:

цитата:

Неудачный пример. Если сделать перебор до sqrt(n), время около 2 с на i3 / 4Гб.

Мне интересно было сравнить один и тот же код у стриммера на Паскале и на Питоне

 Отправлено: 14.12.20 06:43. Заголовок: nikson пишет: предла..

nikson пишет:

цитата:

предлагаю не создавать больших интервалов исходных данных.

Андрей Николаевич, спасибо за замечание. Мысль дельная. Но, на мой взгляд, выполнение программы при оптимальном алгоритме в пределах 20-30 секунд на среднем компьютере вполне допустимо. Заодно алгоритмы подучим, рекурсию будем заменять динамическим программированием, использовать перебор до корня и т.п.