Личный кабинет

ЕГЭ по информатике (2)

Продолжаем тему "ЕГЭ по информатике"
Александр Чернов ( Пользователь )
Цитата (Михалкович Станислав, 30.01.2010, 11:37) <{POST_SNAPBACK}>
...


Вы подаете на вход случайный тест, на котором, очевидно, неэффективное решение работает примерно также, как эффективное. Подавайте на вход наихудший тест.
Станислав Михалкович ( Пользователь )
Цитата (info21, 30.01.2010, 12:21) <{POST_SNAPBACK}>
Ссылки не открываются -- менять браузер (iRider) точно не буду. Потому что он удобней и быстрее всех мозилл.

Про BB - это абсолютно правильное решение - сделать кнопку запуска программы - это увеличит число пользователей. И все же - хотелось бы увидеть код на BB - там, кстати, может, действительно чище получится, чем приведенный ЕГЭ-вариант. И - я не поверю, что в стандартных библиотеках Оберона нет никакой сортировки.

Про iRider - я вот сейчас скачал последнюю версию - всё открывается и работает. А у Вас какая версия?
Александр Чернов ( Пользователь )
Цитата (Михалкович Станислав, 30.01.2010, 12:30) <{POST_SNAPBACK}>
...


Да и еще, давайте в обеих программах будем использовать либо INC, либо +1. Похоже Ваш оптимизатор не умеет нормально оптимизировать a := a + 1
Станислав Михалкович ( Пользователь )
Цитата (cher, 30.01.2010, 12:26) <{POST_SNAPBACK}>
Вынужден констатировать, что Вы 1) либо не понимаете понятие временной сложности алгоритма, 2) либо сознательно пытаетесь спасти свое решение.

Вы подаете на вход случайный тест, на котором, очевидно, неэффективное решение работает примерно также, как эффективное. Подавайте на вход наихудший тест.

Просто мы с Вами расходимся в понимании эффективного решения. И в том, как надо оценивать школьников.

Я прошу еще раз заметить, что я считаю решение ЕГЭ асимптотически более эффективным, чем первое решение Андрея. Я с этим не спорю. То есть, я не спасаю (кстати, не свое) решение. Но я не вижу причин снижать школьнику за такое решение балл. Оно - хорошее и не такое уж неэффективное. И мне обидно, если кто-то из проверяющих снизит за это решение балл.

Кстати, если уж на то пошло, давайте тогда оговоримся, что мы сравниваем асимптотическую сложность алгоритмов после ввода данных (!) - тогда решение Андрея, несомненно, хуже. Но беда этой задачи в том, что поскольку нельзя все данные считывать вначале в память, мы выполняем часть работы во время считывания данных, и это входит в алгоритм.

Еще я, честно говоря, потрясен, что Вы так запросто пробросили то, что видно глазами - ВРЕМЯ. Неэффективное решение работает быстрее эффективного, сколько бы Вы ни запускали тест. Я предлагаю посчитать вероятность того, что случайно будет сгенерирован наихудший тест - она будет ничтожно малой, и вдобавок в этом случае "плохое" решение будет хуже "хорошего" всего в 26 раз. А в остальных случаях - в 2 раза быстрее.

И еще, я не согласен, что надо оценивать эффективность алгоритма по самому худшему тесту. В первую очередь оценивается эффективность алгоритма в среднем. Эффективность в худшем случае - рассматривается - да, но требовать это от школьников - это уже слишком. Это - удел спецкурса "Алгоритмы и анализ сложности".
Андрей Сидоров ( Пользователь )
Цитата (cher, 29.01.2010, 22:27) <{POST_SNAPBACK}>
Если сомневаетесь, то проверьте. Установите себе Turbo Pascal и запустите тестовые программы.


Проверил. Переменные в Turbo Pascal 6.6j инициализируются по умолчанию нулями, а не случайными числами. Я прав. 
Станислав Михалкович ( Пользователь )
Цитата (cher, 30.01.2010, 12:33) <{POST_SNAPBACK}>
Да и еще, давайте в обеих программах будем использовать либо INC, либо +1. Похоже Ваш оптимизатор не умеет нормально оптимизировать a := a + 1

Это делает виртуальная машина если хочет - в .NET код оптимизируется в основном JIT-компилятором. Давайте не говорить про оптимизацию, я ведь говорю в принципе - понятно, что в разных системах ввиду оптимизаций и встраивания функций программа будет работать с разной скоростью. В PascalABC.NET, например, самым быстрым будет написать i +=1. Но это все - частности.
Федор Ткачев ( Пользователь )
Цитата (Михалкович Станислав, 30.01.2010, 12:30) <{POST_SNAPBACK}>
Про iRider - я вот сейчас скачал последнюю версию - всё открывается и работает. А у Вас какая версия?

У меня последняя.

Цитата
сожалению, Ваш браузер не поддерживает элементы, необходимые для корректной работы WDE.

Используйте следующие браузеры:

Mozilla Firefox (от 2.0)
Internet Explorer (от 7)
Google Chrome (от 2)
Safari (от 3.1)


Приносим извинения за доставленные неудобства.

Андрей Сидоров ( Пользователь )
Цитата (Михалкович Станислав, 30.01.2010, 12:47) <{POST_SNAPBACK}>
 мне обидно, если кто-то из проверяющих снизит за это решение балл.

Зависит от проверяющих теперь... Попадется стародуб какой-нибудь, и все: "переменные не инициализированы; сортировки нету, а задача  - на знание сортировки" и т.д. и т.п.

Думаю, вы правы в том, что иногда практичней пожертвовать балл за неэффективность - лучше неэффективное решение, чем никакого. По-крайней мере, запомнить и воспроизвести такое решение школьнику намного легче, чем книжное.


Федор Ткачев ( Пользователь )
Цитата (Андрей Сидоров, 30.01.2010, 18:16) <{POST_SNAPBACK}>
Зависит от проверяющих теперь... Попадется стародуб какой-нибудь, и все: "переменные не инициализированы; сортировки нету, а задача  - на знание сортировки" и т.д. и т.п.

К сожалению, прогрессивных дуроломов, не приученых к элементарной гигиене вроде инициализации переменных, гораздо больше, чем стародубов, требующих как минимум оговаривать автоматическую инициализацию в комментарии.

Учитывая производимые горы дрянного софта, лично я поддержал бы в комиссии стародуба, столь живописно описанного Андреем Николаевичем.
Потому что дуроломов и так слишком много.
Андрей Сидоров ( Пользователь )
Федор Васильевич, если не секрет, вы лично подготовкой скольких школьников к будущему ЕГЭ занимаетесь?

footer logo © Образ–Центр, 2019. 12+