Тренировка #2 [Меньшиков]

[Условия задач]                   [Список тренировок]

2A. Простые числа
[primes2] Идентично [primes]
Первая задача [primes] проходит даже если перебирать в качестве делителей все числа в интервале [2,sqrt(n)]. Вторая же задача [primes2] проходит только, если перебирать нечетные делители.
[primes2] Precalc всех простых чисел
Предыдущую реализацию можно ускорить если в качестве делителей использовать не просто нечетные числа, а простые. Ускорение ~ в 2 раза.
[primes2] Решето Эратосфена
Решето Эратосфена упоминается в учебниках по математики за 6 класс. Сам подход несложен и вполне понятен. Реализация лаконична и не представляет сложности. Ко всему прочему это наиболее эффективный подход к нахождению простых чисел в заданном интервале. 

Тренировка #1 [Меньшиков]

[Условия задач]                    [Список тренировок]

1A. Простые числа
[primes]
Незамудренная реализация с одной фишкой: при нахождении делителей числа перебираем только нечетные из них. Как показала практика при этом достигается экономия по времени в 4 раза.
1B. Выражение
[expr]
Лаконичная рекурсивная реализация. Помимо этого решение имело место решение с генерацией всех комбинаций ‘+’ и ‘–’ для текущего набора чисел, которое требовало пересчета всего выражения целиком для каждой комбинации. Это решение не прошло по времени. К достоинству рекурсивного решения относится то, что перерасчет всего выражения не требуется. Нужно пересчитать только его изменившийся конец.

Олимпиадные задачи по программированию [Федор Меньшиков]

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

Тренировка #1   [08Mar10] 
Тренировка #2   [11Mar10]  
Тренировка #3   [18May10]
Тренировка #4   [20May10] 
Тренировка #5   [19Nov10] 
Тренировка #6   [23Nov10] 
Тренировка #7   [29Nov10]
Тренировка #8   [08Dec10]
Тренировка #9   [18Dec10] 
Тренировка #10  [24Dec10] 
Тренировка #11  [28Dec10] 
Тренировка #12  [06Jan11] 
Тренировка #13  [08Jan11]
Тренировка #14  [11Jan11] 
Тренировка #15  [17Jan11]

Все задачи тестируются в online-judge системе [informatics.mccme.ru], и если будет указано время работы любого из решений, то стоит считать, что эти данные были получены именно оттуда.

P.S: Исходники первых 4 тренировок могут давать ошибку компиляции на указанном сервере. Это связано с обновлением компилятора. Большую часть проблем может решить подключение заголовочного файла <cstdio>