Задачи, решаемые с помощью размещений
Пример 3. Некто забыл нужный ему номер телефона, который состоит из одной из десяти букв и пяти цифр, но он помнит, что в образовании этого номера участвуют цифры 3, 5, 7, 9. Какое наибольшее количество проб надо сделать, чтобы дозвониться нужному абоненту?
В искомый номер должны войти четыре цифры, которые можно разместить на 5 местах
Комбинируя эти номера с каждой из десяти букв, получаем:
10
Составим программу
с использованием процедуры размещений.
Program Problem3;
uses WinCrt;
var
p : longint;
{----------------------------------------------------------------------------------------}
Procedure placement(n, k : integer; var r : longint);
var
i : integer;
begin
r := 1;
for i := 1 to k do
r := r*(n - k + i)
end;
{----------------------------------------------------------------------------------------}
begin
placement(5, 4, p);
p := 10*10*p;
writeln('Надо сделать ', p, ' проб, чтобы дозвониться')
end.
Пример 4. Сколько размещений из n элементов по m будет начинаться с первого элемента?
Соображения по составлению программы
Из n элементов выберем первый элемент и строго закрепим его на первом месте в получаемых размещениях.
Тогда, в исходном множестве останется n - 1 элементов, из которых надо выбирать еще по m - 1 - му элементу и добавлять к уже имеющемуся и стоящему на первом месте первому элементу.
Теперь остается выяснить, сколькими способами можно из n - 1 выбрать по
Поскольку первый элемент строго закреплен на первом месте в получаемых размещениях, то число всевозможных способов и будет равно
Программа
Program Problem4;
uses WinCrt;
var
p : longint;
m, n : integer;
{----------------------------------------------------------------------------------------}
Procedure placement(n, k : integer; var r : longint);
var
i : integer;
begin
r := 1;
for i := 1 to k do r := r*(n - k + i)
end;
{----------------------------------------------------------------------------------------}
begin
write('Введите число всех элементов '); readln(m);
write('Введите число выбираемых элементов '); readln(n);
placement(m - 1, n - 1, p);
writeln('Число размещений из ', m, ' элементов по ', n, ',');
writeln('которые нач. с первого элемента, равно ', p)
end.
Пример 5. Составлены размещения из 10 элементов по 7 элементов. Сколько из этих размещений будут содержать: а) первый элемент, б) второй и четвертый элементы?
Решение
Во-первых, чем эта задача отличается от предыдущей?
В предыдущей задаче к первому элементу было строгое требование, - он должен находиться в образуемых размещениях обязательно на первом месте.
В этом примере, первый элемент просто должен присутствовать в получаемых размещениях, но совсем необязательно чтобы он находился на первом месте, значит он может занимать любое из 7 мест в получаемых размещениях.
Пронумеруем элементы множества цифрами от 1 до 7, тогда заданное множество элементов может быть записано так: {1, 2, 3, 4, 5, 6, 7}. Первый элемент выбираем из заданного множества, а "незанятые" места обозначим "x". Как видно, получается 7 подмножеств.
Отсюда следует, что его можно расположить в получаемых размещениях
Во-вторых,
после того, как "вытащили” первый элемент из 10 в нем осталось 9 элементов. Из этих 9 надо выбрать и добавить к первому элементу еще 6, чтобы всего получаемых эл. было бы 7. Это можно сделать
В итого мы имеем количество способов, равное произведению размещений
Программу
составьте самостоятельно
