IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Размещения из n по m
сообщение
Сообщение #1


Профи
****

Группа: Пользователи
Сообщений: 920
Пол: Женский
Реальное имя: Марина

Репутация: -  2  +


Хочу получить размещения из n элементов по m элементов. Для этого для каждого возможного сочетания из n по m нахожу перестановки по m. Проблема в том, что размещений получается больше чем нужно!! Объясните пожалуста, чего я не предусмотрела!



uses crt;

type
mas=array[0..100] of integer;
mas1=array[1..100] of integer;

Var
razm,razm1 : mas;
s : mas1;
m,n,k,f,kol : integer;
i,j : byte;

procedure output;
var i: integer;
begin
for i:=1 to m do write(s[razm[i]]);
end;

procedure output1;
var i: integer;
begin
for i:=1 to m do write(s[razm1[i]]);
end;

Begin
clrscr;
writeln ('Naidem razmeshenia iz n elementov no m');
writeln ('Enter n and m');
readln (n,m);
writeln ('Vvedite mn-vo razmerom n');
for i := 1 to n do
readln (s[i]);
writeln ('Mn-vo razmerom n:'); writeln;
for i := 1 to n do
write ( s[i]:5);
readln;
clrscr;
for i:=1 to m do razm[i]:=i;
for i:=1 to m do razm1[i]:=i;
kol := 0;
while i <> 0 do
begin
output; write(' '); kol := kol + 1;
for i := 1 to m do razm1[i] := razm[i];
repeat
i:=m;
while razm1[i-1]>razm1[i] do
i := i - 1;
j:=i-1;
f:=razm1[j];
while razm1[i+1]>f do
i := i + 1;
razm1[j]:=razm1[i];
razm1[i]:=f;
i:=j+1;
k:=m;
while i<k do
begin
f:=razm1[i];
razm1[i]:=razm1[k];
razm1[k]:=f;
i := i + 1;
k := k - 1
end;
output1; write(' '); kol := kol + 1;
until j=0;
i :=m;
while razm[i]=n-m+i do
i := i-1;
razm[i] := razm[i] + 1;
for j := i+1 to m do
razm[j] := razm[j-1] + 1;
end;
writeln;
writeln('Kol-vo razmeshenii:', kol);
readkey;
End.







Сообщение отредактировано: 18192123 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Гость






Смотри, я не сторонник выдумывания новых алгоритмов... Есть алгоритм нахождения всех сочетаний из N по M (то, что у нас в FAQ-е называется Combination), и есть алгоритм нахождения всех перестановок (Permutations). Если их объединить, то получится алгоритм нахождения размещений:

const
max_n = 100;
type
arrType = array[1 .. max_n] of integer;

var
s: arrType; { <-- Это те значения, размещения которых будем выводить }
mas: arrType; { <-- Это - массив для хранения сочетаний }

N, M: Longint;
I, J: Longint;


{
для каждого из сочетаний вызываем эту процедуру обработки - и
внутри нее для конкретного сочетания находим все перестановки
}
procedure ProcessCombination(const values: arrType);

var
mas: arrType; { <-- Это - массив для перестановок }
i, j, k: integer;

procedure WritePermutation;
var i: Longint;
begin
for i := 1 to M do write(s[values[mas[i]]], ' '); { <--- Вот она - основная мысль !!! }
writeln;
end;

procedure swap(i, k: longint);
var X: byte;
begin
X := mas[i]; mas[i] := mas[k]; mas[k] := X;
end;

begin

fillchar(mas, sizeof(mas), 0);
for i := 1 to m do mas[i] := i;

while true do begin
WritePermutation;
i := M;
while (i > 0) and (mas[i] >= mas[i + 1]) do dec(I);

if I = 0 then break;

for J := I + 1 to M do
if mas[J] > mas[I] then k := J;
swap(I, k);
inc(I);
J := M;

while I < J do begin
swap(I, J); inc(I); dec(J);
end;
end;

end;



begin

write('n = '); readln(n);
write('m = '); readln(m);
writeln('enter the set of N items:');
for i := 1 to n do readln(s[i]);

for i := 1 to m do mas[i] := i;
while true do begin
ProcessCombination(mas);
i := M;
while (i > 0) and (mas[i] = N - M + i) do dec(i);

if i = 0 then break;
inc(mas[i]);
for j := i + 1 to M do mas[j] := mas[j - 1] + 1;
end;

end.

(в чем была основная мысль? В двойной индексации... Не просто s[mas[ i ]], а еще один уровень - через сочетания: s[values[mas[ i ]]])
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 19:31
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name