OberonCore
https://forum.oberoncore.ru/

Об одной задаче из ЕГЭ
https://forum.oberoncore.ru/viewtopic.php?f=7&t=476		 Страница 1 из 10
Автор:  Trurl [ Среда, 23 Май, 2007 10:52 ]
Заголовок сообщения:  Об одной задаче из ЕГЭ
Задача.
Опишите на русском языке или одном из языков программирования алгоритм подсчета числа элементов равных максимальному в числовом массиве из 30 элементов.

Код:
  CONST N=30;
  VAR  a: ARRAY N OF INTEGER; 
   Num,Max, i: INTEGER;

PROCEDURE OtvetNa1ball;
 BEGIN
    Max:=a[0];
    FOR i := 0 TO N - 1 DO Max := MAX(a[i],Max) END;
    Num:=0;
    FOR i := 0 TO N - 1 DO
      IF a[i]=Max THEN INC(Num) END
    END
  END OtvetNa1ball;

PROCEDURE OtvetNa2balla;
 BEGIN
    Max:=a[0];
    Num:=1;
    FOR i := 1 TO N - 1 DO
      IF a[i]>Max THEN
        Max:=a[i]; Num:=1
      ELSIF a[i]=Max THEN
        Num:=Num+1;
      END
    END
  END OtvetNa2balla;

Как вы думаете, стоит ли такая экономия на спичках оценки в два раза выше? Я понимаю, если бы речь шла о файлах.
Автор:  Александр Ильин [ Среда, 23 Май, 2007 11:05 ]
Заголовок сообщения: 
Первый вариант даст ответ на единицу меньше правильного в случае, если a[0] = Max(a). Кроме того, в первом цикле там лишняя итерация.

В целом, если речь идет об олимпиадном или учебном задании, то дело в принципе, в алгоритме. А второй алгоритм более оптимален. А насчет того, оценивать ли его в два раза выше, то это от задач конкурса зависит и от общего числа подобных заданий.
Автор:  Trurl [ Среда, 23 Май, 2007 12:14 ]
Заголовок сообщения: 
Александр Ильин писал(а):
Первый вариант даст ответ на единицу меньше правильного в случае, если a[0] = Max(a). Кроме того, в первом цикле там лишняя итерация.

Ну, это просто я ошибся, когда с бейсика переписывал. Исправил, дабы не смущать.

Цитата:
В целом, если речь идет об олимпиадном или учебном задании, то дело в принципе, в алгоритме. А второй алгоритм более оптимален.

Да, вот как раз о принципе. Второй алгоритм быстрее, можно даже выгадать несколько микросекунд, но зато он хуже структуирован.
Автор:  Сергей Оборотов [ Среда, 23 Май, 2007 12:57 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
Trurl писал(а):
Я понимаю, если бы речь шла о файлах.
И совершенно напрасно, по-моему. Весь массив умещается в одном буфере в 128 байт.
Автор:  Александр Ильин [ Среда, 23 Май, 2007 13:22 ]
Заголовок сообщения: 
Trurl писал(а):
Да, вот как раз о принципе. Второй алгоритм быстрее, можно даже выгадать несколько микросекунд, но зато он хуже структуирован.

Хм. О структуре я не подумал... Инерция мышления, однако.

Нужно определиться с критериями оценки, а это извечная проблема контролирующего образования (наряду с вопросом "а судьи кто?"). Как известно, множество правильно решающих задачу алгоритмов различается по потреблению ресурсов разного типа. Одни используют больше процессорного времени, другие больше памяти или еще чего-нибудь. Вы добавляете критерий структурированности алгоритма, что предполагает еще один ресурс - время на понимание алгоритма, например, с целью его поддержки и сопровождения. Это, конечно, очень важная характеристика, поскольку большую часть времени программист не пишет, а читает. (Однако, замечу в скобках, что эта характеристика является и наиболее субъективной.)

Подбор критериев напрямую зависит от образовательных задач. Чему мы хотим научить, какие алгоритмы изготавливать: быстрые, компактные или понятные. Как отразить этот трехкоординатный вектор на одномерную балльную шкалу? Только явно сформулировав в задании приоритетное направление. При такой формулировке задачи, которая была приведена, и при условии, что контекст ЕГЭ не устанавливает общего идеологического направления ("русский программист пишет быстрые программы!" и т. п.), оба варианта заслуживают одинаковой положительной оценки, поскольку поставленную задачу - выполняют. И вопрос о том, про файлы речь или про числа в памяти, соответственно, ни при чем: четко написано, что "числовой массив".

С контекстом ЕГЭ я не знаком, но если брать отдельно взятое задание, то в нем нехватает критериев для оценки, отличной от "0 баллов за невыполненное задание либо 1 балл за выполенное".
Автор:  Сергей Оборотов [ Среда, 23 Май, 2007 13:48 ]
Заголовок сообщения: 
Александр Ильин писал(а):
Хм. О структуре я не подумал... Инерция мышления, однако.
Вы как будто оправдываетесь. Не стоит. Тем более критерии оценки были ясно заданы ею самой.
Автор:  dk [ Среда, 23 Май, 2007 17:06 ]
Заголовок сообщения: 
Сильно ли вы удивитесь, если узнаете, что по критериям оценки задачи C2 любое из двух предложенных решений должно оцениваться в 2 балла?

В задаче C2 любой верно работающий алгоритм оценивается максимальным баллов вне зависимости от его эффективности.
Автор:  Александр Ильин [ Среда, 23 Май, 2007 17:25 ]
Заголовок сообщения: 
dk писал(а):
Сильно ли вы удивитесь, если узнаете, что по критериям оценки задачи C2 любое из двух предложенных решений должно оцениваться в 2 балла?

Я спрошу: "А что такое "С2"?"
Автор:  dk [ Среда, 23 Май, 2007 17:37 ]
Заголовок сообщения: 
С2 - это вторая задача части "C" ЕГЭ по информатике.
Приведенная задача как раз задача такого типа, которые даются на позиции C2.
Автор:  Trurl [ Четверг, 24 Май, 2007 08:37 ]
Заголовок сообщения: 
dk писал(а):
Сильно ли вы удивитесь, если узнаете, что по критериям оценки задачи C2 любое из двух предложенных решений должно оцениваться в 2 балла?

Сильно удивлятся можно только в первые дни знакомства с нашей системой образования. :)
Но, как выяснилось, эта задача - С3 из позапрошлогоднего демо варианта и там черным по белому написано

Цитата:
Предложен правильный алгоритм, использующий однократный проход по массиву 2

Составлен правильный алгоритм, не допускающий немедленного обобщения на произвольное число элементов или требующий неоднократного прохода по массиву 1

Задание выполнено неверно 0
Автор:  dk [ Четверг, 24 Май, 2007 08:46 ]
Заголовок сообщения: 
Это демо-версия 2005 года.
С 2006 года поменялась спецификация работы, в частности, задачи такого рода оказались на позиции C2. И критерии оценки по этой задаче изменены так, что оптимальности алгоритма не требуется.
Посмотрите демо-версии 2006 и 2007 годов.
Автор:  Info21 [ Суббота, 26 Май, 2007 11:36 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
Trurl писал(а):
Задача. ...
Как вы думаете, стоит ли такая экономия на спичках оценки в два раза выше? Я понимаю, если бы речь шла о файлах.


Я бы в данном случае вообще вдвое снижал оценку за оптимизацию, т.к. ухудшается понимабельность.

Я и сортировку массива вставками теперь объясняю с двумя циклами: найти место (тупой лин. поиск), вставить (тупой полный проход). Ну и потом как необязательную оптимизацию -- два цикла в один.

"Преждевременная оптимизация -- корень большинства проблем." (С) 197*
Автор:  Сергей Губанов [ Понедельник, 28 Май, 2007 13:53 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
info21 писал(а):
...найти место (тупой лин. поиск)...


Я на собеседовании первым делом прошу написать линейный поиск элемента в массиве. Ещё ни один человек не написал его через WHILE. Далее спрашиваю знакомы ли они с работами Дейкстры? Про монитор Хоара спрашивать уже побаиваюсь, даже его быстрой сортировки не знают. Нужно нанять на работу несколько человек, уже два месяца ищем - ни одного подходящего нет. Однажды даже приходил бывший препод - якобы информатику читал в политехе, выяснилось что не информатику, а язык Си, оказался ещё бестолковее иных претендентов.
Автор:  Info21 [ Понедельник, 28 Май, 2007 16:40 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
Сергей Губанов писал(а):
info21 писал(а):
...найти место (тупой лин. поиск)...


Я на собеседовании первым делом прошу написать линейный поиск элемента в массиве. Ещё ни один человек не написал его через WHILE. ...


У меня точно такой же опыт: за исключением студентов, пришедших слушать курс во второй раз, никто не пишет. И в СИБИНТЕКе (был случай в филиале) никто не написал...
Автор:  Vlad [ Понедельник, 28 Май, 2007 18:59 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
info21 писал(а):
У меня точно такой же опыт: за исключением студентов, пришедших слушать курс во второй раз, никто не пишет. И в СИБИНТЕКе (был случай в филиале) никто не написал...


И о чем это говорит? Интересно, ибо я тоже никогда не пишу линейный поиск в последовательности через WHILE.
Автор:  batyrmastyr [ Понедельник, 28 Май, 2007 21:54 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
Vlad писал(а):
И о чем это говорит? Интересно, ибо я тоже никогда не пишу линейный поиск в последовательности через WHILE.

О вредных привычках, наверное. Поиск через WHILE проще, универсальнее и, частенько, быстрее. :)
Автор:  Сергей Губанов [ Вторник, 29 Май, 2007 10:37 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
Vlad писал(а):
И о чем это говорит? Интересно, ибо я тоже никогда не пишу линейный поиск в последовательности через WHILE.


Это говорит о том, что испытуемый - типичный "народный ополченец" от программирования.

Один мой коллега даже прикалывался по этому поводу. Спрашивает: "Вы английский знаете?".
Испытуемый: "Да, очень хорошо".
Коллега: "А вот и не знаете!
Foreach: 'для' каждого элемента выполнить.
While: 'пока' не нашли - искать.
Поскольку, Вы для поиска использовали foreach, а не while, значит английского Вы не знаете!".

Вот запись алгоритма линейного поиска элемента f в массиве a:
Код:
i := 0;
WHILE (i < LEN(a)) & ~(a[i] = f) DO INC(i) END;
IF i < LEN(a) THEN
  нашли элемент f, его позиция равна i
ELSE
  не нашли
END

и не надо ничего мудрить.
Автор:  Vlad [ Вторник, 29 Май, 2007 11:36 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
batyrmastyr писал(а):
О вредных привычках, наверное. Поиск через WHILE проще, универсальнее и, частенько, быстрее. :)


В каком языке? На каком компиляторе? Ужас какой - для "пареподавателя" иметь настолько узкий кругозор и требовать от "обучаемых" того же. И при этом кричать о глубоком кризисе нашего образования.
Автор:  Vlad [ Вторник, 29 Май, 2007 11:47 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
Сергей Губанов писал(а):
Это говорит о том, что испытуемый - типичный "народный ополченец" от программирования.


А обоснования?

Сергей Губанов писал(а):
Поскольку, Вы для поиска использовали foreach, а не while, значит английского Вы не знаете!".


Бред полный. У вас там филологией занимаются или программированием?

Сергей Губанов писал(а):
Вот запись алгоритма линейного поиска элемента f в массиве a:
Код:
i := 0;
WHILE (i < LEN(a)) & ~(a[i] = f) DO INC(i) END;
IF i < LEN(a) THEN
  нашли элемент f, его позиция равна i
ELSE
  не нашли
END

и не надо ничего мудрить.


Ужас какой. Сравни с таким кодом:
Код:
i = find(a, f);


Где find - аналог стандартной функции практически любого уважающего себя современного ЯВУ (оберон, к несчастью, такую функцию реализовать не позволяет). И знание этой функции надо требовать на собеседовании, чтобы потом не продираться через горы велосипедных циклов, навернутых только ради поиска элемента в последовательности.
Автор:  PGR [ Вторник, 29 Май, 2007 12:06 ]
Заголовок сообщения:  Re: Об одной задаче из ЕГЭ
Vlad писал(а):
Где find - аналог стандартной функции практически любого уважающего себя современного ЯВУ (оберон, к несчастью, такую функцию реализовать не позволяет). И знание этой функции надо требовать на собеседовании, чтобы потом не продираться через горы велосипедных циклов, навернутых только ради поиска элемента в последовательности.

Простейший цикл
Код:
WHILE (i < LEN(a)) & ~(a[i] = f) DO INC(i) END;
заменять функцией???
Страница 1 из 10 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/