Перестановки и факториалы. Способы вычисления факториала. Рекурсия

Вид урока: Бинарный (математика – информатика)

Место проведения: компьютерный класс .

Тема:

Алгебра: Перестановки и факториалы.

Информатика и ИКТ: Способы вычисления факториала. Рекурсия.

Оборудование: компьютерная сеть из 14 компьютеров, мультимедийный проектор, экран, маркерная доска.

Цели и задачи урока:

1. Повторить понятие перестановки и правила вычисления числа перестановок.
2. Повторить понятие факториала и рассмотреть рекурсивный способ его вычисления в среде программирования Турбо Паскаль.
3. Сравнить итерационный и рекурсивный способы вычисления факториала.
4. Рассмотреть типичные задачи и отработать способы их решения.
5. Отработать применение подпрограммы при программировании решения комбинаторной задачи.
6. Закрепить изученный материал, используя ИКТ.

Ход урока

I. Понятие факториала и перестановки.

Рассмотрим задачу, которая хорошо известна Вам как гуманитарному классу, хотя возможно Вы и не догадывались, что перед Вами именно задача (иллюстрируем презентацией).

“Проказница Мартышка, Осел,
Козел,
Да косолапый Мишка
Затеяли сыграть Квартет.
Вот пуще прежнего пошли у них разборы
И споры,
Кому и как сидеть.
А вы, друзья, как ни садитесь,
Всё в музыканты не годитесь".

И.А. Крылов”.

Итак, данной группе пришлось решать не такой уж простой вопрос: “Как расположить 4 объекта по 4 местам?”. Баснописец Крылов предложил только 2 способа рассадки участников квартета. А сколько их было на самом деле?

У нас 4 объекта:

1) Проказница мартышка;
2) Осёл;
3) Козёл;
4) Косолапый мишка.

И мест тоже 4: первое, второе, третье, четвертое.

Записываем решение на слайде.

Допустим, мартышка, как дама, выбирает место первой. Сколько у неё возможностей? Ведь она может занять любое из 4 мест, следовательно – 4.

Мишка по старшинству будет выбирать вторым, но уже только из 3 мест, так как одно занято, следовательно, у него 3 возможности.

Допустим, следующим будет козел, как имеющий неоспоримое преимущество в виде рогов. У него всего 2 возможности выбора, так как незанятых мест всего 2.

И последнему, ослу, остается только занять единственное свободное место, то есть его выбор – 1.

Напоминаю правило умножения для конечного числа испытаний: “Число всех возможных исходов независимого проведения n испытаний равно произведению количества исходов этих испытаний”.

Значит, число возможных вариантов рассадки членов квартета составит:

4•3•2•1=24.

И если бы баснописец Крылов описал все возможные способы, то мы получили бы не басню, а поэму. А как называется полученное нами произведение идущих подряд n натуральных чисел? Факториалом!

Определение.

Произведение идущих подряд n натуральных чисел обозначают n! и называют “эн факториал”.

n!=1•2•3• … • (n – 1)• n.

Фактически мы с Вами решали задачу о количестве перестановок некоторого n – элементного множества (в нашем случае 4-х элементного множества).

Теорема.

Число всех перестановок n – элементного множества равно n!.

II. Рассмотрим ещё несколько задач. (Тексты перед Вами)

№1. У мамы и папы – один сын. К ним в гости пришла другая семья – мама, папа и дочь. За круглым обеденным столом есть 6 мест. Сколькими способами можно рассадить людей за столом, если:

а) место хозяина в доме неприкосновенно;
б) первыми садятся дети, и они садятся рядом;
в) первыми садятся дети, но не рядом друг с другом;
г) жены садятся рядом со своими мужьями?

Ответы:

№1 а) 120; б) 288; в) 432; г) 72.

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

Используется презентация “Алгоритм вычисления факториала”

III. Самостоятельная работа.

Учащиеся работают на компьютерах, выполняя задания и заполняя индивидуальные бланки самостоятельной работы:

Самостоятельная работа

Домашнее задание.

№5. В зоопарке 5 львов надо распределить по одному по пяти клеткам, четырех тигров – по четырем другим клеткам и трех слонов – по трем вольерам.

а) Найдите число всех возможных распределений львов, тигров и слонов в зоопарке.
б) То же, но если есть четыре льва и львица и одного льва (известно какого именно) вместе с львицей надо посадить в одну клетку.
в) То же, что и в пункте а), но если у львов есть две семейные пары.
г) то же, что и в пункте а), но если между клетками для тигров и клетками для львов нет разницы.

Ответ: а) 5!•4!•3!=17280; б) 17280; в)( 5•4•3)•4!•3!=8640; г) 2177280.

IV. Подводим итоги урока.

1. Чему равно количество перестановок в множестве из n элементов?
2. Сколько алгоритмов вычисления факториала нами изучено?

Какие это алгоритмы? В чём различия между ними?

Презентация