Warning: Illegal string offset 'html' in /var/www/lvp37/data/www/lvp37.ru/cache/skin_cache/cacheid_1/skin_topic.php on line 909
Сочетание - олимпиадники-информатики

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


Сочетание


В теме одно сообщение

#1 yanush

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

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

Отправлено 22 December 2011 - 08:32

Сочетание из 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.


#2 Andrew

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

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

Отправлено 12 January 2012 - 06:25

А где сочетание с повторением?
redcode.do.am ( сайт пока пуст )





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

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