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

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

Продолжаем тему "ЕГЭ по информатике"
Евгений Высочин ( Пользователь )
Цитата (Михалкович Станислав, 27.01.2010, 23:06) <{POST_SNAPBACK}>
Может, просто написать, что программа составлена на Delphi?


Какая разница на чем прога написана ?

Цитата (Андрей Сидоров, 28.01.2010, 12:47) <{POST_SNAPBACK}>
Вопрос по задаче С4 вар. 8 из сборника Якушкин-Лещинер-Кириенко.

На вход программе подается последовательность строчных английских букв. Ввод этих символов заканчивается точкой (другие символы, отличные от "." и букв "a"…"z", во входных данных отсутствуют).
Напечатать буквы, встречающиеся во входной последовательности, в порядке увеличения частоты их встречаемости.
Каждая буква при этом должны быть распечатана один раз.
Если какие-то буквы встречаются одинаковое число раз, то они выводятся по алфавиту.

Например, пусть на вход подаются следующие символы:
baobaba.
В данном случае программа должна вывести
oab


Будет ли снижена оценка за такое решение и если да, то почему?

Код
var
    i,num:integer;
    c:char;
    a: array['a'..'z'] of integer;  
      
begin
    read(c);
    while c<>'.' do
    begin
       inc(a[c]);
       inc(num);
       read(c);
    end;
          
    for i:=1 to num do
      for c:='a' to 'z' do
        if a[c]=i then write(c)
end.



А это уже красяво! УВАЖАЮ! Еще бы на С++ написал бы этот пример, цены бы тебе не было!
Андрей Сидоров ( Пользователь )
Цитата (Евгений Высочин, 28.01.2010, 13:37) <{POST_SNAPBACK}>
Какая разница на чем прога написана ?


В дельфи вроде строки длинее.


Цитата (Евгений Высочин, 28.01.2010, 13:37) <{POST_SNAPBACK}>
Еще бы на С++ написал бы этот пример, цены бы тебе не было!


Могу на Руби :)  

  puts gets.scan(/\w/).uniq.sort_by{|i|[$_.count(i),i]}.join

А вот, кстати, решение из книги.

Неужели так лучше?
Федор Ткачев ( Пользователь )
Цитата (Андрей Сидоров, 28.01.2010, 13:31) <{POST_SNAPBACK}>
1) Согласен, но является ли это достаточным формальным основанием для снижения балла? 


Считаю, является.
Андрей Сидоров ( Пользователь )
Цитата (info21, 28.01.2010, 16:53) <{POST_SNAPBACK}>
Считаю, является.


Согласно каким критериям оценивания? Я не припоминаю таких в документации по проверке работ. К тому же ряде случаев (даже в примере из задачи) такой алгоритм будет быстрее сортировки.  
Федор Ткачев ( Пользователь )
Цитата (Андрей Сидоров, 28.01.2010, 17:14) <{POST_SNAPBACK}>
Согласно каким критериям оценивания? Я не припоминаю таких в документации по проверке работ. К тому же ряде случаев (даже в примере из задачи) такой алгоритм будет быстрее сортировки.  

"Считаю".

Преждевременная оптимизация -- источник большинства проблем при разработке программ.

Сортировка ни при чем.
Андрей Сидоров ( Пользователь )
Цитата (info21, 29.01.2010, 00:12) <{POST_SNAPBACK}>
"Считаю".

Преждевременная оптимизация -- источник большинства проблем при разработке программ.

Сортировка ни при чем.

Можете пояснить? Я вообще не понял, что вы сказали.

На всякий случай, я вообще-то говорю не о разработке программ, а о сдаче ЕГЭ. Единственная проблема, которая меня интересует при разработке подобной программы - это снизят за нее балл или нет, и на основании каких формальных признаков, указанных в официальных документах.    
Станислав Михалкович ( Пользователь )
Для меня - загадка, за что снижают в тех или иных случаях. Думаю, элемент субъективизма - огромный. Уже здесь в этом топике предлагали снизить за то, что статические переменные инициализированы неявно. Думаю, таких документов - нет, а если есть, то там много глупости.

Вот мое мнение.

За неявную инициализацию нулями снижать нельзя.

Приведенное "правильное и эффективное решение" - уродское. Вот с такими знаниями приходят к нам в ВУЗ крутые дети из школ. Но - так не программируют в любом приличном проекте. Конкретно:
1. Сортировку оформляют в процедуру, и уж по крайней мере пишут процедуру Swap. Если и сортировать, то массив записей, а не два массива зараз. В данном случае второй массив просто лишний.
2. Волшебные константы типа 25 или 26 - никто не позволит писать - студент, такое написавший, получит незачет.
3. Ord©-Ord('a') - уродская конструкция, повторяющаяся многократно. Так не пишут или оформляют это в функцию. А еще лучше - индексируют не с нуля и символами - как у Вас.
4. Авторы боятся использовать Inc.
5. Если на то пошло, то приведенный алгоритм неэффективен при малом количестве букв, уж не говоря про малую длину строки символов.

Ссылки на малое время на ЕГЭ я не принимаю - дети научаются писать уродски, в старых-престарых средах, по новым-преновым книгам по ЕГЭ.

Общее ощущение - данная программа напоминает программы на Turbo Pascal 15-летней давности, когда это считалось круто.

Честно говоря, мне ваше решение на Руби нравится больше всего.

Про приведенный алгоритм на Паскале - можно немножко пооптимизировать:
for i:=1 to num do - здесь можно не до num, а искать максимальное среди a[c] и до него. Можно сократить вычисления в 26 раз если повезет. А ежели это число окажется еще и меньше 256, я бы прошелся по массиву a[c] еще бы разик и занес все эти значения в множество с тем чтобы пропускать последний внутренний цикл если во множестве нет такого значения.

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

А детей заставляют мыслить сразу оптимально, пренебрегая кучей других критериев хорошей программы. Преждевременная оптимизация - зло. Безальтернативные схемы решения - тоже.
ЛЮДМИЛА РАК ( Пользователь )
Уважаемы коллеги, поделитесь, если есть реальными вариантами ЕГЭ по информатике за прошлые годы. Зараннее спасибо.
Андрей Сидоров ( Пользователь )
 
Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
...


Спасибо за развернутый ответ! Тем более, что здесь, как я посмотрю , никто особо не горит желанием обсуждать конкретику.

Конечно, программу можно оптимизировать и дальше. Просто такое решение наиболее лаконично, и его проще и быстрее объяснить ученику.

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

Насчет древних оболочек - в наших школах еще весьма распространен QBasic, вот это действительно жесть! Кстати, отдельное спасибо лично вам за PascalABC.NET - для Паскаля пользуюсь только им.

Относительно документов: в можно найти достаточно много "указаний по оцениванию" для конкретных задач. Понятие "эффективности" там достаточно узкое и формальное, и практически не совпадает с тем, что считают эффективным разного рода специалисты по программированию (которые, однако, мнение свое тут время от времени высказывают).  

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

Александр Чернов ( Пользователь )
Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
Для меня - загадка, за что снижают в тех или иных случаях. Думаю, элемент субъективизма - огромный. Уже здесь в этом топике предлагали снизить за то, что статические переменные инициализированы неявно. Думаю, таких документов - нет, а если есть, то там много глупости.

Вот мое мнение.

За неявную инициализацию нулями снижать нельзя.


Использование неинициализированных переменных - очень неприятная и очень частая для начинающих ошибка. Разные версии паскаля обрабатывают глобальные (статические) переменные по-разному. В некоторых версиях глобальные переменные не инициализируются нулем. Поэтому за отсутствие инициализации (а не за неявную инициализацию) можно и нужно балл снижать.

В других языках (C, C++, да и все прочие), где глобальные (статические) переменные инициализируются нулем, конечно, требовать явной инициализации не нужно.

Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
Приведенное "правильное и эффективное решение" - уродское. Вот с такими знаниями приходят к нам в ВУЗ крутые дети из школ. Но - так не программируют в любом приличном проекте. Конкретно:


Не стоит делать столь обобщающих утверждений.

В данной программе заметно желание обойтись минимумом выразительных средств языка. Более того, программа написана так, что она переписывается один-в-один на любой другой аналогичный язык программирования, будь то C, C++, Basic, Modula...
Поэтому не используются процедуры, не используются структуры (записи), массивы индексируются от нуля. И с учетом этого программа написана вполне хорошо. Возможно, это решение было переписано на паскаль с си.

Или Вы всерьез предполагаете, что авторы данного решения настолько не знают именно паскаля?

Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
1. Сортировку оформляют в процедуру, и уж по крайней мере пишут процедуру Swap. Если и сортировать, то массив записей, а не два массива зараз. В данном случае второй массив просто лишний.


Процедуры не используются - см. выше. Насчет "по крайней мере" - очень странное утверждение. :)
Увы, но с сортировкой массива Вы не правы. Если сортируемые данные достаточно большие, "в любом приличном проекте" будут сортироваться либо индексы, либо указатели. Ожидать от учебной задачи использования структур или, тем более, указателей, как-то черезчур...

Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
2. Волшебные константы типа 25 или 26 - никто не позволит писать - студент, такое написавший, получит незачет.


Вот здесь я согласен. Действительно лучше использовать константы.

Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
3. Ord©-Ord('a') - уродская конструкция, повторяющаяся многократно. Так не пишут или оформляют это в функцию. А еще лучше - индексируют не с нуля и символами - как у Вас.


Конструкция такова, поскольку паскаль не позволяет просто вычитать символы один из другого. В функцию это оформлять вообще бессмысленно, так как по сути это одно вычитание. Вы предлагаете любое вычитание оформлять в отдельную функцию?

Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
4. Авторы боятся использовать Inc.


См. выше.

Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
5. Если на то пошло, то приведенный алгоритм неэффективен при малом количестве букв, уж не говоря про малую длину строки символов.


Хм... Это что-то новое :) Оценка эффективности алгоритма при малых значениях входных данных? :)

Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
Про приведенный алгоритм на Паскале - можно немножко пооптимизировать:
for i:=1 to num do - здесь можно не до num, а искать максимальное среди a[c] и до него. Можно сократить вычисления в 26 раз если повезет. А ежели это число окажется еще и меньше 256, я бы прошелся по массиву a[c] еще бы разик и занес все эти значения в множество с тем чтобы пропускать последний внутренний цикл если во множестве нет такого значения.

...

А детей заставляют мыслить сразу оптимально, пренебрегая кучей других критериев хорошей программы. Преждевременная оптимизация - зло. Безальтернативные схемы решения - тоже.


Зачем пытаться оптимизировать по мелочам неоптимальное решение? Вы в точности и занимаетесь преждевременной оптимизацией...

Цитата (Михалкович Станислав, 29.01.2010, 00:56) <{POST_SNAPBACK}>
По поводу "единственно верного и оптимального" решения в этой задаче - я считаю, что его нет. В зависимости от того, будет ли количество символов большим или маленьким, оптимальное решение задачи будет сильно разным. Про существенно лучшую читаемость вашего решения я даже не говорю. Если бы я решал, то, наверное, использовал бы алгоритм сортировки вставками - по крайней мере, буквы с нулевой повторяемостью отсеклись бы сам собой.


Единственно верного решения не бывает никогда. Но предложенное в качестве альтернативы решение было заведомо неоптимальным. Это решение имеет сложность порядка 2*N и никакие ваши мелкие оптимизации не понизят его сложность. В то время, как предложенное авторами решение имеет сложность порядка N. N - длина входа, то есть количество символов, поданных на вход программе.

А как сортировать массив из 26 элементов - вообще дело десятое. Хоть пузырьком, хоть вставками, хоть быстрой сортировкой...

Цитата (Андрей Сидоров, 29.01.2010, 12:03) <{POST_SNAPBACK}>
Конечно, программу можно оптимизировать и дальше. Просто такое решение наиболее лаконично, и его проще и быстрее объяснить ученику.


Из того, что решение объяснять проще и быстрее, не следуюет, что оно правильное с точки зрения критериев C4.

Например, наверное, проще всего вычислять числа Фибоначчи через рекурсию вида f(n - 1) + f(n - 2). Нужно ли объяснять, почему такое решение не эффективное?

Цитата (Андрей Сидоров, 29.01.2010, 12:03) <{POST_SNAPBACK}>
Относительно решения из книги - все такие решения явно ориентированы на Турбо Паскаль, там даже Swap нету. Причем я сомневаюсь, что к этой книге имеет прямое отношение хотя бы один из предполагаемых авторов - полагаю, это просто старые варианты ЕГЭ из архива. Кто писал решения - для меня загадка. Может, Кириенко знает.


Решения по необходимости ориентированы на некоторый минимальный язык, являющийся подмножеством всех паскалей, которые могут использоваться в школах. Надо объяснять почему?

Все авторы программ, приведенных в сборниках, более чем компетентные люди.

Цитата (Андрей Сидоров, 29.01.2010, 12:03) <{POST_SNAPBACK}>
Относительно документов: в можно найти достаточно много "указаний по оцениванию" для конкретных задач. Понятие "эффективности" там достаточно узкое и формальное, и практически не совпадает с тем, что считают эффективным разного рода специалисты по программированию (которые, однако, мнение свое тут время от времени высказывают).  


Приведите, пожалуйста, примеры несовпадений? Если просто, то временная эффективность работы алгоритма - это функция времени работы алгоритма от размера входных данных. Обычно рассматривается скорость роста функции при больших размерах входных данных. Все специалисты по программированию понимают это именно так.

Цитата (Андрей Сидоров, 29.01.2010, 12:03) <{POST_SNAPBACK}>
Практически любую программу (особенно школьного уровня) можно усовершенствовать в плане эффективности. По-моему, это не повод для снижения балла. 


В задаче C4 требуется определенная эффективность. Программы, не удовлетворяющие этим требованиям, не могут получить полный балл.

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