'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 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]


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


×

HTML:





Ссылка: