1018. Двоичная яблоня (ДП, структура данных) [acm.timus.ru]

[Условие]

Основная идея:
В ходе решения встают следующие вопросы:
1) Как хранить дерево?
2) Как его получить, используя входные данные?
3) Что дальше делать с этим деревом?

1002. Телефонные номера (ДП) [acm.timus.ru]

[Условие]

Основная идея:
Всю задачу можно разделить на 3 этапа:
1) Хранение данных
Каждое слово из словаря необходимо хранить как в цифровом, так и в буквенном варианте. Для слова “our” цифровое представление будет равно “087”. При этом необходимо иметь связь между между обоими представлениями для получения ответа. Один из вариантов хранения такого представления можно описать в виде структуры, а весь словарь в виде массива элементов таких структур:

1. struct word
2. {
3.   string str;      // буквенное представление
4.   string digits;   // цифровое представление
5. };
6. vector<word> dict; // словарь

Задачи с acm.timus.ru

1002. Телефонные номера (ДП)
1015. Найдите различия! (сортировка,STL, пространственное воображение)
1017. Лестницы (комбинаторика, ДА)
1018. Двоичная яблоня (ДП, структура данных)
1019. Перекрашивание прямой (сортировка, структура данных)
1022. Генеалогическое дерево (топологическая сортировка)

НОД (Наибольший общий делитель)

Английский эквивалент этого понятия GCD(Greatest Common Divisor). Краткую теорию по этому вопросу читаем на Wikipedia. Сразу отметим, что наиболее эффективный и распространенный алгоритм нахождения НОДа является алгоритм Евклида, о котором очень популярно изложено сайте MAXimal. Обратите внимание на доказательство корректности алгоритма.
После ознакомления с этой статьей предлагаю перейти к практической части.
По мотивам введения первой главы книги Левитина “Алгоритмы. Введение в разработку и анализ” рассмотрим несколько реализаций нахождения НОДа.
1. Рекурсивная реализация алгоритма Евклида:

1. int gcd_Euclid(int a, int b)
2. {
3.   if (b == 0)
4.     return a;
5.   return gcd_Euclid(b,a%b);
6. }

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

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

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