Перейти к содержимому


Размещение


Сообщений в теме: 4

#1 Санек

    Продвинутый пользователь

  • Администраторы
  • 41 сообщений
  • ГородВитебск

Отправлено 22 декабря 2011 - 08:27

Размещение из 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; //Часть 1
  REPEAT
 
//Часть 2
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;
 
//Часть 3
 
  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.


#2 Andrew

    Пользователь

  • Пользователи
  • PipPip
  • 14 сообщений

Отправлено 22 декабря 2011 - 08:33

Лучше сделайте функцию, которая принимает массив, а возвращает массив всех перестановок. Удобнее использовать.
redcode.do.am ( сайт пока пуст )

#3 LVP

    Продвинутый пользователь

  • Администраторы
  • 180 сообщений
  • ГородВитебск

Отправлено 23 декабря 2011 - 12:37

Андрюха, напиши эту функцию и размести здесь.
Виктория Павловна

#4 Andrew

    Пользователь

  • Пользователи
  • PipPip
  • 14 сообщений

Отправлено 16 января 2012 - 19:53

Просмотр сообщенияLVP (23 декабря 2011 - 12:37) писал:

Андрюха, напиши эту функцию и размести здесь.

Как_передать_масив_в_подпрограмму?функция_hight_не_пашет.
redcode.do.am ( сайт пока пуст )

#5 Andrew

    Пользователь

  • Пользователи
  • PipPip
  • 14 сообщений

Отправлено 17 января 2012 - 18:23

Просмотр сообщенияLVP (23 декабря 2011 - 12:37) писал:

Андрюха, напиши эту функцию и размести здесь.

http://lvp37.ru/inde...BC%D0%BC%D0%B5/
redcode.do.am ( сайт пока пуст )





Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных