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

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

2 Задача 4 районной олимпиады по информатике Сумма двух чисел. Заданы три числа a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось число c. Формат входных данных 0

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

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

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

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

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

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

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

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

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

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

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

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

15 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]

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

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

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

19