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


Размещение в подпрограмме

Размещение подпрограмма

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

#1 Andrew

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

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

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

Размещение из 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.Теперь меняем элементы с помощью сочетания.
//----------------------------------------------------------------------------------//
// Название: GeneralDeployment                                                  	//
// Автор кода(именно кода): Andrew (Krasnobaev)                                 	//
// Сайт: redcode.do.am (временно пуст)                                          	//
// Описание: Размещение, занесённое в запись, в качестве метода(классов то тут нет) //
//----------------------------------------------------------------------------------//

type
  ArrType = array[0..65536] of byte;
  DepType = array[0..10000] of ArrType;
  Comb_Class = record
    
	procedure IntGeneralDeployment(ArrLength, DepLength: longint; Arr: ArrType; var DepArr: DepType; var DepCount: LongInt);
	var
  	p, q: array [0..10000] of byte;
  	i, j, k, d: longint;
	begin
  	DepCount := 0;
  	for i := 1 to ArrLength do p[i] := i;
  	repeat
    	for i := 0 to DepLength do q[i] := p[i];
    	while q[0] = 0 do
    	begin
      	while q[0] = 0 do
      	begin
        	inc(DepCount);
        	for i := 1 to DepLength do DepArr[DepCount][i] := Arr[q[i]];
        	j := DepLength;
        	while q[j - 1] > q[j] do dec(j);
        	k := DepLength;
        	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 (DepLength + j - 1) div 2 do
        	begin
          	d := q[DepLength + j - i];
          	q[DepLength + j - i] := q[i];
          	q[i] := d;
        	end;
      	end;
    	end;
    	j := DepLength;
    	while (j > 0) and (p[j] = j + ArrLength - DepLength) do dec(j);
    	if j > 0 then begin
      	p[j] := p[j] + 1;
      	for i := j + 1 to DepLength do p[i] := p[i - 1] + 1;
    	end;
  	until j = 0;
	end;
  end;

var
  Combinatorics: Comb_Class;
  ArrLength: 0..65536;
  DepLength, DepCount, i, j: LongInt;
  Arr: ArrType;
  DepArr: DepType;

begin
 
  //Ввод и настройка параметров
  writeln('Entering:');
  read( ArrLength, DepLength  );
  for i:=1 to ArrLength do read(Arr[i]);
 
  //Само размещение
  Combinatorics.IntGeneralDeployment( ArrLength, DepLength, Arr, DepArr, DepCount );
 
  //Вывод
  writeln;
  writeln('Result:');
  for i:=1 to DepCount do begin
	write('Deployment №',i,' is ( ');
	for j:=1 to DepLength do write(DepArr[i][j],' ');
	writeln(' );');
  end;
  writeln('There are ',DepCount,' Deployments');
  writeln('Press <Enter> to finish :');
  readln;
end.

redcode.do.am ( сайт пока пуст )

#2 Санек

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

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

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

Если сам писал, то молодец конечно. Кстати что за сайт?

#3 Andrew

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

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

Отправлено 17 января 2012 - 19:39

Сам писал. А на сайте пока ничего нет.
redcode.do.am ( сайт пока пуст )





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

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