Обычный алгоритм решения задачи выглядит так:
-
Придумать решение.
-
Написать код решения (или лучше части решения).
-
Тестировать решение на своем компьютере (или лучше потестировать часть решения)
3+) Если не работает, то дебажить, пока не заработает на всех тестах.
- Потестировать в тестирующей системе
4+) Если не работает, то придумывать тест, на котором не работает на своем компьютере. Если не находится - напишите стресс-тестирование
4++) Если все работает - внимательно читать код, добавить проверки в опасные места, перечитывать условие задачи, пока не найдете место, где либо вы не поняли задачу, либо ваша программа работает по-разному у вас и на сервере
4+++) Спросить преподавателя. Впрочем, этим методом можно и нужно пользоваться на более ранних стадиях, если вы только начинаете заниматься программированием
Здесь будут собраны советы о том, что делать в пунктах, начиная с 2.
Про первый пункт советов не будет :( Разве что совет, что придумать решение необходимо ДО того, как писать код.
Нужно для каждой переменной понимать
- чему она равна изначально
- как она меняется в какой части программы
- какие значения она может понимать, а какие нет.
Также и для каждого цикла нужно понимать
- какая будет первая итерация
- в какой момент он закончится
- сколько всего будет итераций
- нет ли где-то выхода за границы массива
- ставьте отступы
- ставьте пробелы вокруг арифметических знаков
- пишите понятные, и главное, мало похожие друг на друга названия переменных
- делите программу на логические части (про это подробнее следующий совет)
- Изучите подробности общепринятого кодстайл: TODO: ВСТАВИТЬ ССЫЛКУ НА КАКОЙ-НИБУДЬ КОДСТАЙЛ
Зачем?
- увидеть ошибку в структурированном коде гораздо проще, чем в каше
- чужому человеку и вам в будущем читать ваш непонятный код будет гораздо сложнее и неприятнее
- в промышленном программировании именно так все и пишут, полезно привыкнуть
Почему?
- в длинном сплошном коде легко не заметить ошибку
- отдельные функции очень просто тестировать
- если функция применяется несколько раз, то не нужно копировать код, что хорошо, так как при копировании кода можно скопировать ошибку, увидеть ее, исправить в одном месте, а в другом она
- в промышленном программировании именно так все и пишут, полезно привыкнуть
Вот пример, когда в программе без функций найти ошибку тяжело: (код Сережи Карпышева)
# Задача - найти точку пересечения двух прямых
#include <iostream>
#include <cmath>
using namespace std;
int main(){
long long x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
long long x3, y3, x4, y4;
cin >> x3 >> y3 >> x4 >> y4;
if((x1-x2)*(y4-y3)-(y1-y2)*(x4-x3)==0){
if((x1-x3)*(y2-y3)-(y1-y3)*(x2-x3)==0){
cout << 2;
return 0;
}
cout << 0;
return 0;
}
cout << 1 << ' ';
double a1 = y2 - y1;
double b1 = x1 - x2;
double c1 = x1*y2-y1*x2;
double a2 = y4 - y3;
double b2 = x3 - x4;
double c2 = x4*y3-y4*x3;
double x =(b1*c2-b2*c1)/(b2*a1-b1*a2);
cout << x << ' ';
cout << (c1-c2+a1*x-a2*x)/(b2-b1);
return 0;
}
Если ты - не Сережа Карпышев в октябре 2017 года, то этот код тебе отдебажить будет очень тяжело. Что здесь можно сделать для увеличения понятности кода:
- Структура Point вместо пары чисел x1, y1
- Cчитывание точки происходит 4 раза, удобно сделать для этого функцию или переопределить оператор >>
- Вектор разности двух точек считается где-то 6 раз, удобно сделать для этого функцию
- Векторное произведение двух векторо считается 6 раз, удобно сделать для этого функцию
- Проверку на параллельность двух векторов удобно вынести в отдельную функцию
- Координаты прямой a, b, c удобно вынести в отдельную функцию, считающую их по двум точкам
- Возможно даже структура Line вместо тройки чисел a, b, c
- Координаты пересечения двух прямых удобно считать через функцию от двух прямых, и работать там только с их координатами
Если все это сделать, то код станет понятным, в функции из одной строчки ошибиться очень тяжело. А еще каждую функцию можно легко потестировать отдельно, разобрать крайние случаи для каждой отдельной функции.
TODO описать процесс и виды дебага
Если у вас ошибка, особенно на C++ - это почти всегда выход за границы массива. Когда вы обращаетесь на C++ к элементу в массиве/векторе, которого не существует, ваша программа по стандарту C++ может сделать все, что угодно (хоть отформатировать диск, но вряд ли такое будет :D). Такая штука называется undefined behaviour.
Обычно при запросе к несуществующему элементу массива просто возвращается число из тех битов, которые лежат на том месте в памяти. У вас на компьютере там может быть 0, а на informatics - какое угодно другое число.
Поэтому:
- C++ чаще всего не видит эту ошибку и работает дальше.
- Ваша программа может работать по-разному у вас и на сервере.
Следите за индексами массивов - это то место, в котором вы должны досконально понимать, какие вы берете индексы и какого размера у вас массив, и всегда это проверять.
Нужно знать, что
- int содержит числа примерно от
$-2 * 10^9$ до$2 * 10^9$ - unsigned int содержит числа примерно от
$0$ до$4 * 10^9$ - long long содержит числа примерно от
$-9 * 10^18$ до$9 * 10^18$ - unsigned long long содержит числа примерно от
$0$ до$18 * 10^18$
И всегда проверять, что когда вы
- складываете
- умножаете
- вычитаете
числа, они все еще помещаются в выбранный вами тип.
Например, в задаче про быстрое возведение в степень, по условию гарантируется, что
НО! В ходе алгоритма вы иногда умножаете два числа. При этом, если вы все делаете правильно, вы работаете всегда только с ОСТАТКАМИ по модулю
Если вам дана задача и ограчение
Перечитайте условие, возможно, вы просто праивльно решили не ту задачу, которую надо сдать, а немножко другую. Возможно, вы забыли про какой-то важный случай или принципиально делаете что-то не то.
Но если вы достаточно много тестировали свою задачу, то вам может помочь стресс-тестирование
TODO