Алгоритм и программа расчета числа сочетаний для больших чисел без вычисления промежуточных факториалов путем их разложения на простые множители и сокращений

Размещено на http://www.allbest.ru/

АЛГОРИТМ И ПРОГРАММА РАСЧЕТА ЧИСЛА СОЧЕТАНИЙ ДЛЯ БОЛЬШИХ ЧИСЕЛ БЕЗ ВЫЧИСЛЕНИЯ ПРОМЕЖУТОЧНЫХ ФАКТОРИАЛОВ ПУТЕМ ИХ РАЗЛОЖЕНИЯ НА ПРОСТЫЕ МНОЖИТЕЛИ И СОКРАЩЕНИЙ

В Internet встречается задача: «Найти все комбинации m по n, при этом m и n могут быть очень большими числами, вплоть до нескольких десятков тысяч» и предлагаются различные методы ее решения, в том числе и верные, т.е. работающие [1]. Существуют также on-line калькуляторы факториалов [2] и числа сочетаний [3]. Проблема возникает потому, что при использовании классической комбинаторной формулы числа сочетаний:

,

где: n - число элементов в исходном множестве; m - число элементов в подсистеме, для расчета числа сочетаний необходимо предварительно рассчитать значения факториалов, а они в большинстве языков программирования могут быть рассчитаны для значений аргумента, не превосходящим 170, а иногда и еще меньше, например 30.

Для решения этой проблемы предлагается следующий алгоритм, отличающийся от имеющихся в Internet:

1. Найти все простые числа меньшие заданного параметра n.

2. Сформировать массив чисел числителя.

3. Сформировать массив простых сомножителей чисел числителя.

4. Сформировать массив чисел знаменателя.

5. Сформировать массив простых сомножителей чисел знаменателя.

6. Сформировать массив простых сомножителей числителя, не входящих в массив простых сомножителей знаменателя.

7. Перемножить массив уникальных простых сомножителей числителя.

На рисунках 1 и 2 приводятся экранные формы для задания параметров расчета числа сочетаний для расчета одного значения и массива значений:



Рисунок 1. Экранная форма для задания расчета одного значения числа сочетаний

Рисунок 2. Экранная форма для задания расчета массива значений числа сочетаний

На рисунке 3 и в таблице 1 приведены результаты расчетов:

Рисунок 3. Результат расчета значения числа сочетаний

Отметим, что далеко не каждый on-line калькулятор позволяет посчитать число сочетаний из 10000 по 5, который без проблем рассчитывается по предложенному алгоритму прилагаемой программой. Это говорит о том, что предлагаемый алгоритм может быть востребован. Но вот, например, сайт Вольфрам-математики [3], дает тот же результат: 832500291625002000.

Таблица 1 - Пример расчета числа сочетаний при различных значениях n и m

N	M1	M2	M3	M4	M5	M6	M7	M8	M9	M10	M11
N1	1
N2	2	1
N3	3	3	1
N4	4	6	4	1
N5	5	10	10	5	1
N6	6	15	20	15	6	1
N7	7	21	35	35	21	7	1
N8	8	28	56	70	56	28	8	1
N9	9	36	84	126	126	84	36	9	1
N10	10	45	120	210	252	210	120	45	10	1
N11	11	55	165	330	462	462	330	165	55	11	1
N12	12	66	220	495	792	924	792	495	220	66	12
N13	13	78	286	715	1287	1716	1716	1287	715	286	78
N14	14	91	364	1001	2002	3003	3432	3003	2002	1001	364
N15	15	105	455	1365	3003	5005	6435	6435	5005	3003	1365
N16	16	120	560	1820	4368	8008	11440	12870	11440	8008	4368
N17	17	136	680	2380	6188	12376	19448	24310	24310	19448	12376
N18	18	153	816	3060	8568	18564	31824	43758	48620	43758	31824
N19	19	171	969	3876	11628	27132	50388	75582	92378	92378	75582
N20	20	190	1140	4845	15504	38760	77520	125970	167960	184756	167960
N21	21	210	1330	5985	20349	54264	116280	203490	293930	352716	352716
N22	22	231	1540	7315	26334	74613	170544	319770	497420	646646	705432
N23	23	253	1771	8855	33649	100947	245157	490314	817190	1144066	1352078
N24	24	276	2024	10626	42504	134596	346104	735471	1307504	1961256	2496144
N25	25	300	2300	12650	53130	177100	480700	1081575	2042975	3268760	4457400
N26	26	325	2600	14950	65780	230230	657800	1562275	3124550	5311735	7726160
N27	27	351	2925	17550	80730	296010	888030	2220075	4686825	8436285	13037895
N28	28	378	3276	20475	98280	376740	1184040	3108105	6906900	13123110	21474180
N29	29	406	3654	23751	118755	475020	1560780	4292145	10015005	20030010	34597290
N30	30	435	4060	27405	142506	593775	2035800	5852925	14307150	30045015	54627300
N31	31	465	4495	31465	169911	736281	2629575	7888725	20160075	44352165	84672315
N32	32	496	4960	35960	201376	906192	3365856	10518300	28048800	64512240	129024480
N33	33	528	5456	40920	237336	1107568	4272048	13884156	38567100	92561040	193536720
N34	34	561	5984	46376	278256	1344904	5379616	18156204	52451256	131128140	286097760
N35	35	595	6545	52360	324632	1623160	6724520	23535820	70607460	183579396	417225900
N36	36	630	7140	58905	376992	1947792	8347680	30260340	94143280	254186856	600805296
N37	37	666	7770	66045	435897	2324784	10295472	38608020	124403620	348330136	854992152
N38	38	703	8436	73815	501942	2760681	12620256	48903492	163011640	472733756	1203322288
N39	39	741	9139	82251	575757	3262623	15380937	61523748	211915132	635745396	1676056044
N40	40	780	9880	91390	658008	3838380	18643560	76904685	273438880	847660528	2311801440
N41	41	820	10660	101270	749398	4496388	22481940	95548245	350343565	1121099408	3159461968
N42	42	861	11480	111930	850668	5245786	26978328	118030185	445891810	1471442973	4280561376
N43	43	903	12341	123410	962598	6096454	32224114	145008513	563921995	1917334783	5752004349
N44	44	946	13244	135751	1086008	7059052	38320568	177232627	708930508	2481256778	7669339132
N45	45	990	14190	148995	1221759	8145060	45379620	215553195	886163135	3190187286	10150595910
N46	46	1035	15180	163185	1370754	9366819	53524680	260932815	1101716330	4076350421	13340783196
N47	47	1081	16215	178365	1533939	10737573	62891499	314457495	1362649145	5178066751	17417133617
N48	48	1128	17296	194580	1712304	12271512	73629072	377348994	1677106640	6540715896	22595200368
N49	49	1176	18424	211876	1906884	13983816	85900584	450978066	2054455634	8217822536	29135916264
N50	50	1225	19600	230300	2118760	15890700	99884400	536878650	2505433700	10272278170	37353738800
N51	51	1275	20825	249900	2349060	18009460	115775100	636763050	3042312350	12777711870	47626016970
N52	52	1326	22100	270725	2598960	20358520	133784560	752538150	3679075400	15820024220	60403728840
N53	53	1378	23426	292825	2869685	22957480	154143080	886322710	4431613550	19499099620	76223753060

Ниже приводится исходный текст программы на языке программирования xBase++: массив знаменатель числитель программирование

(C) Расчет числа сочетаний для больших чисел без промежуточного расчета факториалов путем разложения их на простые множители и сокращения, beta-version, rel: 12.06.2013

(C) д.э.н., к.т.н., профессор Луценко Евгений Вениаминович, Россия, Краснодар.

PROCEDURE AppSys

// Рабочий стол остается окном приложения

RETURN

FUNCTION Main()

LOCAL GetList[0], GetOptions, nColor, oMessageBox, oMenuWords, oDlg, ;

oMenuBar,oMenu1,oMenu2,oMenu3,oMenu4,oMenu5,oMenu6,oMenu7,; oMenu3_3

DC_IconDefault(1000)

SET DECIMALS TO 15

SET DATE GERMAN

SET ESCAPE On

SET COLLATION TO SYSTEM // Руссификация

*SET COLLATION TO ASCII // Руссификация

PUBLIC aSay[30], Mess97, Mess98, Mess99 // Массив сообщений отображаемых стадий исполнения (до 30 на экране)

PUBLIC Time_progress, Wsego, oProgress, lOk

PUBLIC nEvery := 100 // Количество корректировок прогресс-бар

g = 0

s = 0

mRegim = 1

@g , 0 DCGROUP oGroup1 CAPTION 'Задайте вариант использования программы:' SIZE 62.0, 7.0

@++s, 2 DCRADIO mRegim VALUE 1 PROMPT 'Расчет одного конкретного значения числа сочетаний из N по M' PARENT oGroup1

@++s, 2 DCRADIO mRegim VALUE 2 PROMPT 'Расчет таблицы значений числа сочетаний для диапазонов N и M' PARENT oGroup1

s = 3

mN1 = 30

mM1 = 2

@++s+0.2,12 DCSAY "Задайте значение N:" EDITPROTECT {||.NOT.mRegim=1} HIDE {||.NOT.mRegim=1} PARENT oGroup1

@ s ,27 DCSAY "" GET mN1 PICTURE "#######" EDITPROTECT {||.NOT.mRegim=1} HIDE {||.NOT.mRegim=1} PARENT oGroup1

@++s+0.2,12 DCSAY "Задайте значение M:" EDITPROTECT {||.NOT.mRegim=1} HIDE {||.NOT.mRegim=1} PARENT oGroup1

@ s ,27 DCSAY "" GET mM1 PICTURE "#######" EDITPROTECT {||.NOT.mRegim=1} HIDE {||.NOT.mRegim=1} PARENT oGroup1

s = 3

N1 = 1

N2 = 30

M1 = 1

M2 = N2

@++s+0.2, 5 DCSAY "Задайте диапазон значений N:" EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

@ s ,27 DCSAY "" GET N1 PICTURE "#######" EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

@ s ,37 DCSAY "" GET N2 PICTURE "#######" EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

@++s+0.2, 5 DCSAY "Задайте диапазон значений M:" EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

@ s ,27 DCSAY "" GET M1 PICTURE "#######" EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

@ s ,37 DCSAY "" GET M2 PICTURE "#######" EDITPROTECT {||.NOT.mRegim=2} HIDE {||.NOT.mRegim=2} PARENT oGroup1

DCGETOPTIONS TABSTOP

DCREAD GUI ;

FIT ;

OPTIONS GetOptions ;

ADDBUTTONS;

MODAL ;

TITLE '(C) Луценко Е.В. Расчет сочетаний для больших чисел'

IF mRegim = 1

oScr := DC_WaitOn()

Mess := {}

IF mN1 <= 21

AADD(Mess, "Число сочетаний из N=# по M=$ по классической формуле с факториалами: С(n,m) = n! / ( m! ( n-m )! ) = "+ALLTRIM(STR(INT(Cf(mN1,mM1)))))

ELSE

AADD(Mess, "Число сочетаний из N=# по M=$ по формуле с факториалами: С(n,m)=n!/(m!(n-m)!) не может быть рассчитано !")

ENDIF

AADD(Mess, "Число сочетаний из N=# по M=$ по алгоритму с сокр.простых множителей: С(n,m) = P(m+1,n)/P(1,n-m) = "+C(mN1,mM1))

AADD(Mess, "где: P(a,b)=a*(a+1)*(a+2)*...*b: произведение целых чисел от a до b с шагом 1")

