Билет № 28. Комбинаторные задачи. Виды и формулы для подсчёта числа возможных комбинаций.

⇐ ПредыдущаяСтр 5 из 5

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

Задачи, требующие такого решения, называются комбинаторными.

В начальной школе такие задачи решаются методом перебора, а для облегчения этого процесса используются таблицы и графики.

Вылеляют:

1)Размещение элементов.

Правило сумы и произведения- это общие правила решения комбинаторных задач, кроме них пользуются формулами для подсчета комбинаций, которые используются наиболее часто.

Определение: Пусть имеется множество, состоящее из n-элементов, в нем выбирают подмножества, состоящие из m- элементов. Размещением из n-элементов, по m- называются картежи составленные из m элементов.

В размещении важен не только состав элементов, но и порядок их следования.

Пример: 7, 4, 1= 74, 41, 47, 14, 71, 14

Пример: учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание н 1-ый день что бы в нем было 4 различных предмета.

1- 8 способов, 2-7, 3-6, 4-5.=1680.

Любое расписание на один день отличается либо предметами либо порядком следования предметов. Значит речь идет о размещениях их 8 элементов по 4.

Для подсчета количества размещений существуют формулы:

а) размещение из n по m с повторениями

с волной сверху А по n в степени m = n в степени m.

Пример: сколько трехзначных чисел можно составить из цифр 1, 2, 5, 7, 8, если цифры в записи могут повторяться?

С волной А по 5 в степени 3= 5 в степени3 =125.

в) без поторений.

А по n в степени m =nх(n-1)…..(n-m+1)/

Пример: сколь…. Если в записи не повторяются А по 5 в степени 3= 5х4х3=60.

2)В данном случае разные числа получаются в результате перестановки цифр, по этому размещение из n по m называют перестановкой из n элементов.

Другими словами перестановкой и n элементов называют каждое расположение этих элементов в определенном порядке.

Количество перестановок подсчитывается по формуле.

P по n= n1=1х2х3……хn

3) сочетание.

Пример: имеется 5 роз разног цвета, требуется составить букет из 3х роз. Сколькими способами это можно сделать?

12345 123, 235, 321

Наборы элементов, в которых важен состав, а порядок не важен называют сочетаниями.

Сочетанием из n элементов по m называется любое множество их m элементов взятых из n элементного множества.

Формула: С по n в степени m = n! \m! х(n-m)!

С по 5 в 3 степени = 10.-

Задачи:

имеется 5 автомобилей разных марок сколько разлчных кортежей автомашин можно составить

Р по5=5! =120.

Билет № 29. Правило суммы и произведения (без доказательства), их применение при решении комбинаторных задач.

Правило суммы:

Если а можно выбрать х способами, а б у способами, то выбор элемента « а или б» можно осуществить х+у способами.

Имеются 4 желтых и 3 красных воздушных шарика. Сколькими способами можно выбрать один шарик.

Ж-4 кр-3 = 7 выбор одного шарика ( либо, либо) можно осуществить 4+3 способами.

Правило произведения:

Если а можно выбрать х способами, а б у способами, то элемент « а и б» можно выбрать х*у сп.

Имеются 5 красных, 4 желтых, 4 розовых шарика. Сколькими способами можно составить букет из 3 роз разного цвета.

Кр-5 ж-4 р-4 ) 5*4*4=80

Сколько 2х значных чисел можно составить из цифр 7, 4, 1 при условии

1. Цифры могут повторяться. ( 3*3=9)

2. Не могут повторяться ( 3*2=6)

Сколько 4х значных цифр можно составить из 0, 8 ( 1*2*2*2=8)

Билет № 30. Перестановки из n элементов. Применение при решении задач.

Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается Pn и вычисляется по формуле Pn=n!.

Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд? Решение: эта задача о числе перестановок семи разных книг. Имеется P7=7! =1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.

Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.

Пример. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?

Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.

Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

Билет № 31. Размещение из n элементов по m без повторений. Примеры применения при решении задач.

Число размещений без повторений из n по m (n различных элементов) вычисляется по формуле:

Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются;

Решение. Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.

По формуле получаем: наборов.

!!! Размещением из n элементов по m элементов без повторений называется упорядоченное подмножество попарно различных m элементов множества Mn ( ).

Билет № 32. Размещение из n элементов по m элементов с повторениями.. Примеры применения при решении задач.

Размещениями с повторениями из n элементов по m называются упорядоченные m-элементные выборки, в которых элементы могут повторяться.

Число размещений с повторениями вычисляется по формуле:

Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 2) буквы могут повторяться?

Решение.

Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

По формуле (3.2) получаем: наборов.

!!! Размещение с повторениями или выборка с возвращением — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.

Билет № 33. Сочетания из n элементов по m элементов. Примеры применения при решении задач.

Сочетаниями из n элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (отличие сочетаний от размещений в том, что в сочетаниях не учитывается порядок элементов).

Число сочетаний без повторений (n различных элементов, взятых по m) вычисляется по формуле:

Число сочетаний c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться) вычисляется по формуле:

Пример. Возьмем буквы Б, А, Р. Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы.

А	В	А Ù В
и	и	и
и	л	л
л	и	л
л	л	л

Решение.

Получатся наборы: БА (БА и АБ - один и тот же набор), АР и РБ.

А	В	А Ù В	В Ù А
И	И	И	И
И	Л	Л	Л
Л	И	Л	Л
Л	Л	Л	Л

По формуле получаем: наборов.

Получатся наборы: ББ, БА, БР, АА, АР, РР.

По формуле получаем: наборов.

Пример. Из 20 учащихся надо выбрать двух дежурных. Сколькими способами это можно сделать?

Решение. Надо выбрать двух человек из 20. Ясно, что от порядка выбора ничего не зависит, то есть Иванов-Петров или Петров-Иванов - это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2.

По формуле получаем: способов.

Пример. В хлебном отделе имеются булки белого и черного хлеба. Сколькими способами можно купить 6 булок хлеба?

Решение. Обозначая булки белого и черного хлеба буквами Б и Ч, составим несколько выборок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ, ... Состав меняется от выборки к выборке, порядок элементов несущественен, значит это - сочетания с повторениями из 2 по 6. По формуле получаем способов.

Cделаем проверку и выпишем все варианты покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Их действительно 7.

Билет № 34. Текстовая задача: определение, структура, типы, этапы решения. Примеры.

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

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

Типы т.з. по отнош.между условиями и требованиями.

1. Определенные ( в них заданных условий столько, сколько необходимо и достаточно для выполнения требования)

2. Недоопределенные ( в них условий недостаточно для выполнения требований)

3. Переопределенные ( в них есть лишние условия)

Этапы решения.

и у алгебраического и у арифметического.

1. Восприятие и анализ содержания задачи.

2. Поиск и составления плана решения задачи.

3. Выполнение плана решения. Формулировка вывода о выполнении требования задачи ( ответа на вопрос задачи).

4. Проверка решения и устранение ошибок, если они есть. Формулировка окончательного вывода о выполнении требования задачи или ответа на вопрос задачи.

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

Билет № 35. Текстовая задача: методы решения. Примеры.

Основные методы решения – арифметический и алгебраический.

О. решить задачу арифм.методом – значит найти ответ на требование задачи при помощи выполнения арифметических действий над числами. ( можно решать несколькими способами, они будут отличаться логикой рассуждения).

Пример. Сшили 3 платья, расходуя на каждое по 4 метра ткани. Сколько кофт можно сшить из этой ткани, если расходовать на 1 кофту по 2 м.

1. 4*3=12 2. 12: 2=6. 1. 4: 2=2 2. 3*2=6

О. решить задачу алгебраическим методом – значит найти ответ на требование задачи, составив и решив уравнение или систему уравнений. ( тоже можно несколькими способами)

Пример. Свитер, шапку и шарф связали из 1кг 200г шерсти, шарф на 100 гр больше шапки и на 400 гр меньше свитера. Сколько шерсти израсх.на каждую вещь?

Пусть х-это шарф. Х-(х-100) + ( х+400)=1200

3х+300=1200

3х=900

Х=300гр. И т.д.

Билет № 36. Понятие алгоритма, его основные свойства и способы представления. Примеры.

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.

Основными свойствами алгоритма являются:

1.детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;

2.результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;

3.массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;

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

Алгоритм должен быть формализован по некоторым правилам посредством конкретных изобразительных средств. К ним относятся следующие способы записи алгоритмов: словесный, формульно-словесный, графический, язык операторных схем, алгоритмический язык.

⇐ Предыдущая 1 2 3 45