Интегрированный урок «Комбинаторика и программирование»

1.

Интегрированный урок
«Комбинаторика и программирование»
Мигушова Л.П. – учитель математики,
Осипова Е.В. – учитель информатики
МБОУ «СОШ №13»
г. Новочебоксарск

2.

"Считай несчастным тот день или тот час, в
который ты не усвоил ничего нового и ничего не
прибавил к своему образованию.»
Я. А. Коменский

3. Ребусы

4. Ребусы

3 4
бина
,,,,,,
ика

5.

Задачи из ЕГЭ на вероятность

6.

Записать всевозможные
двузначные числа, используя
цифры 3, 5, 7.
Подсчитать их количество.

7.

I-й метод (перебора).
Решение:
35; 37; 53; 57; 73; 75; 33; 55; 77.
Всего девять чисел.

8.

II-й метод (таблица вариантов).
Решение:
2-я цифра
1-я цифра
3
5
7
3
33
35
37
5
53
55
57
7
73
75
77
Всего девять чисел.

9.

III-й метод (дерево вариантов).
Решение:
3
3
5
7
5
3
7
7
3
5
7
5
33; 35; 37; 53; 55; 57; 73; 75; 77.
Всего девять чисел.

10.

Самостоятельная работа
Вариант 1
Вариант 2
Вариант 3
Вариант 4
1. На столе 12
кусков пирога. В
трех
«счастливых» из
них запечены
призы. Какова
вероятность
взять
«счастливый»
кусок пирога?
1. В коробке 24
карандаша, из
них 3 красного
цвета. Из
коробки наугад
вынимается
карандаш.
Какова
вероятность того,
что он красный?
1.В лотерее 100
билетов, из них 5
выигрышных.
Какова
вероятность
выигрыша?
1.В вазе 7
цветков, из них 3
розы. Из букета
наугад
вынимается
цветок. Какова
вероятность того,
что это роза?
2. В урне 15
белых и 25
черных шаров.
Из урны наугад
выбирается один
шар. Какова
вероятность того,
что он будет
белым?
2. Из чисел от 1
до 25 наудачу
выбрано число.
Какова
вероятность того,
что оно окажется
кратным 5?
2. В корзине
лежат 5 яблок и 3
груши. Из
корзины наугад
вынимается один
фрукт. Какова
вероятность того,
что это яблоко?
2. В корзине 10
яблок, из них 4
червивых.
Какова
вероятность того,
что любое взятое
наугад яблоко
окажется не
червивым?

11.

Задача: «Квартет»
Сколько времени
будут
пересаживаться
герои, если одна
пересадка занимает
1 минуту?

12.

Решение:
Всего 24
варианта

13.

Правило
произведения
Если объект А1 может быть выбран
n1 различными способами, А2 - n2
различными способами и т.д, Аk - nk
различными способами, то k объектов
А1 , А2 , ..., Аk в указанном порядке
можно выбрать n1 · n2 · ... · nk
способами.

14.

Решение:
IV место
1 вариант
III место
2 варианта
II место
3 варианта
Всего вариантов: 4 · 3 · 2 · 1 = 24.
Если одна пересадка занимает 1 минуту,
то 24 минуты будут пересаживаться
герои.
Ответ: 24 минуты.
I место
4 варианта

15.

Сколько времени займет пересадка, если герои
задумают сыграть квинтет, если к ним
присоединится белка с трубой?

16.

Решение:
Р = 5 · 4 · 3 · 2 · 1 = 120.
Если одна пересадка занимает 1
минуту, то 120 минут будут
пересаживаться герои.
Ответ: 120 минут или 2 часа.

17. Тест с оценкой

1. Встретились 10 друзей, и каждый пожал руку каждому.
Сколько всего было рукопожатий?
90, 45, 100
2. У Жени 3 брюк и 5 рубашек, удачно сочетающихся по цвету.
Сколько различных комбинаций одежды имеется у Жени?
15, 30, 8
3. Сколькими способами можно выбрать гласную и
согласную буквы из слова «книга»?
2, 6, 5
4. В классе 25 учеников. Сколькими способами можно выбрать
старосту и его заместителя?
600, 300, 100
5. В классе 25 учеников. Сколькими способами можно
выбрать двух дежурных?
600, 300, 100

18.

Задача: « Обед десяти »
Десять студентов решили пообедать
в кафе, но места за столом не были
назначены заранее, между ними
возник спор, как лучше
разместиться за столом.
Хозяин кафе предложил им
попробовать все возможности и
пообещал, что начиная с того дня,
когда закончатся все возможные
способы размещения, он будет
кормить их в кафе бесплатно.
Студенты обрадовались и
заключили договор.
Через сколько времени, они получат
бесплатный обед?

19.

Решение:
P = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 =
= 3 628 800 (дней) ≈ 9 942 (лет).
Если кушать 3 раза в день,
то можно потратить 3 314 лет.
Ответ:
через 3 314 лет
студенты получат
бесплатный обед.

20.

Вопрос 1.
Как Вы думаете: какая процедура
обеспечивает ввод данных в Паскале ?
Ответы:
Вариант 1: begin
Вариант 2: input
Вариант 3: read или readln
Вариант 4: print

21.

Вопрос 4.
Как Вы думаете: какой символ
проставляется между вводимыми
величинами как конец одной и начало
следующей ?
Ответы:
Вариант 1: запятая
Вариант 2: пробел
Вариант 3: точка с запятой
Вариант 4: наклонная черта /

22.

Вопрос 5.
Как Вы думаете: какая клавиша
нажимается после набора последнеого
данного в операторе read ?
Ответы:
Вариант 1: Enter
Вариант 2: точка с запятой
Вариант 3: пробел
Вариант 4: Ctrl

23.

Вопрос 6.
Как Вы думаете: чем отличается readln от read ?
Ответы:
Вариант 1: ничем
Вариант 2: переводом курсора в readln к началу следующей строки
Вариант 3: в readln все данные набираются в одной строке
Вариант 4: в read все данные набираются в отдельной строке
Вопрос 7.
Какая процедура выводит числовые данные, символы,
строки и булевские значения ?
Ответы:
Вариант 1: write или writeln
Вариант 2: print
Вариант 3: read или readln
Вариант 4: output

24. Разминка

25. Комбинаторика – раздел дискретной математики, изучающий всевозможные сочетания и расположения предметов.

А
200 км
400 км
Д
В
С
Путешественник хочет
выехать из пункта А,
посетить пункты В, С, Д,
после чего вернуться в А.
Какими путями можно это
сделать?
Путь
Длина пути
в км
АВСДА
1550 км
АВДСА
1300 км
АСВДА
1450 км
АСДВА
1300 км
АДВСА
1450 км
АДСВА
1550 км

26.

Комбинаторные задачи –
практические задачи, при решении
которых возникают проблемы с большим
количеством операций. При решении этих
задач используется метод перебора и
уходит очень много времени. Поэтому есть
специальные приёмы решения
комбинаторных задач, на которых мы
сегодня и остановимся. Рассмотрим приём
рассуждений и приём перестановок.

27.

Приём рассуждений
Приём перестановок

28.

В турнире участвовало 12
шахматистов, причём каждый с
каждым сыграл по одной партии.
Сколько всего было сыграно
партий?
(Самостоятельное решение с
последующей проверкой).
12 11
66
2

29.

Если мы хотим, чтобы компьютер решал наши
задачи, необходимо уметь записывать алгоритмы на
языках, понятных машинам. Поэтому сегодня мы с
вами научимся составлять программу, понятную
для машины, на языке Pascal. Умение составлять
программы на языках программирования вам также
пригодится на ЕГЭ по информатике.

30.

Некоторые операторы языка QBasic.
CLS - очистить экран. Вся информация, которая
была на экране стирается.
INPUT (ввод) – оператор ввода. Используется
для передачи в программу каких-либо
значений.
PRINT (вывод, печать) – оператор вывода.
END – оператор конца программы.

31.

пример:
INPUT а
На экране появится приглашение ввести данные
(появится знак "?") и компьютер будет ждать их
ввода. Для ввода необходимо ввести данные с
клавиатуры и нажать ввод (Enter).
PRINT "Привет! Меня зовут Саша."
На экран будет выведено сообщение: Привет! Меня
зовут Саша.

32.

Пример 1. У Жени есть 3 свитера (красный,
синий, чёрный) и две пары брюк (синие и
чёрные). Сколько у него имеется способов
одеться?
CLS
INPUT ”количество свитеров =”;N
INPUT ”количество брюк =”;M
R=N*M
PRINT ”R=”; R
F5 – запуск программы

33. Встретились 8 друзей, и каждый пожал руку каждому. Сколько всего было рукопожатий?

CLS
INPUT ”количество друзей =”;N
R=N*(N-1)/2
PRINT ”R=”; R

34. Задачи на перестановки

Перестановка – упорядоченный
набор чисел 1,2,…,n. При этом n
называется порядком перестановки.
Число всех перестановок порядка n
равно 1*2*…*n=n!
n 1 2 3
4
5
6
7
8
9
10
n! 1 2 6 24 120 720 5040 40320 362880 3628800

35. Анаграммы

Анаграмма – это «слово», полученное из
данного слова перестановкой его букв(но не
обязательно имеющее смысл).
Сколько существует различных анаграмм слова
«логика» ?
6!=720
«робот»
5!/2=60

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

1. На 3 призовых места претендуют Вася,
Дима и Коля. Каким числом способов могут
распределиться
места?
2. Сколько различных трехзначных чисел
можно записать с помощью цифр 1,2,3 при
условии, что цифры могут повторяться?

37. Выводы

"Считай несчастным тот день
или тот час, в который ты не
усвоил ничего нового и ничего не
прибавил к своему образованию.»
Я. А. Коменский

38. Анаграмма «Космос»

Андриян
Николаев
Юрий
Гагарин
Муса
Манаров
Николай
Бударин

39.

5. Рефлексия
39

40. Спасибо !

7!
2520
2