DC_Impl(oScr)

Mess[1] = STRTRAN(Mess[1], "#", ALLTRIM(STR(mN1,15)))

Mess[1] = STRTRAN(Mess[1], "$", ALLTRIM(STR(mM1,15)))

Mess[2] = STRTRAN(Mess[2], "#", ALLTRIM(STR(mN1,15)))

Mess[2] = STRTRAN(Mess[2], "$", ALLTRIM(STR(mM1,15)))

LB_Warning(Mess, "(C) Луценко Е.В. Расчет числа сочетаний для больших чисел" )

ENDIF

IF mRegim = 2

aStructure := { { "N", "C", 15, 0} }

FOR j=N1 TO N2

FieldName = "M"+ALLTRIM(STR(j,21))

AADD(aStructure, { FieldName, "C", 250, 0 })

NEXT

DbCreate( "Cnm.dbf" , aStructure )

nMax = 0;FOR mn=N1 TO N2;FOR mm=1 TO mn;++nMax;NEXT;NEXT

Mess = 'Расчет числа сочетаний из n по m'

@ 4,5 DCPROGRESS oProgress SIZE 70,1.1 MAXCOUNT nMax COLOR GRA_CLR_CYAN PERCENT EVERY 100

DCREAD GUI TITLE Mess PARENT @oDialog FIT EXIT

oDialog:show()

nTime = 0

CLOSE ALL

USE Cnm EXCLUSIVE NEW

SELECT Cnm

DC_GetProgress(oProgress,0,nMax)

FOR mn = N1 TO N2

APPEND BLANK

FIELDPUT(1, "N"+ALLTRIM(STR(mn,21)))

FOR mm = 1 TO mn

FIELDPUT(1+mm, C(mn,mm))

DC_GetProgress(oProgress, ++nTime, nMax)

NEXT

NEXT

DC_GetProgress(oProgress,nMax,nMax)

oDialog:Destroy()

Mess := {}

AADD(Mess, 'Результаты расчета числа сочетаний C(n,m) в базе данных Cnm.dbf')

AADD(Mess, 'Из-за большой размерности числа в БД Cnm.dbf представлены в текстовом формате')

AADD(Mess, 'Заданием в MS Excel формата ячеек "числовой" они преобразутся в числовой формат')

LB_Warning(Mess, "(C) Луценко Е.В. Расчет числа сочетаний для больших чисел")

ENDIF

CLOSE ALL

RETURN NIL

С(n,m) = n! / (m! (n - m)!) число сочетаний из n по m

FUNCTION Cf(n,m)

RETURN(Fact(n)/(Fact(m)*Fact(n-m)))

С(n,m) = n! / (m! (n - m)!) число сочетаний из n по m для больших чисел без вычисления промежуточных факториалов путем разложения

факториалов на простые множители и их сокращений

С(n,m) = P(m+1,n) / P(1,n-m), где P(a,b) произведение целых чисел от a до b с шагом 1

1. Найти все простые числа меньшие n

2. Сформировать массив чисел числителя

3. Сформировать массив простых сомножителей числителя

4. Сформировать массив чисел знаменателя

5. Сформировать массив простых сомножителей чисел знаменателя

6. Сформировать массив простых сомножителей числителя, не входящих в массив простых сомножителей знаменателя

7. Перемножить массив уникальных простых сомножителей числителя

FUNCTION C(n,m)

1. Найти все простые числа меньшие n, включая 1 и допуская n=1 aPrCh := {} // Массив простых чисел

IF n = 1

AADD(aPrCh, 1)

ELSE

FOR j = 2 TO n

Проверка, является ли j простым числом

Flag = .T.

FOR i=2 TO j-1

IF j=i*INT(j/i) // Делится ли j на i нацело?

Flag = .F.

EXIT

ENDIF

NEXT

IF Flag

AADD(aPrCh, j)

ENDIF

NEXT

ENDIF

