Дистанционные семинары




Скачать 0.69 Mb.
страница 1/7
Дата 31.08.2016
Размер 0.69 Mb.
  1   2   3   4   5   6   7

Дистанционные семинары


Оглавление

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

В настоящий момент доступны материалы следующих занятий:

Занятия 2004-05 учебного года


Занятие 0

Введение: требования к решениям олимпиадных задач, работа с файлами

Занятие 1

Знакомство с олимпиадными задачами.







Занятие 2

Метод динамического программирования.

Занятие 3

Метод динамического программирования (продолжение).

Занятие 4

Графы - введение.

Занятие 5

Графы: поиск кратчайшего пути, обход в ширину.

Занятие 6

Графы. Поиск кратчайшего пути. Алгоритм Дейкстры.

Занятие 7

Графы. Поиск кратчайшего пути. Алгоритм Флойда.

Занятие 8

Графы. Поиск кратчайшего пути. Алгоритм Форда-Беллмана.

Занятие 9

Графы. Каркас. Алгоритмы Прима и Краскала.

Занятия 2005-06 учебного года

Занятие 10

Длинная арифметика.

Занятие 11

Длинный корень.

Занятие 12

Рекурсия - 1.

Занятие 13

Графы. Обход в глубину.

Занятие 14

Рекурсия - 2. Перебор.

Занятие 0. Введение: требования к решениям олимпиадных задач, работа с файлами.

Если вам доводилось участвовать в олимпиадах по информатике и чтение входных данных из файла не вызывает у вас трудностей, то это занятие вы можете пропустить.



Что такое олимпиадная информатика?

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

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

Как проверяются решения и что из этого следует

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

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

Второе следствие из автоматической проверки - как правило, тесты по задаче составляются так, чтобы "покрыть" все возможные случаи. В том числе и максимальные. То есть если, например, в условии написано, что "во входном файле записано N чисел и N не превышает 1000", то тест на N=1000 (или очень близкое к нему число) почти наверняка будет. Так что если по условию что-топлохое возможно, оно будет.

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

Ваше решение должно читать входные данные из входного файла (его имя обычно указано в условии задачи) в описанном формате, решать задачу, и выводить результат в выходной файл (его имя тоже обычно указывается в условии). Программа должна всегда завершаться с кодом 0 (иначе тестирующая программа считает, что в ходе работы произошла ошибке) - то есть командой halt(0); или просто дохождением до конца на паскале, или return 0; - на C.

Рекомендуем также на эту тему почитать здесь.

Работа с файлами

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

Более подробно рассмотрим просто примеры программ на разных языках для решения такой задачи: из файла x.in вводятся два числа, и их сумму нужно вывести в файл x.out.


BASIC

C

PASCAL

open "x.in" for input as #1

open "x.out" for output as #2

input #1,a,b

print #2,a+b

close #1

close #2


#include
int main(void)

{

long a, b;



FILE *fin, *fout;
fin = fopen("x.in", "r");

fout = fopen("x.out", "w");

fscanf(fin, "%ld%ld", &a, &b);

fprintf(fout, "%ld", a + b);

fclose(fin);

fclose(fout);

return 0;

}


var a,b:longint;

var fi,fo:text;

begin

assign(fi,'x.in');



reset(fi);

assign(fo,'x.out');

rewrite(fo);

read(fi,a,b);

writeln(fo,a+b);

close(fi);

close(fo);

end.


Для программирующих на паскале. Если во входном файле записаны только числа, то для чтения лучше всего пользоваться командой read - она сама пропускает пробелы и переходы на новую строку. Таким образом, вам не важно, как идут эти числа - в одну строку, с переводами строки и т.д. Если же в файле записана текстовая информация - то (при чтении строк) команда read читает информацию из текущей строки (столько символов, сколько входит в строковую переменную), когда достигнут конец строки - возвращается пустая строка. А команда readln читает информацию из текущей строки и переходит на следующую (независимо от того, достигнут конец строки или нет).
  1   2   3   4   5   6   7


База данных защищена авторским правом ©infoeto.ru 2022
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница