РАЗМЕЩЕНИЕ
Размещение в
математике
Размещение без
повторения
Размещениями из n различных элементов по m называются
соединения (наборы), каждое(ый) из которых содержит m элементов из n,
взятых в определенном порядке. Размещения из n различных элементов по m
отличаются друг от друга элементами или порядком их расположения.
На рисунке показано,
как получить размещения из пяти различных элементов по три:
на первое место в наборе можно
поставить любой из пяти элементов (первый столбик состоит из пяти строк);
на второе место - любой из четырех оставшихся элементов, т.е.
от каждого элемента первого столбика проведены четыре стрелки (второй столбик);
на третье место – любой из
оставшихся трех элементов, т. е. от каждого элемента проведены три стрелки.
Размещение с
повторениями.
Размещения из n элементов, в каждое
из которых входит m элементов, причем
один и тот же элемент может повторяться в каждом размещении любое число раз,
называется размещениями из n по m элементов с
повторением.
После выбора первого
элемента второй элемент можно выбрать n элементов, так как
элементы в перестановке с повторениями могут повторяться), третий элемент можно
выбрать также n способами и т. д., m-й элемент – n способами.
По правилу
произведения m элементов из n можно выбрать n*n*...*n (число сомножителей равно m ) способами, т. е.
число размещений с повторениями.
Размещение в информатике
Задача 1. Напечатать все последовательности длины k из чисел 1..n.
Решение: Будем печатать их в лексикографическом порядке (последовательность а
предшествует последовательности b, если для некоторого i их начальные отрезки длины i
равны, а (i+1)-ый член последовательности а меньше). Первой будет последовательность
<1,1,...,1>, последней - <n,n,...,n>. Будем хранить последнюю напечатанную
последовательность в массиве x[1],..,x[k].
last[1],..,last[k] положим равным n. Для того, чтобы перейти к следующей
последовательности надо: двигаясь с конца последовательности, найти самый правый
член, меньший n, увеличить его на 1, а идущие за ним члены положить равными 1.
Процедура print(x:massiv) - вывод последовательности.
Функция egual(x,last:massiv):boolean - сравнивает элементы массивов,если x<>last, то
egual:=false иначе egual:=true.
for i:=1 to k do x[i]:=1;
print(x);
for i:=1 to k do last[i]:=n;
while not(equal(x,last)) do
begin
p:=k;
while not (x[p]<n) do p:=p-1;
x[p]:=x[p]+1;
for i:=p+1 to k do x[i]:=1;
print(x);
end;
Комментариев нет:
Отправить комментарий