* DC_DebugQout( aPrCh )

2. Сформировать массив чисел числителя

aChis := {}

IF m = n

AADD(aChis, 1)

ELSE

IF m < n

FOR j=m+1 TO n

AADD(aChis, j)

NEXT

ENDIF

ENDIF

DC_DebugQout( aChis )

3. Сформировать массив простых сомножителей числителя

aPSChis := {}

FOR i=1 TO LEN(aChis)

***** Разложить число на простые множители

aPrMn := {} // Массив простых множителей числа: Chislo

Chislo = aChis[i]

IF Chislo = 1

AADD(aPrMn,1)

ELSE

Flag = .T.

DO WHILE Flag

FOR j=1 TO LEN(aPrCh)

**** Проверка, делится ли Chislo на простое число из массива aPrCh

Flag = .F.

IF Chislo = aPrCh[j] * INT(Chislo/aPrCh[j])

AADD(aPrMn,aPrCh[j])

Chislo = Chislo/aPrCh[j]

Flag = .T.

EXIT

ENDIF

NEXT

ENDDO

ENDIF

***** Занести простые множители числа aChis[j] в массив простых сомножителей числителя

FOR j=1 TO LEN(aPrMn)

AADD(aPSChis, aPrMn[j])

NEXT

NEXT

* DC_DebugQout( aPSChis )

***** 4. Сформировать массив чисел знаменателя

aZnam := {}

IF m = n

AADD(aZnam, 1)

ELSE

IF m < n

FOR j=1 TO n - m

AADD(aZnam, j)

NEXT

ENDIF

ENDIF

* DC_DebugQout( aZnam )

******* 5. Сформировать массив простых сомножителей чисел знаменателя

aPSZnam := {}

FOR i=1 TO LEN(aZnam)

***** Разложить число на простые множители

aPrMn := {} // Массив простых множителей числа: Chislo

Chislo = aZnam[i]

IF Chislo = 1

AADD(aPrMn,1)

ELSE

Flag = .T.

DO WHILE Flag

FOR j=1 TO LEN(aPrCh)

**** Проверка, делится ли Chislo на простое число из массива aPrCh

Flag = .F.

IF Chislo = aPrCh[j] * INT(Chislo/aPrCh[j])

AADD(aPrMn,aPrCh[j])

Chislo = Chislo/aPrCh[j]

Flag = .T.

EXIT

ENDIF

NEXT

ENDDO

ENDIF

*** Занести простые множители числа aZnam[j] в массив простых сомножителей знаменателя

FOR j=1 TO LEN(aPrMn)

AADD(aPSZnam, aPrMn[j])

NEXT

NEXT

* DC_DebugQout( aPSZnam )

******** 6. Сформировать массив простых сомножителей числителя,

******** не входящих в массив простых сомножителей знаменателя

aPS:= {}

FOR j=1 TO LEN(aPSChis)

Pos = ASCAN(aPSZnam, aPSChis[j])

IF Pos = 0

AADD(aPS, aPSChis[j])

ELSE

aPSZnam[Pos] = 1 // Сокращение простых сомножителей числителя и знаменателя

ENDIF

NEXT

* DC_DebugQout( aPS )

******** 7. Перемножить массив уникальных простых сомножителей числителя и знаменателя

mMulChis = 1

FOR j=1 TO LEN(aPS)

mMulChis = mMulChis * aPS[j]

NEXT

mMulZnam = 1

FOR j=1 TO LEN(aPSZnam)

mMulZnam = mMulZnam * aPSZnam[j]

NEXT

DC_DebugQout( mMulChis, mMulZnam, mMulChis/mMulZnam )

RETURN(ALLTRIM(STR(mMulChis/mMulZnam,250)))

FUNCTION LB_Warning( message, ctitle )

LOCAL aMsg := {}

DEFAULT cTitle TO ''

IF valtype(message) # 'A'

aadd(aMsg,message)

ELSE

