Начало
Учебные задачи
Занятие № 1
Давайте для начала рассмотрим один простой пример. Решим следующую задачу. Во входном файле input.txt записаны два натуральных числа, каждое из которых не превышает 32000. Числа во входном файле разделяются пробелами и (или) символами перевода строки. В выходной файл output.txt вывести сумму этих двух чисел.
Кажется, что это даже не задача, и любой знакомый с программированием школьник с легкостью может написать ее решение:
var a,b,c:integer;
begin
assign(input,'input.txt'); {Связываем ввод с файлом input.txt}
reset(input); {Открываем файл для чтения}
read(a,b); {Считываем данные из файла}
close(input); {Закрываем файл}
c:=a+b; {Решаем задачу :-) }
assign(output,'output.txt'); {Связываем вывод с файлом output.txt}
rewrite(output); {Открываем файл для записи}
writeln(c); {Записываем данные в файл}
close(output); {Закрываем файл}
end.
#include <stdio.h>
int main()
{
short a,b,c;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d",&a,&b);
c=a+b;
printf("%d\n",c);
return 0;
}
Кажется, что все правильно.
На всякий случай запустим нашу программу, чтобы еще раз убедиться, что она работает правильно.
Посылаем ее на проверку, и получаем неожиданный результат – несколько тестов прошло, но на некоторых тестах происходит ошибка во время исполнения (или неверный ответ – это зависит от ключей компилятора).
Давайте еще раз внимательно прочитаем условие, и особо остановимся на ограничениях: Числа натуральные, не превышающие 32000. У нас для хранения чисел заведены переменные типа integer, диапазон значений переменных этого типа – от –32768 до 32767, так что кажется, что тут все правильно.
Однако, условию удовлетворяет тест, в котором оба числа равны 32000. Конечно, они входят в тип integer, чего нельзя сказать об их сумме! Меняя в нашей программе тип integer на тип longint получаем уже действительно полное решение задачи (замечание: оказывается, если сделать тип переменной c – longint, а a и b оставить типа integer, то программа работать все равно не будет – подумайте почему).
Таким образом, первый совет, который хочется дать – всегда внимательно читать условие и обращать самое пристальное внимание на ограничения, при этом учитывать не только ограничения на входные данные, но и задумываться о том, какие ограничения накладываются на выходные данные и промежуточные результаты.
Ограничения важны еще с одной точки зрения. Задумайтесь – а сколько действий выполнит ваша программа в самом худшем случае. Успеют ли все эти действия выполниться за время, отведенное на работу программы на одном тесте? Если ответ заведомо отрицательный – попытайтесь как-то улучшить свой алгоритм, или даже придумать новый.
Обязательно перед сдачей решения проверьте его самостоятельно, введя тесты, приведенные в условиях задач, и придумав свои.
Хорошо бы протестировать задачу не только на маленьких тестах, но и на максимальных, удовлетворяющих ограничениям. Это позволит найти ошибки, приводящие к переполнению типов, выходу индекса за границы массива.
Эти же тесты дают возможность проверить, укладывается ли ваше решение в ограничения по времени, указанные в условии задачи.
Если вы осуществили все такие проверки, а задача все равно не проходит какие-то тесты, подумайте, быть может, вы не учли какой-то из частных случаев задачи.
Если вы послали решение, которое у вас работает, а оно не прошло ни одного теста, проверьте, правильно ли в вашем решении называются входной и выходной файлы, соблюдены ли форматы входных и выходных данных, заканчивает ли ваша программа свою работу (например, не ждет ли она нажатия клавиши "Enter")?
Если вы не знаете, как решать задачу при указанных ограничениях или в общем случае, но ваша программа работает в каких-то частных случаях, обязательно пошлите ее на проверку – быть может несколько тестов она все-таки пройдет, а любой положительный результат – это лучше, чем ничего.
