Сочетание из n элементов по m - это соединение, содержащее m элементов, взятых из n различных элементов, отличающихся хотя бы одним элементом. Порядок элементов не учитывается.

Сочетания обозначаются буквой C.

Формула сочетания:

С из n по m

C=n! / m!*( n-m )!

Задача.

В магазине 5 разных по цвету гвоздик: К(красная),Ж(жёлтая),Р(розовая),Б(белая),Г(голубая). Из них надо выбрать все возможные варианты букетов и вывести их на экран.

Для начала попробуем сделать это на бумаге:

К Ж Р (1 перестановка )

К Ж Б (2 перестановка )

К Ж Г (3 перестановка )

К Р Б (4 перестановка )

К Р Г (5 перестановка )

К Б Г (6 перестановка )

Ж Р Б (7 перестановка )

Ж Р Г (8 перестановка )

Ж Б Г (9 перестановка )

Р Б Г (10 перестановка )

Как мы видим всего получилось 10 вариантов.

Теперь давайте проверим нашу  формулу сочетания (которая указана выше).

C(из 5 по 3)
С = 5! / 3! ( 5 - 3 )! = 4*5 / 2 * 1 = 10

Ответ:10 вариантов.

Теперь давайте попробуем составить словесный алгоритм этой задачи.

Словесный алгоритм:

1. Читаем заданные n и   m и забивает массив р от 0..m

(в этой задачи лучше пользоваться Рипитом)

2. Первым делом в Рипите выводим сочетание.

3. Ищем с конца элемент не достигшей своего максимума(этот элемент j).

4. Если нашли такой элемент, то увеличиваем его значение на единицу, а остальные элементы по порядку от j+1 делаем на единицу больше чем предыдущий(на паскале это выглядит так:  p[i]:=p[i-1]+1).

Программный алгоритм

var p: array [0..1000] of byte;
     n,m,i,j,s:longint;
     b:array [1..1000] of char;
 
 begin

   readln(n,m);
 
   for i:=1 to n do read(b[i]);
   for i:=0 to m do p[i]:=i;
 
  REPEAT
   
   for i:=1 to m do write(b[p[i]]);
    writeln;
   s:=s+1;
     
   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-07-13 10:37:01)