Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

Подписаться Бесплатная «Серебряная» новостная рассылка Подписчиков 7.350 RSS
←   Ноябрь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней 1 выпусков (1 раз в 2 месяца)


Сайт рассылки: http://bestinvestblog.com
Открыта: 10-02-2009

Автор
bestinvestblog

Статистика

7.350 подписчиков
0 за неделю
←   Все выпуски   →

Занятие 53. Комбинаторика. Число сочетаний.


Сегодня, уважаемые подписчики, мы с вами рассмотрим одну из задач комбинаторики.

В связи с “эпидемией свинского гриппа” всем моим подписчикам желаю здоровья, бодрости, хорошего настроения, а также счастья в семейной и личной жизни!!!

ЧИСЛО СОЧЕТАНИЙ

Из N различных элементов будем составлять группы по M элементов в каждой, не обращая внимания на порядок элементов в группе. Получающиеся при этом комбинации называются сочетаниями из N элементов по M. Общее число различающихся между собой сочетаний обозначается  и вычисляется по формуле . Например, число сочетаний из пяти элементов по три равно .

Практическое значение имеют также следующие соотношения:

1) так как, по определению 0! = 1, то , ;

2) в силу симметрии формулы для числа сочетаний, справедливо .

Численный эксперимент показывает, что если для вычисления числа сочетаний использовать формулу непосредственно, то при использовании типа LongInt предел возможностей достигается уже при N = 12. Дальнейшие попытки увеличивать значение N приводят к переполнению, что объясняется быстрым ростом факториала.

Уважаемые подписчики! Предлагаю вам убедиться в этом самостоятельно, для чего вам придётся составить соответствующую программу. Если при этом будут возникать те или иные вопросы, прошу обращаться ко мне через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru.  

Чтобы избавиться от лишних умножений, воспрепятствовать чрезмерному росту произведения и тем самым отдалить наступление переполнения, существуют три возможности.

Первая возможность. Формула и пример вычисления числа сочетаний  показывают, что есть возможность сократить все сомножители, соответствующие M!. В результате в числителе остаются сомножители от M + 1 до N включительно, а (N - M)! остаётся в знаменателе. При этом желательно, чтобы выполнялось условие M ³ (N – M). В этом случае сокращается наибольшее число сомножителей. Чтобы добиться выполнения этого условия, достаточно заменить M на M – N, если вдруг оказалось, что M < (N – M).

Вторая возможность. Она заключается в дальнейшем сокращении того, что осталось после предыдущего сокращения на M!. Базируется эта возможность на принципе Дирихле, который в данном приложении может быть сформулирован следующим образом: если перемножаются K идущих подряд чисел, то результат обязательно делится на K без остатка. Таким образом, выполняя последовательные умножения в числителе, мы можем параллельно выполнять деления без остатка на числа знаменателя. Для вышеприведённого примера это выглядит следующим образом: умножим 6 на 7, а результат разделим на 2; то, что получилось умножим на 8, а результат разделим на 3; и, наконец, то, что получилось, умножим на 9, а результат разделим на 4.

Третья возможность. Она связана с выбором правильного порядка выполнения операций. Если нам известно, что произведение X и Y делится без остатка на Z, то сначала целесообразно проверить, делится ли X без остатка на Z. Если это так, то порядок действий должен быть таким: X Div Z * Y. В противном случае вычислять следует так: Y Div Z * X.

Задача C.1.11. “Число сочетаний”. Вычислить число сочетаний, которые могут быть получены из N различных элементов по M элементов в каждом.

   Function Combination ( M, N: LongInt ): LongInt;
      Var P,i: LongInt;
   Begin
      If M < N - M Then M := N - M;
      P := 1;
      For i := 1 To N - M Do
         If (i+M) Div i = 0 Then P := (i+M) Div i * P
                            Else P := P Div i * (i+M);
      Combination := P
   End;

Решение задачи в целом реализовано подпрограммой C.1.11 (функция Combination). Её основные составляющие таковы:  

1) значение M заменяется большим из M и N–M;

2) текущему результату P присваивается исходное единичное значение;

3) организуется цикл с числом повторений N-M, что соответствует количеству сомножителей после сокращения на M!; последовательные значения параметра цикла i представляют собой числа в знаменателе;

4) каждый сомножитель в числителе ровно на M больше соответствующего сомножителя в знаменателе; по результатам проверки условия (i+M) Div i = 0 выбирается порядок выполнения операций и выполняются очередные умножение и деление.    

Тестирование подпрограммы C.1.11 показало, что она может вычислять число сочетаний при любом M для N = 33. Дальнейшие попытки увеличивать значение N снова приводят к переполнению.

Привожу также и полный текст программы C.1.11.

{$B+,D+,E+,I+,L+,N+,Q+,R+,X-}
Program C_01_11;
   Function Combination ( M, N: LongInt ): LongInt;
      Var P,i: LongInt;
   Begin
      If M < N - M Then M := N - M;
      P := 1;
      For i := 1 To N - M Do
         If (i+M) Div i = 0 Then P:=(i+M) Div i * P
                            Else P:=P Div i * (i+M);
      Combination:=P
   End;
   Var M,N: LongInt;
Begin
   Repeat
      Write('Введите M и N: ');
      ReadLn(M,N)
   Until (M>=0) And (N>=M);
   WriteLn('Число сочетаний C = ',Combination(M,N));
   ReadLn
End.

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.

 
В избранное