Институт Естественных Наук и Экологии Карта сервера
Версия для печати
  Главная  События  О нас  Учебная часть  Студенты  Преподаватели  [Школа 1189]
   Учебные материалы   Текущий учебный год   [Курчатовская Олимпиада]
Курчатовская олимпиада по информатике.
2003-2004 год, заочный тур.

 Условия олимпиады: в олимпиаде может принимать участие любой школьник, обучающийся в 1-11 классе любой школы России. Олимпиада состоит из двух туров: заочного и очного. Очный тур будет проходить в конце января -- начале февраля 2004 года в Москве; отбор участников очного тура происходит по результатам заочного тура. Правила проведения заочного тура таковы: желающим предлагается две задачи, которые решаются дома, и не позднее 18 января решения отсылаются по электронной почте нам: olymp04@inse.ru. В присланных решениях должно содержаться следующее:

  1. откомпилированные исполняемые файлы программ, готовые к работе без дополнительных внешних библиотек.
  2. исходные текты программ с инструкциями по их компиляции, вплоть до указания типа операционной системы и конкретного компилятора. Если компилятор экзотический, то необходимо прислать ссылку на ресурс, с которого можно этот компилятор скачать.
  3. подробное описание алгоритма программ в форматах RTF, MS Word, TeX, PostScript, PDF или текстовом формате.
Требования к программам: программы могут быть написаны на любом из существующих процедурных языков программирования под любую свободно-распространяемую операционную систему для PC или под Miscrosoft Windows. Исходный текст программы должен быть хорошо отформатирован и откомментирован. Запрещается использовать внешние библиотеки, не входящие в состав поставки компилятора, а также библиотеки компилятора, предназначенные специально для решения поставленной перед вами задачи. Очень приветствуется переносимость написанной программы на другие компиляторы/платформы.

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

Задача 1. Числа Фибоначчи.
Как известно, последовательность чисел Фибоначчи Fn задается реккурентным соотношением
Fn=Fn-1+Fn-2,  F0=F1=1.

Требуется найти предел отношения Fn+1/Fn при n стремящемся к бесконечности с любой заданной наперед точностью, т.е. программе задается число верных десятичных знаков после запятой. Число правильных знаков может превосходить машинную точность, поэтому рекомендуется реализовать собственную библиотеку для работы с числами произвольной точности.

Задача 2. Распознавание образов.
Требуется написать программу, которая бы могла распознавать текст, нарисованный на картинке. Программе дается два графических файла: в первом из них находятся образы строчных букв английского алфавита, а во втором -- фраза, которую нужно распознать.

Графические файлы содержат чёрно-белую картинку и их формат таков: сначала идёт два 32-битных числа (двойных слова или числа типа long) -- высота и ширина картинки в пикселах. Последующие байты содержат информацию о белых и черных пикселах картинки; в каждом байте закодировано 8 пикселов: если некоторый бит равен единице, то соответствующий пиксел чёрный, если нулю, то белый. Таким образом, оставшаяся часть файла представляет собой поток битов, каждый из которых отвечает за соответственный пиксел рисунка. Картинка сохранена в файле построчно, если размер картинки не кратен восьми, то недостающие биты заполняются нулями. То есть двоичное число 10011100 соответствует последовательности цветов ЧББЧЧЧББ.

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

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

Архив с тремя файлами: font.dmp -- образец шрифта, text1.dmp -- "легкая" картинка для распознавания, text2.dmp -- "сложная" картинка для распознавания.

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

Удачи!
  Главная  События  О нас  Учебная часть  Студенты  Преподаватели  Школа 1189
INSE WWW team   Обновлено: