Размещение из n по m - это соединения, отличающиеся друг от друга составом элементов или их порядком, содержащие m элементов из n различных.
Размещение обозначается буквой A
Формула размещения
А= n! / ( n-m )!
Теперь устная задача
Задача
Найти сколько вариантов из 3-х букв a b c можно составить 2-х буквенных слов.
Попробуем на бумаге:
(1 перестановка ) a b (3 перестановка ) a c (5 перестановка ) b c
(2 перестановка ) b c (4 перестановка ) c a (6 перестановка ) c b
Получается 6 вариантов.
Теперь проверим нашу формулу
А=3!/(3-2)1=6/1=6
Значит формула правильная.
Ответ:6 вариантов.
Алгоритм
Тут нам понадобится совместить алгоритм сочетания и алгоритм перестановки .
Способ первый
В алгоритме сочетания ( смотри ниже).
1. Пересохраняем массив p в q.
2. Делаем перестановку из m элементов на ходящихся в массиве q.
3.Теперь меняем элементы с помощью сочетания.
type mas= array [0..1000] of byte;
var p,q:mas;
n,m,i,j,s,k,d:longint;
b:array [1..1000] of char;
begin
readln(n,m);
for i:=1 to n do read(b[i]);
s:=0;
for i:=0 to m do p[i]:=i;<------[b][color=green]{Часть 1}[/color][/b]
REPEAT
[color=green]{_______________[b]Часть 2[/b]_______________} [/color]
for i:=0 to m do q[i]:=p[i];
while q[0]=0 do
Begin
while q[0]=0 do
begin
for i:=1 to m do write(b[q[i]]);
writeln;
inc(s);
j:=m;
while q[j-1]>q[j] do dec(j);
k:=m;
while q[j-1]>q[k] do dec(k);
d:=q[j-1];
q[j-1]:=q[k];
q[k]:=d;
for i:=j to (m+j-1)div 2 do
begin
d:=q[m+j-i];
q[m+j-i]:=q[i];
q[i]:=d;
end;
end;
end;
[color=green]{_______________[b]Часть 3[/b]_______________} [/color]
j:=m;
while (j>0) and(p[j]=j+n-m) do dec(j);
if j>0 then begin
p[j]:=p[j]+1;
for i:=j+1 to m do p[i]:=p[i-1]+1;
end;
UNTIL j=0;
writeln(s);
end.
Способ второй
Всё тоже самое только записываем перестановку в процедуру.
type mas= array [0..1000] of byte;
var p:mas;
n,m,i,j,s:longint;
b:array [1..1000] of char;
procedure perestan(q:mas);
var i,j,k,d:longint;
begin
while q[0]=0 do
begin
for i:=1 to m do write(b[q[i]],' ');
writeln;
inc(s);
j:=m;
while q[j-1]>q[j] do dec(j);
k:=m;
while q[j-1]>q[k] do dec(k);
d:=q[j-1];
q[j-1]:=q[k];
q[k]:=d;
for i:=j to (m+j-1)div 2 do
begin
d:=q[m+j-i];
q[m+j-i]:=q[i];
q[i]:=d;
end;
end;
end;
begin
readln(n,m);
for i:=1 to n do read(b[i]);
for i:=0 to m do p[i]:=i;
REPEAT
perestan(p);
j:=m;
while (j>0) and(p[j]=j+n-m) do dec(j);
if j>0 then begin
p[j]:=p[j]+1;
for i:=j+1 to m do p[i]:=p[i-1]+1;
end;
until j=0;
writeln(s);
end.Отредактировано Санчоус (2011-11-01 07:57:15)