aMsg := message

ENDIF

IF LEN(ALLTRIM(cTitle)) > 0

DC_MsgBox( ,,aMsg,cTitle)

ELSE

DC_MsgBox( ,,aMsg,'Универсальная когнитивная аналитическая система "Эйдос-Х++"')

ENDIF

Выводы

Материалы данной статьи могут быть использованы в учебном процессе при преподавании дисциплин: «Алгоритмы и структуры данных», «Дискретная математика», «Численные методы», «Основы статистики и комбинаторики» и других.

Аннотация

АЛГОРИТМ И ПРОГРАММА РАСЧЕТА ЧИСЛА СОЧЕТАНИЙ ДЛЯ БОЛЬШИХ ЧИСЕЛ БЕЗ ВЫЧИСЛЕНИЯ ПРОМЕЖУТОЧНЫХ ФАКТОРИАЛОВ ПУТЕМ ИХ РАЗЛОЖЕНИЯ НА ПРОСТЫЕ МНОЖИТЕЛИ И СОКРАЩЕНИЙ

Луценко Евгений Вениаминович д.э.н., к.т.н., профессор

Кубанский государственный аграрный университет, Россия, 350044, Краснодар, Калинина, 13,

Классическая комбинаторная формула для расчета числа сочетаний из n по m: C(n,m)=n!/(m!(n-m)!) предполагает промежуточный расчет факториалов, что чаще всего невозможно при n>170 из-за ограничений в разрядности чисел, используемых в языках программирования и созданных помощью них системах. Однако, в ряде случаев необходимо произвести расчет числа сочетаний при n и m значительно превосходящих это ограничение, например при их значениях больше 10000. В подобных случаях возникает определенная проблема, проявляющаяся, например в том, что многие on-line сервисы по расчету числа сочетаний при таких параметрах не работают. В данной статье предлагается ее решение в виде алгоритма и программной реализации. Суть подхода состоит в том, чтобы сначала разложить факториалы на простые множители и сократить их, а уже потом уже производить умножения. Этот подход отличается от приводимых в Internet

Ключевые слова: АВТОМАТИЗИРОВАННЫЙ СИСТЕМНО-КОГНИТИВНЫЙ АНАЛИЗ, ИНТЕЛЛЕКТУАЛЬНАЯ СИСТЕМА «ЭЙДОС», ЧИСЛО СОЧЕТАНИЙ ИЗ N ПО M ДЛЯ БОЛЬШИХ ЧИСЕЛ

AN ALGORITHM AND A PROGRAM FOR CALCULATING THE NUMBER OF COMBINATIONS FOR LARGE NUMBERS WITHOUT CALCULATING THE INTERMEDIATE FACTORIALS BY THEIR DECOMPOSITION INTO PRIME FACTORS AND ABBREVIATIONS

Lutsenko Evgeny Veniaminovich Dr.Sci.Econ., Cand.Tech.Sci., professor

Kuban State Agrarian University, Krasnodar, Russia

Classical combinatorial formula to calculate the number of combinations from n on m: C(n,m)=n!/(m!(n-m)!) involves the intermediate calculation of factorials, which is often impossible when n>170, due to limitations in the capacity of numbers that are used in programming languages and created through these systems. However, in some cases it is necessary to calculate the number of combinations for n and m much larger than this limit, such as when a value greater than 10000. In such cases, there is a definite problem, which manifests itself, for example in the fact that many on-line services meant to calculate the number of combinations with these parameters do not work properly. In this article, we present its solution in the form of an algorithm and software implementation. The essence of the approach is to first decompose the factorials into prime factors and reduce them, and then to produce multiplication. This approach differs from those cited in the Internet

Keywords: AUTOMATED SYSTEM-COGNITIVE ANALYSIS, "EIDOS" INTELLECTUAL SYSTEM, NUMBER OF COMBINATIONS FROM N ON M FOR LARGE NUMBERS

Размещено на Allbest.ru

...