РАЗМЕЩЕНИЕ

РАЗМЕЩЕНИЕ
Размещение в математике
Размещение без повторения

Размещениями из 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;

Комментариев нет:

Отправить комментарий