Методика обучения решению задач повышенной сложности

Задача №4 районной олимпиады по информатике
Сумма двух чисел.
Заданы три числа a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось число c.
Формат входных данных 0
Формат выходных данных Если перестановка возможна, вывести слово YES, в противном случае – слово NO. При положительном ответе вывести число x, получаемое перестановкой цифр числа а, и число у, получаемое перестановкой цифр числа b. Числа не должны содержать ведущих нулей.
Примеры входных и выходных данных

Решение задачи
Текст программы (мой алгоритм)
Решение задачи (мой алгоритм)
Ссылки не работают. Для получения текста программы и файлов обращайтесь на e-mail школы
[email protected]
Графические интерпретации работы алгоритма:
Тест 1
Тест 2
Тест 3
Тест 4
Тест 5
Все решения задачи
Ссылки не работают. Для получения текста программы и файлов обращайтесь на e-mail школы
[email protected]

Комбинаторные алгоритмы

Из предисловия к главе 2 книги С.М. Окулова «Программирование в алгоритмах»
Одной из главных целей изучения комбинаторных алгоритмов, помимо традиционных, заключается в том, чтобы учащиеся осознали суть «отношения порядка» на некотором множестве объектов.

Классические задачи комбинаторики
Перестановки
Размещения
Сочетания
Размещения с повторениями (строки)
Перестановки с повторениями
Сочетания с повторениями
Разбиения
Подмножества
без повторений

Перестановки
Сколькими способами можно переставить N различных предметов, расположенных на N различных местах.
Примеры:
1. Сколькими способами можно переставить три монеты 1, 2, 5 рублей, расположенных соответственно на трех местах с номерами 1, 2, 3? Ответ: 6.
2. Сколькими способами можно переставить буквы в слове «эскиз»? Ответ: 120.
3. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга? Ответ: 40320.

Размещения
Сколькими способами можно выбрать и разместить по М различным местам М из N различных предметов?
Примеры:
1. Сколькими способами можно выбрать и разместить на двух местах 1, 2 две из трех монет 1, 2, 5 рублей? Ответ: 6.
2. Сколько трехбуквенных словосочетаний можно составить из букв слова «эскиз»? Ответ: 60.
3. Партия состоит из 25 человек. Требуется выбрать председателя, заместителя, секретаря и казначея. Сколькими способами можно это сделать, если каждый член партии может занимать лишь один пост? Ответ: 303600.

Сочетания (выборки)
Сколькими способами можно выбрать М из N различных предметов?
Примеры:
1. Сколькими способами можно выбрать две из трех монет 1, 2, 5 рублей? Ответ: 3.
2. Сколькими способами можно выбрать три из пяти букв слова «эскиз»? Ответ: 10.
3. Сколькими способами можно поставить на шахматной доске 8 ладей (условие о том, что ладьи не могут бить друг друга, снимается)? Ответ: 4328284968.

Перестановки
Перестановкой конечного множества называется упорядоченная последовательность всех его элементов, в которой каждый элемент встречается ровно один раз.

Задача. Перечислить или сгенерировать все перестановки для заданного значения N.
Данная задача требует введения отношения порядка на множестве перестановок.

Перестановка А следующая по порядку после S
На рисунке Р – позиция, в которой встретился элемент нарушающий порядок возрастания справа в перестановке S. R – часть справа от Р («хвост» перестановки), отсортирована по возрастанию слева на право в перестановке A.

Лексикографический порядок
Все перестановки
последовательности 1 2 3 4
в лексикографическом порядке

Получение следующей перестановки

Получение следующей перестановки
1. Пусть P – массив, содержащий перестановку.
2. Находим первое i с конца массива P такое, что P[ i ] < P[ i + 1 ]. Если такого i найти не удалось, то массив P упорядочен по убыванию – алгоритм работать не будет.
3. Находим первое j с конца массива такое, что i < j и P[ i ] < P[ j ]
4. Меняем местами P[ i ] и P[ j ]
5. Транспонируем кусок массива P – от P[ i + 1 ] до P[N]

Решение задачи на основе классического алгоритма генерации перестановок
в лексикографическом порядке.
Текст программы
Решение задачи
Ссылки не работают. Для получения текста программы и файлов обращайтесь на e-mail школы
[email protected]

Перевод числа а в массив цифр
* * *
am[0]:=0;
while a>0 do begin inc(am[0]);
am[am[0]]:=a mod 10;
a:=a div 10;
end;
* * *

Получение числа, соответствующего
полученной перестановке
* * *
a:=0;
for k:=1 to am[0] do a:=10*a+am[p[k]];
* * *