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

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

3A.Разложение на простые множители
[pfactor] Типовая соптимизированная реализация
Оптимизация заключается в пересчете верхней границы цикла(корень квадратный из N) при переходе к новому делителю.
3B.Перестановки(2)
[permut2] Рекурсивная реализация с подсчетом элементов
Реализация основана на разборе этой задачи из книги Меньшикова. Первоначально подсчитываем количество вхождений символов из первоначальной перестановки. Затем на i-ое место текущей перестановки ставим ближайший в лексикографическом порядке символ, счетчик которого имеет ненулевое значение, и декрементируем счетчик на единицу.
[permut2] Идентично [permut] next_permutation
Важный факт того, что генерация алгоритмом next_permutation не зависит от того есть ли дублирующие символы во входном наборе или нет. Общий вывод: любая корректная реализация задачи 3B пройдет на задаче 2B.

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. }