Сочетания обозначаются буквой 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.