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


The Presentation inside:

Slide 0

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


Slide 1

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


Slide 2

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


Slide 3

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


Slide 4

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


Slide 5

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


Slide 6

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


Slide 7

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


Slide 8

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


Slide 9

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


Slide 10

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


Slide 11

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


Slide 12

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


Slide 13

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


Slide 14

Получение следующей перестановки 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]


Slide 15

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


Slide 16

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


Slide 17

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


Slide 18

Спасибо за внимание!


×

HTML:





Ссылка: