Слайд 2Задача №4 районной олимпиады по информатике
Сумма двух чисел.
Заданы три числа a,
![Задача №4 районной олимпиады по информатике Сумма двух чисел. Заданы три числа](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-1.jpg)
Слайд 3Решение задачи
Текст программы (мой алгоритм)
Решение задачи (мой алгоритм)
Ссылки не работают. Для получения
![Решение задачи Текст программы (мой алгоритм) Решение задачи (мой алгоритм) Ссылки не](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-2.jpg)
текста программы и файлов обращайтесь на e-mail школы klin-50let-vlksm@yandex.ru
Графические интерпретации работы алгоритма:
Тест 1
Тест 2
Тест 3
Тест 4
Тест 5
Все решения задачи
Ссылки не работают. Для получения текста программы и файлов обращайтесь на e-mail школы klin-50let-vlksm@yandex.ru
Слайд 5Из предисловия к главе 2 книги С.М. Окулова «Программирование в алгоритмах»
Одной из
![Из предисловия к главе 2 книги С.М. Окулова «Программирование в алгоритмах» Одной](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-4.jpg)
главных целей изучения комбинаторных алгоритмов, помимо традиционных, заключается в том, чтобы учащиеся осознали суть «отношения порядка» на некотором множестве объектов.
Слайд 6Классические задачи комбинаторики
Перестановки
Размещения
Сочетания
Размещения с повторениями (строки)
Перестановки с повторениями
Сочетания с повторениями
Разбиения
Подмножества
без повторений
![Классические задачи комбинаторики Перестановки Размещения Сочетания Размещения с повторениями (строки) Перестановки с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-5.jpg)
Слайд 7Перестановки
Сколькими способами можно переставить N различных предметов, расположенных на N различных местах.
Примеры:
1.
![Перестановки Сколькими способами можно переставить N различных предметов, расположенных на N различных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-6.jpg)
Сколькими способами можно переставить три монеты 1, 2, 5 рублей, расположенных соответственно на трех местах с номерами 1, 2, 3? Ответ: 6.
2. Сколькими способами можно переставить буквы в слове «эскиз»? Ответ: 120.
3. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга? Ответ: 40320.
Слайд 8Размещения
Сколькими способами можно выбрать и разместить по М различным местам М из
![Размещения Сколькими способами можно выбрать и разместить по М различным местам М](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-7.jpg)
N различных предметов?
Примеры:
1. Сколькими способами можно выбрать и разместить на двух местах 1, 2 две из трех монет 1, 2, 5 рублей? Ответ: 6.
2. Сколько трехбуквенных словосочетаний можно составить из букв слова «эскиз»? Ответ: 60.
3. Партия состоит из 25 человек. Требуется выбрать председателя, заместителя, секретаря и казначея. Сколькими способами можно это сделать, если каждый член партии может занимать лишь один пост? Ответ: 303600.
Слайд 9Сочетания (выборки)
Сколькими способами можно выбрать М из N различных предметов?
Примеры:
1. Сколькими способами
![Сочетания (выборки) Сколькими способами можно выбрать М из N различных предметов? Примеры:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-8.jpg)
можно выбрать две из трех монет 1, 2, 5 рублей? Ответ: 3.
2. Сколькими способами можно выбрать три из пяти букв слова «эскиз»? Ответ: 10.
3. Сколькими способами можно поставить на шахматной доске 8 ладей (условие о том, что ладьи не могут бить друг друга, снимается)? Ответ: 4328284968.
Слайд 10Перестановки
Перестановкой конечного множества называется упорядоченная последовательность всех его элементов, в которой каждый
![Перестановки Перестановкой конечного множества называется упорядоченная последовательность всех его элементов, в которой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-9.jpg)
элемент встречается ровно один раз.
Слайд 11Задача. Перечислить или сгенерировать все перестановки для заданного значения N.
Данная задача требует
![Задача. Перечислить или сгенерировать все перестановки для заданного значения N. Данная задача](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-10.jpg)
введения отношения порядка на множестве перестановок.
Слайд 12Перестановка А следующая по порядку после S
На рисунке Р – позиция, в
![Перестановка А следующая по порядку после S На рисунке Р – позиция,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-11.jpg)
которой встретился элемент нарушающий порядок возрастания справа в перестановке S. R – часть справа от Р («хвост» перестановки), отсортирована по возрастанию слева на право в перестановке A.
Слайд 13Лексикографический порядок
Все перестановки
последовательности 1 2 3 4
в лексикографическом порядке
![Лексикографический порядок Все перестановки последовательности 1 2 3 4 в лексикографическом порядке](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-12.jpg)
Слайд 14Получение следующей перестановки
![Получение следующей перестановки](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-13.jpg)
Слайд 15Получение следующей перестановки
1. Пусть P – массив, содержащий перестановку.
2. Находим первое i
![Получение следующей перестановки 1. Пусть P – массив, содержащий перестановку. 2. Находим](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-14.jpg)
с конца массива 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Решение задачи на основе классического алгоритма генерации перестановок
в лексикографическом порядке.
Текст программы
Решение
![Решение задачи на основе классического алгоритма генерации перестановок в лексикографическом порядке. Текст](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-15.jpg)
задачи
Ссылки не работают. Для получения текста программы и файлов обращайтесь на e-mail школы klin-50let-vlksm@yandex.ru
Слайд 17Перевод числа а в массив цифр
* * *
am[0]:=0;
while a>0 do begin
![Перевод числа а в массив цифр * * * am[0]:=0; while a>0](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-16.jpg)
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]];
*
![Получение числа, соответствующего полученной перестановке * * * a:=0; for k:=1 to](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/439533/slide-17.jpg)
* *