Задачи по программированию

[Ktulkhu_old]

Уважаемые ЕнЕтовцы-программисты!

Не могли бы вы помочь маленькой девочке решить задачи для заочной олимпиады, а также (а вдруг?) попробовать научить ее решать эти (и другие) задачи по программированию? //да, этот ребенок программистом собрался становиться

Файл с задачами прилагается, первую я решила ^^

[Rowan]

Задачи по информатике, а не по программированию. Здесь логика и немного математики, ну и вконце еще немножко паскаля хотя это уже детали.

А решать таким сповобом задачи разве не противоречит правилам описанным вначале informatics_2012.PDF?

[Ktulkhu_old]

Ну, у меня пока что выхода другого нет..

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

[Lance]

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

[NortUS]

(заныло)

На выходных можно порешать будет... Вторая задача шикарная - люблю оптимизации

upd. Списался с ТС. Тему можно закрывать

[Daniel5555]

Задание 5. Рассмотрим текст романа Л. Н. Толстого «Анна Каренина» (следует использовать

электронную версию романа, находящуюся по адресу http://ejudge.ru/study/anna.txt).

Словоформой назовем последовательность латинских или русских букв. Словоформы

ограничиваются символами, не являющимися латинскими или русскими буквами. В

словоформах не различаются заглавные и строчные буквы и буквы е и ѐ. Например, Осел и

осѐл — это одна словоформа. Выпишите 10 наиболее часто встречающихся словоформ

длиной 4 буквы в порядке уменьшения частоты их появления и для каждой словоформы

укажите частоту ее появления. Словоформы должны быть выписаны строчными буквами, с

буквой ѐ, преобразованной к букве е. Если несколько словоформ имеют равную частоту

появления, они должны быть упорядочены по алфавиту (причем русские буквы идут раньше

Олимпиада школьников «Ломоносов», отборочный этап, информатика, 2011-2012 учебный год

латинских). Обоснуйте свой ответ и приложите исходные тексты (например, тексты

программ или электронные таблицы), использованные для получения ответа.

Мне кажется, здесь можно использовать адаптированный вариант словаря Ахо-Корасика, одну из простых имплементаций которого я написал не так давно: http://www.forum.evanotend.com/index.php?showtopic=7598&view=findpost&p=479033

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

Для топа-10 наиболее частовстречающихся слов можно сделать упорядоченный массив из 10 пар слово-частота и каждый раз сверять частоту последнего найденного слова с частотой наименее частого слова из этого массива (если этого слова нет в массиве, в противном случае надо проверить не превосходит ли его частота следующее более частое слово в топе), не забывая проверять так же приоритет по алфавиту, естественно.

Я не думаю, что это наиболее эффективное решение, но по крайней мере оно гарантирует поиск слов в словаре за O(n) время, а операцию проверки с массивом можно сделать равной O(1), операцию вставки слова в массив можно сделать в худшем случае равной O(11).

[NortUS]

Даниэль, Ахо-Корасик, равно как и Кнутт-Моррисон-Пратт и иные алгоритмы поиска подстроки нам нафиг не нужны.

Рассматриваем входной текст как поток символов. Пишем простейший конечный автомат, который выплевывает пословно (слово - это последовательность русских букв и знака "-", ограниченная слева и справа иными символами.

Если словоформа имеет 4 буквы, то приводим ее в нормальный вид и кладем в дерево. (Ибо ассоциативных массивов на паскале нет, а писать хэш мне как-то влооом)

Неясно только что такое частота - то ли имеется в виду частота среди всего текста (тогда она будет микроскопична), то ли среди словоформ длины 4.

Меня убило задание 2. С каких пор ксоры позволяют построить произвольную булеву функцию? Сколько себе помню для этого нужна операция и-не (или-не) или две операции (и/или, и/ксор)

[WaterMan]

Меня убило задание 2. С каких пор ксоры позволяют построить произвольную булеву функцию? Сколько себе помню для этого нужна операция и-не (или-не) или две операции (и/или, и/ксор)

Может, имеется ввиду алгебраическая нормальная форма?

x && y = x*y.

А x || y = x + (x+1)*y

-x = x+1

ПС: Я так... мимо проходил, задание не читал.

[Daniel5555]

NortUS

Даниэль, Ахо-Корасик, равно как и Кнутт-Моррисон- Пратт и иные алгоритмы поиска подстроки нам нафиг не нужны.

Рассматриваем входной текст как поток символов. Пишем простейший конечный автомат, который выплевывает пословно (слово - это последовательность русских букв и знака "-", ограниченная слева и справа иными символами.

Если словоформа имеет 4 буквы, то приводим ее в нормальный вид и кладем в дерево. (Ибо ассоциативных массивов на паскале нет, а писать хэш мне как-то влооом)

Можно поподробнее, что ты имеешь в виду? Какое именно дерево?

Если не ошибаюсь, то написание, скажем, AVL-дерева, гораздо более сложное в концептуальном плане, чем такого словаря и не дает никаких преимуществ, по-моему.

Ну а про поток символов-то это просто, конечно. Проверяем их на соответствие условиям и вставляем в словарь.

Хеши это, конечно, overkill в данной ситуации.

Неясно только что такое частота - то ли имеется в виду частота среди всего текста (тогда она будет микроскопична), то ли среди словоформ длины 4.

Я думаю, речь идет о том, чтобы сосчитать количество всех словоформ, которые есть в тексте. То есть в слове "микросхема" есть словоформы "микр", "икро", "крос", "росх", и так далее. Надо найти наиболее часто встречающиеся.

Меня убило задание 2. С каких пор ксоры позволяют построить произвольную булеву функцию? Сколько себе помню для этого нужна операция и-не (или-не) или две операции (и/или, и/ксор)

Я вообще не понял это задание. Я не знаю что такое "вектор значений" и как это переводится на испанский.

[NortUS]

То есть в слове "микросхема" есть словоформы "микр", "икро", "крос", "росх", и так далее.

Словоформой назовем последовательность латинских или русских букв. Словоформы

ограничиваются символами, не являющимися латинскими или русскими буквами.

Словоформа - это слово в "обыденном" понимании. Хотя например кое-кто это 2 словоформы

Хэш - 30 метров памяти и поиск за O(1)

Двоичное лексикографическое дерево - 40Кб памяти и поиск за О(log)

Мне как-то второе симпатичнее