Книги по олимпиадному программированию
На днях со мной связался экс-тренер казахстанской сборной IOI Алдияр Даулеткулов и предложил выложить свои книги на http://olympiads.kz, что я, собственно, и сделал: Олимпиады по информатике, Основы программирования на языке Паскаль.
От себя добавлю, что “Олимпиады по информатике” – первая книга по олимпиадному программированию, которую я прочитал. В ней достаточно понятно разобраны многие задачи, и, хотя в настоящее время они являются достаточно простыми, книга с успехом может использоваться теми, кто только начинает этот долгий и тернистый путь. Про вторую книгу ничего сказать не могу, так как с Паскалем у нас довольно натянутые отношения
P.S. Вчера решал одну задачку и написал такую вот функцию:
bool sign(int x) {
if (x) return x / abs(x);
return 0;
}
Долго не мог понять, почему у меня не работала программа. Проблема оказалась в том, что даже в этом простом коде есть два бага (хотя мне был важен только один) – попробуйте их найти
| Print article | This entry was posted by arti on September 23, 2008 at 10:49 pm, and is filed under Олимпиады. Follow any responses to this post through RSS 2.0. Вы можете оставить комментарий или трэкбэк с вашего сайта. |
Русский
English
1 год назад
Предполагалась signum function?
1) bool int
2) x = -2^31
Здесь, кажется, такой случай, когда тупо if сделать и нагляднее и быстрее.
1 год назад
точно
но почему-то захотелось сделать именно так.
1 год назад
Я бы тоже не заметил bool, если б не подсказка.
Вот еще вариант:
int sign(int x) {return x >> 31 | !!x;}
1 год назад
теперь буду писать только так
1 год назад
1. Тип возвращаемого значения bool
2. abs(INT_MIN) == INT_MIN
1 год назад
быстро вы все понаходили – а я вот два дня не додумался вообще на эту функцию посмотреть
1 год назад
Опечатку с bool я тоже не сразу заметил. Увидел только потому, что было сказано про два бага
1 год назад
На 1 минуту опоздал
1 год назад
Я, я был первым!
1 год назад
Еще проще проверку на знак сделать выражением:
if (x&0×80000000)
{
//Действие по отрицательному x
}
Достоинства: экономятся драгоценные машинные такты ввиду отсутствия прыжка в функцию, отсутствуют лишние битовые инверсии, тем более отсутствуют математические вычисления. На выходе компилятора имеем одну машинную инструкцию, которая выполняется за четверть такта (по классификации Pentium III). Огромная экономия процессорного времени, что в вашем случае неоспоримый плюс.
Недостатки: отсутствие наглядности кода, прямая зависимость от размера используемой переменной (0×80000000 для 32-х битной, 0×8000 для 16-ти и 0×80 для 8-ми битной)