На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



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


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

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 6 [только новые]





Сообщение: 98
ссылка на сообщение  Отправлено: 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 даже третий алгоритм не спасает

Спасибо: 0 
ПрофильЦитата Ответить



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


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

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

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 102
ссылка на сообщение  Отправлено: 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Гб

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




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


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

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

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



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


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

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


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

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 2231
ссылка на сообщение  Отправлено: 14.12.20 06:43. Заголовок: nikson пишет: предла..


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

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

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 1952
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет