Combinații posibile. Elemente de combinatorie
O combinație este o selecție neordonată de elemente dintr-o mulțime finită cu un număr fix și fără repetări de elemente. Combinațiile diferite trebuie să difere în cel puțin un element, iar ordinea elementelor nu contează. De exemplu, din setul tuturor vocalelor literelor latine (AEIOU), puteți face 10 combinații diferite de 3 litere, formând următoarele triplete neordonate:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Este interesant de observat că din aceleași cinci litere puteți obține și 10 combinații diferite dacă le combinați câte 2 litere odată, formând următoarele perechi neordonate:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Cu toate acestea, dacă combinați aceeași vocală litere latine cu 4, veți obține doar următoarele 5 combinații diferite:
AEIO, AEIU, AIOU, EIOU, AEOU.
În general, pentru a desemna numărul de combinații de n elemente diferite ale m elemente, se utilizează următorul simbolism funcțional, index sau vectorial (Appel):
Indiferent de forma de notație, numărul de combinații de n elemente cu m elemente poate fi determinat folosind următoarele formule multiplicative și factoriale:
Este ușor de verificat că rezultatul calculelor folosind aceste formule coincide cu rezultatele exemplului discutat mai sus cu combinații de vocale cu litere latine. În special, cu n=5 și m=3, calculele folosind aceste formule vor da următorul rezultat:
În cazul general, formulele pentru numărul de combinații au o semnificație combinatorie și sunt valabile pentru orice valori întregi ale lui n și m, astfel încât n > m > 0. Dacă m > n și m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
În plus, este util să ne amintim următoarele numere limită de combinații, care pot fi verificate cu ușurință prin substituție directă în formulele multiplicative și factoriale:
De asemenea, trebuie menționat că formula multiplicativă rămâne valabilă chiar și atunci când n este un număr real, atâta timp cât m este încă o valoare întreagă. Totuși, atunci rezultatul calculului folosindu-l, păstrând valabilitatea formală, își pierde sensul combinatoriu.
IDENTITATILE COMBINARILOR
Utilizarea practică a formulelor multiplicative și factoriale pentru a determina numărul de combinații pentru valorile arbitrare ale lui n și m se dovedește a fi de o productivitate redusă datorită creșterii exponențiale a produselor factoriale ale numărătorului și numitorului lor. Chiar și pentru valori relativ mici de n și m, aceste produse depășesc adesea capacitățile de reprezentare a numerelor întregi în sistemele moderne de calcul și software. În plus, valorile lor se dovedesc a fi semnificativ mai mari decât valoarea rezultată a numărului de combinații, care poate fi relativ mică. De exemplu, numărul de combinații de n=10 cu m=8 elemente este de numai 45. Cu toate acestea, pentru a găsi această valoare folosind formula factorială, trebuie mai întâi să calculați valori mult mai mari de 10! la numărător și 8! la numitor:
Pentru a elimina operațiunile consumatoare de timp pentru prelucrarea cantităților mari, pentru a determina numărul de combinații, puteți utiliza diverse relații de recurență, care decurg direct din formulele multiplicative și factoriale. În special, următoarea relație de recurență decurge din formula multiplicativă, care ne permite să luăm raportul indicilor săi dincolo de semnul numărului de combinații:
În cele din urmă, menținerea constantă a indicelui oferă următoarea relație de recurență, care este ușor de obținut din formula factorială pentru numărul de combinații:
După transformări elementare, cele trei relații de recurență rezultate pot fi reprezentate în următoarele forme:
Dacă acum adăugăm părțile stânga și dreaptă ale primelor 2 formule și reducem rezultatul cu n, obținem o relație de recurență importantă, care se numește identitatea adunării numerelor combinate:
Identitatea de adunare oferă o regulă de recurență de bază pentru determinarea eficientă a numărului de combinații pentru valorile mari ale lui n și m, deoarece permite ca operațiile de înmulțire în produse factoriale să fie înlocuite cu operațiuni de adunare mai simple și pentru un număr mai mic de combinații. În special, folosind identitatea de adăugare, este acum ușor să se determine numărul de combinații de n=10 cu m=8 elemente, care a fost discutat mai sus, prin efectuarea următoarei secvențe de transformări recurente:
În plus, mai multe relații utile pentru calcularea sumelor finite pot fi derivate din identitatea de adunare, în special, formula de însumare prin indice, care are următoarea formă:
Această relație se obține dacă în identitatea de adunare extindem recurența de-a lungul termenului cu cel mai mare indice, în timp ce indicele acestuia este mai mare decât 0. Următorul exemplu numeric ilustrează acest proces de transformări recurente:
Formula de însumare a indicelui este adesea folosită pentru a calcula suma puterilor numerelor naturale. În special, presupunând m=1, folosind această formulă este ușor de găsit suma primelor n numere ale seriei naturale:
O altă versiune utilă a formulei de însumare poate fi obținută prin extinderea recurenței identității de adunare de-a lungul termenului cu cel mai mic superscript. Următorul exemplu numeric ilustrează această versiune a transformărilor recurente:
În cazul general, în urma unor astfel de transformări, se obține suma numerelor de combinații, a căror ambii indici diferă cu unul de termenii vecini, iar diferența de indici rămâne constantă (în exemplul luat în considerare, este de asemenea egal cu unu). Astfel, obținem următoarea formulă de însumare pentru ambii indici ai numerelor combinate:
Pe lângă relațiile de recurență și formulele de însumare discutate mai sus, multe alte identități utile pentru numerele combinate au fost obținute în analiza combinatorie. Cel mai important dintre ele este identitate de simetrie, care arată astfel:
Valabilitatea identităţii de simetrie poate fi verificată în exemplul următor prin compararea numărului de combinaţii de 5 elemente cu 2 şi prin (5 2) = 3:
Identitatea de simetrie are o semnificație combinatorică evidentă, întrucât, prin determinarea numărului de opțiuni de selectare a m elemente din n elemente, stabilește simultan și numărul de combinații din restul (nm) elemente neselectate. Simetria indicată se obține imediat prin înlocuirea m cu (nm) în formula factorială pentru numărul de combinații:
Numerele și identitățile combinate sunt utilizate pe scară largă în diferite domenii ale matematicii computaționale moderne. Cu toate acestea, cele mai populare aplicații ale lor sunt legate de binomul lui Newton și triunghiul lui Pascal.
TEOREMA BIOMIALĂ
Pentru a efectua diverse transformări și calcule matematice, este important să poți reprezenta orice putere naturală a unui binom algebric (binom) sub forma unui polinom. Pentru puteri mici, polinomul dorit poate fi obținut ușor prin înmulțirea directă a binoamelor. În special, următoarele formule pentru pătratul și cubul sumei a doi termeni sunt bine cunoscute din cursul de matematică elementară:
În cazul general, pentru un grad arbitrar n al unui binom, reprezentarea necesară sub formă de polinom este oferită de teorema binomului lui Newton, care declară următoarea egalitate ca fiind adevărată:
Această egalitate este de obicei numită binomul lui Newton. Polinomul din partea sa dreaptă este format din suma produselor a n termeni X și Y ai binomului din stânga, iar coeficienții din fața lor se numesc binomi și sunt egali cu numărul de combinații cu indici, care sunt obținute din puterile lor. Având în vedere popularitatea deosebită a formulei binomiale a lui Newton în analiza combinatorie, termenii coeficient binomial și număr de combinații sunt în general considerați sinonimi.
În mod evident, formulele sumei pătrate și cube sunt cazuri speciale ale teoremei binomiale pentru n=2 și, respectiv, n=3. Pentru a gestiona grade mai mari (n>3), trebuie utilizată formula binomială a lui Newton. Aplicația sa pentru un binom de gradul al patrulea (n=4) este demonstrată de următorul exemplu:
Trebuie remarcat faptul că formula binomială era cunoscută chiar înainte de Newton de matematicienii medievali din estul arab și din Europa de Vest. Prin urmare, numele său general acceptat nu este corect din punct de vedere istoric. Meritul lui Newton este că a generalizat această formulă în cazul unui exponent real arbitrar r, care poate lua orice valori raționale și iraționale pozitive sau negative. În cazul general, o astfel de formulă binomială Newton are o sumă infinită pe partea dreaptă și este de obicei scrisă după cum urmează:
De exemplu, cu o valoare fracțională pozitivă a exponentului r=1/2, ținând cont de valorile coeficienților binomi, se obține următoarea expansiune:
În cazul general, formula binomială a lui Newton pentru orice exponent este o versiune specială a formulei lui Maclaurin, care oferă extinderea unei funcții arbitrare într-o serie de puteri. Newton a arătat că pentru |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Dacă acum setăm Z=X/Y și înmulțim părțile stânga și dreaptă cu Yn, obținem o versiune a formulei binomului Newton discutată mai sus.
În ciuda universalității sale, teorema binomului își păstrează sensul combinatoriu numai pentru puterile întregi nenegative ale binomului. În acest caz, poate fi folosit pentru a demonstra mai multe identități utile pentru coeficienții binomi. În special, formulele de însumare a numerelor de combinații după indice și după ambii indici au fost discutate mai sus. Identitatea de însumare a superscriptului lipsă poate fi obținută cu ușurință din formula binomială a lui Newton punând X = Y = 1 sau Z = 1 în ea:
O altă identitate utilă stabilește egalitatea sumelor coeficienților binomi cu numerele pare și impare. Se obține imediat din formula binomială a lui Newton dacă X = 1 și Y = 1 sau Z = 1:
În cele din urmă, din ambele identități considerate obținem identitatea sumei coeficienților binomi cu numai numere pare sau doar impare:
Pe baza identităților considerate și a regulii recurente de eliminare a indicilor de sub semnul numărului de combinații, se pot obține o serie de relații interesante. De exemplu, dacă în formula de însumare a indicelui înlocuim n peste tot cu (n1) și eliminăm indicii din fiecare termen, obținem următoarea relație:
Folosind o tehnică similară în formula pentru suma coeficienților binomi cu numere pare și impare, este posibil să se demonstreze validitatea, de exemplu, a următoarei relații:
O altă identitate utilă vă permite să calculați cu ușurință suma produselor coeficienților binomi situati simetric a două binoame de grade arbitrare n și k folosind următoarea formulă Cauchy:
Valabilitatea acestei formule rezultă din egalitatea necesară a coeficienților pentru orice grad m al variabilei Z de pe părțile din stânga și din dreapta următoarei relații identice:
În cazul special când n=k=m, ținând cont de identitatea simetriei, se obține o formulă mai populară pentru suma pătratelor coeficienților binomi:
Multe alte identități utile pentru coeficienții binomii pot fi găsite în literatura extinsă despre analiza combinatorie. Cu toate acestea, cea mai faimoasă aplicație practică a acestora este legată de triunghiul lui Pascal.
TRIANGUL LUI PASCAL
Triunghiul aritmetic al lui Pascal formează un tabel numeric infinit format din coeficienți binomi. Liniile sale sunt ordonate după puteri ale binomurilor de sus în jos. În fiecare linie, coeficienții binomi sunt aranjați în ordinea crescătoare a superindicelor numerelor de combinație corespunzătoare de la stânga la dreapta. Triunghiul lui Pascal este de obicei scris fie sub formă isoscelă, fie dreptunghiulară.
Mai vizual și mai comun este formatul isoscel, unde coeficienții binomi, eșalonați, formează un triunghi isoscel infinit. Fragmentul său inițial pentru binoame până la gradul 4 (n=4) are următoarea formă:
În general, triunghiul isoscel al lui Pascal oferă o regulă geometrică convenabilă pentru determinarea coeficienților binomi, care se bazează pe identitățile adunării și simetria combinațiilor de numere. În special, conform identității de adunare, orice coeficient binom este suma celor doi coeficienți ai rândului anterior cel mai apropiat de acesta. Conform identității simetriei, triunghiul isoscel al lui Pascal este simetric față de bisectoarea sa. Astfel, fiecare dintre liniile sale este un palindrom numeric de coeficienți binomi. Caracteristicile algebrice și geometrice indicate fac posibilă extinderea cu ușurință a triunghiului isoscel al lui Pascal și găsirea constantă a valorilor coeficienților binomi ai puterilor arbitrare.
Cu toate acestea, pentru a studia diferite proprietăți ale triunghiului lui Pascal, este mai convenabil să folosiți formatul dreptunghiular mai strict formal. În acest format, este specificat de o matrice triunghiulară inferioară de coeficienți binomi, unde formează un triunghi dreptunghic infinit. Fragmentul inițial al triunghiului dreptunghic al lui Pascal pentru binoamele până la gradul 9 (n=9) are următoarea formă:
Geometric, o astfel de masă dreptunghiulară se obține prin deformarea orizontală a triunghiului isoscel al lui Pascal. Ca rezultat, seria numerică paralelă cu laturile laterale ale triunghiului isoscel al lui Pascal se transformă în verticale și diagonale ale triunghiului dreptunghic al lui Pascal, iar liniile orizontale ale ambelor triunghiuri coincid. În același timp, regulile de adunare și simetrie a coeficienților binomi rămân valabile, deși triunghiul dreptunghic al lui Pascal își pierde simetria vizuală caracteristică omologul său isoscel. Pentru a compensa acest lucru, devine mai convenabil să analizăm în mod formal diferitele proprietăți numerice ale coeficienților binomi pentru orizontale, verticale și diagonale ale triunghiului dreptunghic al lui Pascal.
Începând cu analiza orizontalelor triunghiului dreptunghic al lui Pascal, este ușor de observat că suma elementelor oricărui rând cu număr n este egală cu 2n conform formulei de însumare a binoamelor prin superscript. Rezultă de aici că suma elementelor de deasupra oricăreia dintre liniile orizontale cu număr n este egală cu (2 n 1). Acest rezultat devine destul de evident dacă valoarea sumei elementelor fiecărei orizontale este scrisă în sistemul numeric binar. De exemplu, pentru n=4 această adunare poate fi scrisă după cum urmează:
Iată câteva proprietăți interesante ale orizontalelor care sunt, de asemenea, legate de puterile a doi. Se dovedește că dacă numărul orizontal este o putere a doi (n=2 k), atunci toate elementele sale interne (cu excepția celor exterioare) sunt numere pare. Dimpotrivă, toate numerele unei linii orizontale vor fi impare dacă numărul ei este cu unu mai mic decât o putere de doi (n=2 k 1). Valabilitatea acestor proprietăți poate fi verificată prin verificarea parității coeficienților binomi interni, de exemplu, în orizontale n=4 și n=3 sau n=8 și n=7.
Fie acum numărul de rând al triunghiului dreptunghic al lui Pascal un număr prim p. Atunci toți coeficienții săi binomi interni sunt divizibili cu p. Această proprietate este ușor de verificat pentru valori mici ale numerelor de contur prime. De exemplu, toți coeficienții binomi interni ai celei de-a cincea orizontale (5, 10 și 5) sunt în mod evident divizibili cu 5. Pentru a demonstra acest rezultat pentru orice număr prim orizontal p, trebuie să scrieți formula multiplicativă pentru coeficienții săi binomi după cum urmează:
Deoarece p este un număr prim și, prin urmare, nu este divizibil cu m!, produsul factorilor rămași ai numărătorului acestei formule trebuie să fie divizibil cu m! pentru a garanta o valoare întreagă a coeficientului binomial. Rezultă că raportul dintre paranteze drepte este un număr natural N și rezultatul dorit devine evident:
Folosind acest rezultat, putem stabili că numerele tuturor liniilor orizontale ale triunghiului lui Pascal, ale căror elemente interne sunt divizibile cu un număr prim dat p, sunt puteri ale lui p, adică au forma n=p k. În special, dacă p=3, atunci numărul prim p împarte nu numai toate elementele interne ale rândului 3, așa cum s-a stabilit mai sus, ci, de exemplu, a 9-a orizontală (9, 36, 84 și 126). Pe de altă parte, în triunghiul lui Pascal este imposibil să găsim o linie orizontală ale cărei elemente interne sunt toate divizibile cu un număr compus. În caz contrar, numărul unei astfel de linii orizontale trebuie să fie simultan o putere a divizorilor primi ai numărului compus prin care sunt împărțite toate elementele sale interne, dar acest lucru este imposibil din motive evidente.
Considerațiile luate în considerare ne permit să formulăm următorul criteriu general de divizibilitate a elementelor orizontale ale triunghiului lui Pascal. Cel mai mare divizor comun (GCD) al tuturor elementelor interne ale oricărei linii orizontale a triunghiului lui Pascal cu numărul n este egal cu numărul prim p dacă n=pk sau 1 în toate celelalte cazuri:
GCD(Cmn) = ( ) pentru orice 0< m < n .
În încheierea analizei orizontalelor, merită luată în considerare încă o proprietate interesantă pe care o au seria de coeficienți binomi care le formează. Dacă coeficienții binomi ai oricărei linii orizontale cu numărul n sunt înmulțiți cu puterile succesive ale numărului 10 și apoi se adună toate aceste produse, rezultatul este 11 n. Justificarea formală a acestui rezultat este înlocuirea valorilor X=10 și Y=1 (sau Z=1) în formula binomială Newton. Următorul exemplu numeric ilustrează îndeplinirea acestei proprietăți pentru n=5:
Analiza proprietăților verticalelor triunghiului dreptunghic al lui Pascal poate începe cu studiul caracteristicilor individuale ale elementelor lor constitutive. Formal, fiecare m verticală este format din următoarea succesiune infinită de coeficienți binomi cu un indice constant (m) și un increment al indicelui:
Evident, când m=0 se obține o succesiune de uni, iar când m=1 se formează o serie de numere naturale. Când m=2 verticala este formată din numere triunghiulare. Fiecare număr triunghiular poate fi reprezentat într-un plan sub forma unui triunghi echilateral, care este umplut cu obiecte arbitrare (nuclee) aranjate într-un model de șah. În acest caz, valoarea fiecărui număr triunghiular T k determină numărul de nuclee reprezentative, iar indicele arată câte rânduri de nuclee sunt necesare pentru a-l reprezenta. De exemplu, 4 numere triunghiulare inițiale reprezintă următoarele configurații ale numărului corespunzător de simboluri nucleare „@”:
De remarcat că în mod similar se pot introduce în considerare numere pătrate S k , care se obțin prin pătrarea numerelor naturale și, în general, numere figurate poligonale formate prin umplerea regulată a poligoanelor regulate. În special, cele 4 numere pătrate inițiale pot fi reprezentate după cum urmează:
Revenind la analiza verticalelor triunghiului lui Pascal, putem observa că următoarea verticală la m=3 este umplută cu numere tetraedrice (piramidale). Fiecare astfel de număr P k specifică numărul de nuclee care pot fi aranjate în formă de tetraedru, iar indicele determină câte straturi triunghiulare orizontale de rânduri de nuclee sunt necesare pentru a-l reprezenta în spațiul tridimensional. În acest caz, toate straturile orizontale trebuie reprezentate ca numere triunghiulare succesive. Elementele următoarelor verticale ale triunghiului lui Pascal pentru m>3 formează serii de numere hipertetraedale, care nu au o interpretare geometrică vizuală în plan sau în spațiul tridimensional, dar corespund formal analogilor multidimensionali ai numerelor triunghiulare și tetraedice.
Deși seria numerică verticală a triunghiului lui Pascal are trăsăturile de formă individuale considerate, pentru ele este posibil să se calculeze sumele parțiale ale valorilor elementelor inițiale în același mod, folosind formula de însumare a numerelor de combinații prin indice. . În triunghiul lui Pascal, această formulă are următoarea interpretare geometrică. Suma valorilor celor n coeficienți binomi superiori ai oricărei verticale este egală cu valoarea elementului următoarei verticale, care se află o linie mai jos. Acest rezultat este, de asemenea, în concordanță cu structura geometrică a numerelor triunghiulare, tetraedrice și hipertetraedrice, deoarece reprezentarea fiecărui astfel de număr constă din straturi de bază care reprezintă numere de ordin inferior. În special, al n-lea număr triunghiular Tn poate fi obținut prin însumarea tuturor numerelor naturale reprezentând straturile sale liniare:
În mod similar, nu este dificil să găsiți numărul tetraedric Pn calculând următoarea sumă a primelor n numere triunghiulare care formează straturile sale de miez orizontale:
Pe lângă orizontale și verticale din triunghiul dreptunghic al lui Pascal, se pot urmări șiruri diagonale de elemente, studiul proprietăților cărora prezintă, de asemenea, un anumit interes. În acest caz, se face de obicei o distincție între diagonalele descendente și ascendente. Diagonalele în jos sunt paralele cu ipotenuza triunghiului dreptunghic al lui Pascal. Ele sunt formate din serii de coeficienți binomi cu o creștere a ambilor indici. Datorită identității simetriei, diagonalele descendente coincid în valorile elementelor lor cu rândurile verticale corespunzătoare ale triunghiului lui Pascal și, prin urmare, își repetă toate proprietățile discutate mai sus. Corespondența indicată poate fi urmărită prin coincidența valorilor elementelor diagonalei descendente și ale verticalei cu orice număr n, dacă nu se iau în considerare zerourile verticale:
Diagonalele crescătoare formează o serie de numere geometric perpendicular pe ipotenuza triunghiului dreptunghic al lui Pascal. Ele sunt umplute cu coeficienți binomi cu o scădere a celui mai mic și o creștere a superscriptului. În special, cele 7 diagonale ascendente superioare formează următoarea secvență numerică fără a lua în considerare zerourile finale:
În general, numărul diagonal ascendent n conține următorii coeficienți binomi, suma indicilor fiecăruia dintre care este egală cu (n1):
În virtutea identității de adunare pentru numere de combinație, fiecare element diagonal este egal cu suma a două elemente corespondente în indici din cele două diagonale ascendente anterioare. Acest lucru permite ca fiecare diagonală ascendentă ulterioară să fie construită prin însumarea în perechi a elementelor orizontale adiacente din cele două diagonale anterioare, extinzând infinit triunghiul lui Pascal de-a lungul diagonalei. Următorul fragment din triunghiul lui Pascal ilustrează construcția unei diagonale ascendente cu numărul 8 de-a lungul diagonalelor numerotate 6 și 7:
Cu această metodă de construcție, suma elementelor oricărei diagonale ascendente, începând de la a 3-a, va fi egală cu suma elementelor celor două diagonale ascendente anterioare, iar primele 2 diagonale constau dintr-un singur element, valoarea dintre care este 1. Rezultatele calculelor corespunzătoare formează următoarea serie numerică, conform căreia puteți verifica validitatea proprietății luate în considerare a diagonalelor ascendente ale triunghiului dreptunghic al lui Pascal:
Analizând aceste numere, puteți vedea că, conform unei legi similare, se formează binecunoscuta succesiune de numere Fibonacci, în care fiecare număr următor este egal cu suma celor două anterioare, iar primele două numere sunt egale cu 1:
Astfel, putem trage următoarea concluzie importantă: sumele diagonale ale elementelor triunghiului lui Pascal constituie șirul Fibonacci. Această proprietate ne permite să stabilim o altă caracteristică interesantă a triunghiului lui Pascal. Expandând recursiv formula Fibonacci, este ușor de demonstrat că suma primelor n numere Fibonacci este egală cu (F n+2 1).
Prin urmare, suma coeficienților binomi care umplu n diagonalele superioare este de asemenea egală cu (F n+2 1). Rezultă că suma primelor n diagonale ale triunghiului lui Pascal este cu 1 mai mică decât suma coeficienților binomi care stau pe diagonala sa cu numărul (n+2).
În concluzie, trebuie menționat că proprietățile considerate ale orizontalelor, verticalelor și diagonalelor triunghiului lui Pascal nu epuizează uriașa varietate de posibilități care leagă între ele diverse aspecte matematice care la prima vedere nu au nimic în comun. Astfel de proprietăți neobișnuite ne permit să considerăm triunghiul lui Pascal unul dintre cele mai perfecte sisteme numerice, ale cărui capacități nu pot fi enumerate și sunt greu de supraestimat.
Algoritmul pentru calcularea numărului de combinații folosind triunghiul lui Pascal este prezentat mai jos:
Funcție privată SochTT (ByVal n ca întreg, ByVal k ca întreg) Ca dublu Dim i Ca întreg Dim j Ca întreg Dim TT () Ca dublu ReDim TT (n, k) Pentru i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Următorul Pentru i = 2 To n Pentru j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Următorul Următorul SochTT = TT (n, k) End Function
Dacă trebuie să calculați numărul de combinații de mai multe ori, atunci poate fi mai convenabil să construiți triunghiul lui Pascal o dată și apoi să primiți date din matrice.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n Ca Integer, ByVal k Ca Integer) Ca Double If n > Ubound (TT) Apoi BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start Ca Integer, ByVal final Ca Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (sfârșit, sfârșit) Pentru i = început Pentru a sfârșit TT (0, i) = 1 TT (i, i) = 1 Următorul Dacă sfârșit< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Mai întâi trebuie să apelați procedura CreateTT. Puteți obține apoi numărul de combinații folosind funcția SochTT. Când nu mai aveți nevoie de triunghi, apelați procedura TerminateTT. În codul de mai sus, la apelarea funcției SochTT, dacă triunghiul nu a fost încă finalizat la nivelul necesar, atunci acesta este finalizat folosind procedura BuildTT. Funcția primește apoi elementul dorit al matricei TT și îl returnează.
Dim X () Ca Integer Dim Contor () Ca Integer Dim K Ca Integer Dim N Ca Integer Public Sub Soch() Dim i Ca Integer N = CInt(InputBox("Introduceti N")) K = CInt(InputBox("Introduceti K) ")) K = K + 1 ReDim X(N) Pentru i = 1 To N X(i) = i Următorul txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Ca Integer) Dim i Ca Integer Dim j Ca Integer Dim n1 Ca Integer Dim Out() Ca Integer Dim X1() Ca Integer Daca c = K Atunci ReDim Out(K) X1 = X Pentru i = 1 La K - 1 n1 = 0 Pentru j = 1 La N Dacă X1(j)<>0 Atunci n1 = n1 + 1 Dacă n1 = Counter(i) Atunci Out(i) = X1(j) X1(j) = 0 Exit For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
LISTAREA COMBINAȚILOR DE NUMERE NATURALE
Pentru a rezolva multe probleme practice, este necesar să se enumere toate combinațiile de cardinalitate fixă care pot fi obținute din elementele unei mulțimi finite date și nu doar să se determine numărul acestora. Ținând cont de posibilitatea mereu existentă de numerotare întregă a elementelor oricărei mulțimi finite, în majoritatea cazurilor este permis să ne limităm la utilizarea algoritmilor pentru enumerarea combinațiilor de numere naturale. Cel mai natural și simplu dintre ele este algoritmul de enumerare a combinațiilor de numere naturale în ordine lexigrafică.
Pentru a descrie oficial acest algoritm, este convenabil să presupunem că mulțimea principală, toate combinațiile de m elemente ale cărora trebuie enumerate, formează numere naturale consecutive de la 1 la n. Apoi orice combinație de m Ca urmare a ordonării, valoarea în fiecare poziție a unui astfel de vector de combinații se dovedește în mod natural a fi limitată ca valoare de sus și de jos, după cum urmează: Algoritmul lexigrafic generează secvenţial astfel de vectori de combinaţie, începând cu cel mai mic vector din punct de vedere lexigrafic, unde toate poziţiile conţin următoarele valori minime posibile ale elementelor egale cu indicii lor: Fiecare vector de combinație succesiv este format din cel curent după scanarea elementelor sale de la stânga la dreapta pentru a găsi elementul din dreapta care nu și-a atins încă valoarea limită: Valoarea unui astfel de element ar trebui să fie mărită cu 1. Fiecărui element din dreapta acestuia ar trebui să i se atribuie cea mai mică valoare posibilă, care este cu 1 mai mare decât vecinul său din stânga. După aceste modificări, următorul vector de combinații va avea următoarea compoziție elementară: Astfel, următorul vector de combinație va fi lexigrafic mai mare decât cel anterior, deoarece valorile elementelor lor inițiale (j1) sunt egale ca valoare, iar valoarea elementului din poziția j este cu 1 mai mare decât cea a celui precedent. . Relația specificată de ordine lexigrafică crescătoare este garantată a fi satisfăcută la toate iterațiile algoritmului. Rezultatul este o secvență lexigrafică crescătoare, care este completată de cel mai mare vector de combinație lexigrafic, unde elementele din toate pozițiile au următoarele valori maxime: Algoritmul lexigrafic considerat este ilustrat de următorul exemplu, în care este necesar să se enumere în ordine lexigrafică crescătoare toate cele 15 combinații de n=6 primele numere naturale prin m=4 numere, adică toate submulțimile posibile de 4 elemente ale generatorului principal. set (1, 2, 3, 4, 5, 6) din 6 elemente. Rezultatele calculului sunt prezentate în următorul tabel: În acest exemplu, cele mai mari valori admise ale numerelor în pozițiile vectorilor de combinație sunt, respectiv, 3, 4, 5 și 6. Pentru ușurința interpretării rezultatelor, în fiecare vector de combinație, elementul din dreapta, care are nu a atins încă valoarea maximă, se subliniază. Indicii numerici ai vectorilor combinați determină numerele lor în ordine lexigrafică. În cazul general, numărul lexigrafic N al oricărei combinații de n elemente prin m poate fi calculat folosind următoarea formulă, unde, din motive cosmetice, simbolismul Appel este folosit pentru a desemna numărul de combinații: În special, următoarele calcule folosind această formulă pentru numărul de combinație (1, 3, 4, 6) de n=6 elemente ale lui m=4 în ordine lexigrafică vor da rezultatul N=8, care corespunde exemplului discutat mai sus: În cazul general, folosind identitatea pentru suma numerelor de combinații pentru ambii indici, este posibil să se arate că numărul celei mai mici combinații lexigrafic (1, ... i, ... m) atunci când este calculat folosind acest formula va fi întotdeauna egală cu 1: De asemenea, este evident că numărul celei mai mari combinații lexigrafice (m, … nm+i, … n) atunci când este calculat folosind această formulă va fi egal cu numărul de combinații de n elemente prin m: Formula pentru calcularea numerelor de combinație lexigrafică poate fi utilizată pentru a rezolva problema inversă, în care trebuie să determinați vectorul de combinație după numărul său în ordine lexigrafică. Pentru a rezolva o astfel de problemă inversă, trebuie scrisă sub forma unei ecuații, în care toate valorile necunoscute ale elementelor vectorului combinației dorite (C 1, ... C i, ... C m ) sunt concentrate în numerele de combinații ale părții sale drepte, iar diferența cunoscută L a numărului de combinații se scrie pe partea stângă a n elemente fiecare m și numărul combinației necesare N: Rezolvarea acestei ecuații este oferită de următorul algoritm „lacom”, în timpul repetărilor căruia valorile elementelor vectorului combinației dorite sunt selectate succesiv. La iterația inițială, este selectată valoarea minimă posibilă (în limitele sale) a lui C 1, la care primul termen din partea dreaptă va avea o valoare maximă care nu depășește L: Acum partea stângă a lui L ar trebui să fie redusă cu primul număr de combinații din partea dreaptă cu valoarea selectată a lui C 1 și, în mod similar, să se determine valoarea lui C 2 la a doua iterație: În mod similar, toate iterațiile ulterioare ar trebui efectuate pentru a selecta valorile tuturor celorlalte elemente C i ale combinației dorite, până la ultimul element C m: Din motive evidente, valoarea ultimului element C m poate fi determinată pe baza egalității numărului său de combinații cu valoarea reziduală a părții stângi a lui L: De remarcat că valoarea ultimului element al combinației C m poate fi găsită și mai simplu, fără a enumera posibilele sale valori: Implementarea iterațiilor algoritmului considerat este ilustrată de următorul exemplu, unde este necesar să se determine combinații cu numărul N=8 în ordine lexigrafică, dacă n=6 și m=4: Abilitatea algoritmică de a determina o combinație cu un număr dat în ordine lexigrafică poate fi utilizată în diferite direcții. În special, la enumerarea combinațiilor în ordine lexigrafică, este necesar să se asigure o revenire la orice combinație care a fost obținută anterior, este suficient să cunoaștem doar numărul acesteia. În plus, devine posibilă generarea de combinații în orice ordine, care este reglementată de o succesiune dată arbitrar a numerelor lor lexigrafice. Acum prezentăm un algoritm pentru generarea de combinații în ordine lexicografică: 2 pentru i:= 1 la k face A[i] := i; 5 începe să scrie (A, …, A[k]); 6 dacă A[k] = n atunci p:= p 1 altfel p:= k; 8 pentru i:= k jos până la p face A[i] := A[p] + i p + 1 COMBINAȚII CU ELEMENTE REPETARE Spre deosebire de o combinație clasică, în care toate elementele sunt diferite, o combinație cu repetări formează o selecție neordonată de elemente dintr-o mulțime finită, unde orice element poate apărea la nesfârșit frecvent și nu este neapărat prezent într-o singură copie. În acest caz, numărul de repetări ale elementelor este de obicei limitat doar de lungimea combinației, iar combinațiile care diferă în cel puțin un element sunt considerate diferite. De exemplu, alegând opțional 4 numere diferite din setul 1, 2 și 3, puteți crea următoarele 15 combinații cu repetări: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
În general, combinațiile cu repetări se pot forma prin selectarea a n elemente de tipuri arbitrare. Cu toate acestea, ele pot fi întotdeauna asociate cu numere naturale consecutive de la 1 la n. Apoi orice combinație de m numere opțional diferite din acest interval poate fi scrisă în formă vectorială, aranjandu-le în ordine nedescrescătoare de la stânga la dreapta: Desigur, cu această formă de notație, orice elemente învecinate pot fi egale datorită posibilității de repetări nelimitate. Cu toate acestea, fiecare vector de combinație cu repetiții de n elemente de m poate fi asociat cu un vector de combinație de (n+m−1) elemente de m, care este construit după cum urmează: Este clar că pentru orice valoare a elementelor vectorului f, elementele vectorului C sunt garantate a fi diferite și strict ordonate în ordinea crescătoare a valorilor lor din intervalul de la 1 la (n+m1) : Prezența unei corespondențe unu-la-unu între elementele vectorilor de combinație f și C ne permite să propunem următoarea metodă simplă de enumerare sistematică a combinațiilor cu repetiții de n elemente prin m. Este necesar doar să enumerați, de exemplu, în ordine lexigrafică, toate combinațiile C de (n+m1) elemente ale lui m, transformând secvențial elementele fiecăruia dintre ele în elementele corespunzătoare ale combinațiilor cu repetiții f folosind următoarea formulă: Ca urmare, se formează o succesiune de vectori de combinații cu repetiții de elemente, care sunt aranjați în ordinea generată prin listarea combinațiilor corespunzătoare fără repetiții de elemente. În special, pentru a obține succesiunea de mai sus de combinații de 3 cifre 1, 2 și 3 cu repetări de 4 cifre, este necesar să enumerați în ordine lexigrafică toate combinațiile fără repetări de 6 cifre 1,2,3,4, 5 și 6 sunt de 4 cifre fiecare, transformându-le așa cum este indicat. Următorul exemplu arată o astfel de conversie a combinației (1,3,4,6) cu numărul lexicografic 8: Corespondența considerată unu-la-unu între combinații cu și fără repetări ale elementelor înseamnă că seturile lor sunt la fel de puternice. Prin urmare, în cazul general, numărul de combinații cu repetări de n elemente cu m este egal cu numărul de combinații fără repetări de (n+m1) elemente cu m. Folosind același simbolism pentru a desemna numerele de combinații cu repetări f și fără repetări C, această egalitate poate fi scrisă după cum urmează: Este ușor de verificat că pentru exemplul considerat mai sus, unde n=3 și m=4, numărul de combinații de repetare va fi egal cu 15, ceea ce coincide cu rezultatul listării lor directe: Trebuie remarcat faptul că, spre deosebire de versiunea clasică, valorile parametrilor de combinație cu repetiții n și m nu sunt direct legate între ele, prin urmare f(n,m)>0 pentru orice combinație a valorilor lor pozitive. Condițiile la limită corespunzătoare sunt determinate din egalitatea dintre valorile (n+m1) și (n1) sau (n+m1) și m: De asemenea, ar trebui să fie destul de evident că, dacă m este egal cu 1, atunci nu sunt posibile repetări ale elementelor și, prin urmare, pentru orice valoare pozitivă de n>0, următoarea egalitate va fi adevărată: În plus, pentru numerele de combinații cu repetiții pentru orice valori pozitive ale lui n și m, este valabilă următoarea relație de recurență, care este similară cu identitatea de adunare pentru numerele de combinații fără repetiții de elemente: De fapt, se transformă în identitatea de adăugare indicată la înlocuirea formală a numerelor corespunzătoare de combinații fără repetări în părțile sale stânga și dreapta: Relația de recurență considerată poate fi utilizată pentru a determina efectiv numărul de combinații cu repetări, atunci când este important să se elimine operațiunile intensive de muncă de calculare a produselor factoriale și să le înlocuiască cu operații de adunare mai simple. În acest caz, pentru a calcula valoarea lui f(n,m), trebuie doar să aplicați această relație de recurență până când obțineți suma termenilor de forma f(1,m) și f(i,1), unde i ia valori în intervalul de la n la 1. Prin definiția cantității, astfel de termeni sunt egali cu 1 și, respectiv, i. Următorul exemplu ilustrează utilizarea acestei tehnici de transformare pentru cazul n=3 și m=4: LISTAREA COMBINAȚILOR BINARE Când implementați combinații în hardware sau programare în limbaj de asamblare, este important să puteți procesa înregistrările de combinații în format binar. În acest caz, orice combinație de n elemente ale lui m ar trebui specificată sub forma unui număr binar de n biți (B n,...B j,...B 1), unde m cifre de unitate indică elementele combinație, iar cifrele rămase (nm) au valori zero. Evident, cu această formă de notație, diferite combinații trebuie să difere în aranjarea cifrelor lui 1 și există doar C(n,m) moduri de a aranja m-uri sau (nm) zerouri într-o mulțime binară de n biți. De exemplu, următorul tabel listează toate cele 6 astfel de combinații binare, care oferă numere binare de 4 biți pentru toate combinațiile de 4 elemente ale unei mulțimi arbitrare (E 1 , E 2 , E 3 , E 4 ) cu 2: În cazul general, sarcina de a enumera astfel de combinații binare se rezumă la o căutare sistematică a tuturor mulțimilor binare de n biți cu aranjamente diferite de biți m unu și (nm) zero. În cea mai simplă formă, o astfel de căutare este implementată prin diferite metode de transpunere a biților adiacenți cu o deplasare (algoritmi de schimbare transpozitivă). Aceștia sunt algoritmi iterativi, iar numele lor reflectă natura operațiunilor efectuate la fiecare pas. Procedurile iterative ale algoritmilor de schimbare transpozitivă formează secvențe de combinații binare care încep cu o mulțime binară, în care toate sunt concentrate în cifrele de ordin inferior (pe dreapta) și se termină atunci când toate cele 1 sunt în cifrele de ordin superior ( la stânga): În timp ce se potrivesc în combinațiile inițiale și finale, aceste secvențe diferă în ordinea în care sunt listate seturile binare intermediare. Cu toate acestea, în toate cazurile, fiecare combinație binară ulterioară este formată din cea anterioară ca urmare a efectuării operațiilor de transpunere și deplasare corespunzătoare. În același timp, diferiți algoritmi de schimbare transpozitivă diferă în modul în care selectează o pereche de biți pentru transpunere și un grup de biți pentru deplasare. Această specificitate este discutată mai jos pentru algoritmii de transpunere cu deplasare la stânga și la dreapta. În algoritmul de transpunere cu deplasare la stânga, la fiecare pas, următoarea combinație binară este obținută din cea curentă prin înlocuirea perechii de cifre din stânga 01 cu 10 (transpunere) și deplasarea grupului de cifre unității de conducere, dacă există, aproape de perechea 10 obţinută după transpunere (deplasare). Dacă în acest caz nu există unități în cifrele de început în combinația binară curentă, atunci deplasarea nu este efectuată, chiar și atunci când unitatea de conducere este obținută după transpunerea la acest pas. Deplasarea nu este, de asemenea, efectuată atunci când nu există zerouri în cei mai semnificativi biți înainte de perechea 10 obținută după transpunere. Acțiunile luate în considerare sunt ilustrate de următorul exemplu de realizare a două iterații succesive ale acestui algoritm, unde la o iterație (15) se realizează doar transpunerea (T"), iar la cealaltă iterație (16) transpunerea este completată de o deplasare ( T"+S"): În algoritmul de transpunere cu deplasarea la dreapta, la fiecare pas sunt efectuate pași similari din punct de vedere conceptual. Doar transpunerea asigură că biții din dreapta lui 01 sunt înlocuiți cu 10 (în loc de cei din stânga), iar apoi toți cei din dreapta acestuia sunt mutați la biții mai puțin semnificativi. Ca și înainte, schimbarea se efectuează numai dacă există unități care pot fi deplasate la dreapta. Acțiunile luate în considerare sunt ilustrate de următorul exemplu de realizare a două iterații succesive ale acestui algoritm, unde la o iterație (3) se realizează doar transpunerea (T"), iar la cealaltă iterație (4) transpunerea este completată de o deplasare ( T"+S"): Trebuie remarcat faptul că iterațiile ambilor algoritmi pot fi scrise în formă aditivă dacă combinațiile binare sunt interpretate ca numere întregi în sistemul numeric de bază 2. În special, pentru algoritmul de transpunere cu deplasare la dreapta, fiecare combinație binară următoare (B" n ,…B" j , …B" 1), se poate obține întotdeauna din combinația curentă (B n,…B j,…B 1) prin efectuarea operațiilor de adunare a numerelor întregi folosind următoarea formulă aditivă: În această formulă aditivă, exponenții puterilor de doi f și t denotă, respectiv, numărul de cifre zero de ordin inferior al combinației binare curente și numărul de unități într-un rând în stânga acestora. De exemplu, pentru a patra combinație binară (001110) de n=6 cifre f =1 și t =3. Prin urmare, calcularea următoarei combinații binare folosind formula aditivă la iterația 5 va da următorul rezultat, echivalent cu efectuarea operațiilor de transpunere și deplasare: Pentru o analiză comparativă a algoritmilor de transpunere considerați cu deplasări la stânga și la dreapta, este recomandabil să se compare secvențele de combinații binare pe care le generează în iterațiile lor. Următorul tabel prezintă două astfel de secvențe de combinații binare a 4 elemente din 2, care sunt obținute prin algoritmii de deplasare la stânga (TSL) și, respectiv, la dreapta (TSR): Comparând aceste 2 secvențe, puteți vedea că sunt în oglindă inversă. Aceasta înseamnă că oricare două combinații binare care sunt situate în ele la aceeași distanță de capetele reciproc opuse ale secvențelor lor sunt o imagine în oglindă una a celeilalte, adică coincid atunci când indexarea biților din oricare dintre ele este inversată. De exemplu, al doilea model binar de la începutul secvenței TSL (0101) este o imagine în oglindă a modelului binar (1010) care este al doilea de la sfârșitul secvenței TSR. În general, orice combinație binară cu numărul i dintr-o secvență este o imagine în oglindă a unei combinații binare cu numărul (ni+1) al unei alte secvențe. Această relație dintre aceste secvențe este o consecință a naturii simetrice a operațiilor de transpunere și deplasare în cei doi algoritmi considerați pentru enumerarea combinațiilor binare. Trebuie remarcat faptul că formatul binar poate fi folosit și pentru a înregistra combinații cu repetiții de elemente. Pentru a face acest lucru, este necesar să se stabilească o corespondență unu-la-unu între combinații cu repetiții și combinații binare, care sunt construite după cum urmează. Să existe o combinație arbitrară cu repetări, care se obține prin alegerea a m elemente opțional diferite dintre cele n elemente ale mulțimii generatoare. Pentru a stabili potrivirea dorită, trebuie mai întâi să adăugați toate elementele setului de formare (pisica) la combinație și apoi să sortați concatenarea rezultată (sortați) astfel încât toate elementele identice să fie una lângă alta. Rezultatul este o succesiune de elemente (n+m), unde există n grupuri de elemente identice. Va exista un total de (n+m1) goluri între elemente, printre care vor exista (n1) goluri între grupuri de elemente identice și m goluri între elemente din cadrul grupurilor. Pentru claritate, puteți plasa simbolurile „|” în spațiile indicate. și în mod corespunzător. Dacă acum potrivim 1 cu spațiile dintre grupuri (|) și 0 cu toate celelalte spații (), obținem o combinație binară. Este format dintr-un set binar de (n+m1) biți, unde (n1) sunt uni și m zero biți, a căror locație corespunde în mod unic combinației inițiale cu repetări ale elementelor de la n la m. Tehnica de transformare considerată este ilustrată de următorul exemplu de construire a unei combinații binare (1001101) folosind o combinație cu repetiții (BBD), ale cărei elemente sunt selectate din setul generator al primelor cinci litere latine: În general, numărul de astfel de mulțimi binare determină numărul de moduri de a aranja (n1) uni (sau m zerouri) în (n+m1) cifre binare. Această valoare este în mod evident egală cu numărul de combinații de la (n+m1) prin (n1) sau cu m, adică C(n+m1,n1) sau C(n+m1,m), care este egal cu număr de combinații cu repetări f( n,m) a n elemente, m fiecare. Astfel, având o corespondență unu-la-unu între combinații cu repetiții și combinații binare, este legitim să se reducă enumerarea combinațiilor cu repetiții la enumerarea combinațiilor binare, de exemplu, folosind algoritmi de transpunere cu deplasare la stânga sau la dreapta. După aceasta, trebuie doar să restaurați combinațiile necesare cu repetări folosind combinațiile binare rezultate. Acest lucru se poate face oricând folosind următoarea tehnică de recuperare. Fie mulțimea principală, din elementele cărora se formează combinații cu repetări de m elemente nu neapărat diferite, să fie ordonată în mod arbitrar, astfel încât fiecare dintre elementele sale să aibă un anumit număr de serie de la 1 la n. Să implementăm și enumerarea combinațiilor binare de (n+m1) cifre binare, unde (n1) uni și m cifre zero. Fiecare combinație binară rezultată poate fi completată în stânga cu o cifră unitară fictivă, iar toate cifrele unității pot fi numerotate de la stânga la dreapta cu numere întregi de la 1 la n. Apoi, numărul de zerouri într-un rând după fiecare i-a unitate a combinației binare va fi egal cu numărul de instanțe ale i-lea element al setului principal în combinația corespunzătoare cu repetări. Tehnica luată în considerare este ilustrată de următorul exemplu, în care, folosind o combinație binară (1001101), este restaurată o combinație cu repetări ale BBD, ale cărei elemente sunt selectate din setul generator al primelor cinci litere latine, scrise în ordine alfabetică. , iar linia de suprafață indică elemente care sunt absente în această combinație: Efectuând acțiuni similare în condițiile acestui exemplu, puteți enumera toate cele 35 de combinații binare care formează seturi binare de 7 biți, unde există 4 uni și 3 zerouri, și puteți restabili combinațiile corespunzătoare cu repetări a 5 elemente din 3. Iarna se apropia, iar Khoma și Suslik au decis să se aprovizioneze cu mazăre. Toată ziua au fugit la hambar și au cărat mai multe păstăi: Khoma, patru, și Suslik, doi. Până seara, au numărat toate păstăile pe care le recoltaseră și s-au întrebat cum să împartă acum aceste mazăre. Khoma a susținut că, dacă a târât de două ori mai mult decât Suslik, atunci ar trebui să primească de două ori mai multe mazăre. Suslik a obiectat în mod rezonabil la aceasta că, în primul rând, viteza lui Khoma este vizibil mai mică decât a lui Suslik și, în al doilea rând, cine știe, poate Khoma a fugit doar o dată sau de două ori, iar în restul timpului a fost inactiv... Ajută-ți prietenii să înțeleagă măcar puțin această situație dificilă. Determinați toate opțiunile posibile pentru câte păstăi a adus Suslik și câte Khoma. În prima linie există un număr par natural M – numărul de păstăi furate, 2 ≤ M ≤ 1000. Toate combinațiile posibile ale cantităților de păstăi aduse de Suslik și Khoma, o combinație pe linie. Fiecare combinație reprezintă două numere întregi nenegative separate printr-un spațiu: primul număr este numărul de păstăi aduse de Suslik, al doilea – adus de Khoma. Sortați combinațiile în ordinea descrescătoare a primului număr. #include folosind namespace std; int main()( int a, b = 0; cin >> a ; în timp ce (a >= 0 ) ( cout<<
a
<<
" "
<<
b
<<
"\n"
;
a -= 4; b += 4; returnează 0; Fie a numărul de păstăi aduse de Homa și b numărul de păstăi aduse de Suslik. Întrucât, conform condițiilor problemei, Khoma a purtat doar patru păstăi, vom lua în considerare a = a-4 și b = b + 4 pentru a enumera astfel toate combinațiile posibile ale numerelor de păstăi aduse de Suslik și Khoma. Să folosim și o buclă in timp ce, care va repeta acțiunea descrisă mai sus până la un \geq 0. În răspuns tipărim toate combinațiile posibile ale numerelor de poduri aduse de prieteni, câte una pe linie, ordonate în ordinea descrescătoare a primului număr. Exemplu // Combinații de 3 din 52 pentru (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Aici ne vom uita la o problemă mai complexă, a cărei soluție nu am găsit-o în RuNet (cu toate acestea, voi da un link, dar acea formulă este în mod clar incorectă) - bazată pe combinația în sine (în acest caz, un set de trei numere) găsiți-i indicele. Să presupunem, pentru certitudine, după ordonarea i1 = 3, i2 = 7, i3 = 12. Un algoritm de generare tipic este că generăm combinații de 2 din 52, iar pentru fiecare astfel de combinație într-o buclă imbricată generăm combinații de 3 din 50 și verificăm dacă indicii (i3, i4, i5) din combinația imbricată nu nu coincid cu indicii (i1, i2) în combinație externă: cod C++ // COMBINAȚIE EXTERNĂ pentru (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
cod C++ dacă (i3 >= i1) --i3; dacă (i3 >= i2) --i2; // similar pentru i4, i5 Exemplu de cod pentru împărțirea indexului cu 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Indexul combinației de 2 din 52, înmulțit cu C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // „Reindexează” grupul intern astfel încât numerotarea să fie 0...49 dacă (i3 > = i1) --i3; dacă (i3 >= i2) --i3; dacă (i4 >= i1) --i4; dacă (i4 >= i2) --i4; dacă (i5 >= i1) --i5 ; dacă (i5 >= i2) --i5; // Acum adăugați indicele combinației cu 3 // 0: // SUMA pentru n = 0 cu i3-1 COMBINAȚII (2, 49-n) // = SUMA pentru m = 50-i3 cu 49 (m * (m-1) / 2) offset += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // SUMA pentru n = i3+1 la i4-1 COMBINAȚII (1, 49-n) offset += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUMA pentru n = i4+1 la i5-1 (1) offset + = (i5 - i4 - 1); compensare de întoarcere ; ) În general, aș împărți algoritmii combinatori în următoarele clase: Numărul de combinații Combinaţie din n De k numit set k elemente selectate din date n elemente. Seturile care diferă doar în ordinea elementelor (dar nu în compoziție) sunt considerate identice; de aceea combinațiile diferă de plasamente. Numărul de combinații de n De k
egal cu coeficientul binom Pentru o valoare fixă n functie generatoare de numere de combinatii cu repetari din n De k este: Funcția de generare bidimensională a numerelor de combinații cu repetări este: Fundația Wikimedia. 2010. 70 șaptezeci 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Factorizare: 2×5×7 Notație romană: LXX Binar: 100 0110 ... Wikipedia Număr ușor, un număr condiționat care exprimă în mod unic exteriorul condițiile din timpul fotografierii (de obicei luminozitatea subiectului și fotosensibilitatea materialului fotografic utilizat). Orice valoare a lui E. h. poate fi selectată de mai multe ori. combinatii numarul deschiderii...... Big Enciclopedic Polytechnic Dictionary O formă de număr care distinge două obiecte atât în raport cu un singur obiect, cât și în raport cu mai multe obiecte. Această formă nu există în limba rusă modernă, dar rămân rămășițe ale influenței sale. Deci, combinații de două tabele (cf. plural... ... Dicţionar de termeni lingvistici Matematică combinatorică, combinatorică, ramură a matematicii dedicată rezolvării problemelor de alegere și aranjare a elementelor unui anumit set, de obicei finit, în conformitate cu reguli date. Fiecare astfel de regulă determină metoda de construcție... ... Enciclopedie matematică În combinatorică, o combinație de by este un set de elemente selectate dintr-un set dat care conține elemente diferite. Seturile care diferă doar în ordinea elementelor (dar nu în compoziție) sunt considerate identice, aceste combinații ... ... Wikipedia Angajat în studiul evenimentelor a căror apariție nu este cunoscută cu certitudine. Ne permite să judecăm caracterul rezonabil de a aștepta apariția unor evenimente în comparație cu altele, deși atribuirea de valori numerice probabilităților evenimentelor este adesea inutilă... ... Enciclopedia lui Collier 1) la fel ca analiza combinatorie matematică. 2) O secțiune de matematică elementară asociată cu studiul numărului de combinații, supuse anumitor condiții, care pot fi compuse dintr-un set finit dat de obiecte... ... Marea Enciclopedie Sovietică - (paradoxuri grecești neașteptate, ciudate) în sens larg: o afirmație care se îndepărtează brusc de opinia general acceptată, stabilită, o negare a ceea ce pare „corect necondiționat”; într-un sens mai restrâns, două afirmații opuse, pentru... ... Enciclopedie filosofică - (sau principiul incluziunilor și excluderilor) o formulă combinatorie care vă permite să determinați cardinalitatea unirii unui număr finit de mulțimi finite, care în cazul general se pot intersecta între ele ... Wikipedia O teorie matematică preocupată de determinarea numărului de moduri diferite de distribuire a obiectelor date într-o ordine cunoscută; este deosebit de important în teoria ecuațiilor și teoria probabilității. Cele mai simple sarcini de acest fel sunt... ... Dicţionar Enciclopedic F.A. Brockhaus și I.A. EfronDate de intrare
Ieșire
Teste
Date de intrare
Ieșire
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Cod program
Rezolvarea problemei
Indicele de combinație
Fiecare combinație, permutare, aranjament și alte obiecte combinatorii pot fi asociate cu un index - acesta este numărul în care apare atunci când se repetă prin acest algoritm.
Există o opțiune de căutare „directă”. Pornim contorul de combinații, luăm algoritmul de mai sus și încercăm totul până ajungem la opțiunea dorită. Această opțiune are o complexitate de timp foarte mare, așa că vom renunța la această opțiune.
Să presupunem că intrarea conține numerele i1, i2, i3. În primul rând, trebuie să le aranjam în ordine crescătoare (rețineți că algoritmul de generare însuși, prezentat mai sus, le produce întotdeauna într-o formă ordonată, deși însuși conceptul de „combinație” implică o ordine arbitrară).
Aceasta înseamnă că am „trecut” prin toate combinațiile în care i1 a fost egal cu 0, 1 și 2.
Pentru i1 = 0, am trecut prin C(2, 51) combinații, deoarece indicii i1, i2 trec prin toate combinațiile a 2 din cele 51 de numere.
Pentru i1 = 1 am trecut prin C(2, 50) combinații.
Pentru i1 = 2 am trecut prin C(2, 49) combinații.
În total, am trecut prin SUM (de la n = 0 la n = i1-1) C(2, 51-n).
Pentru i1 = 3, să luăm în considerare acele combinații prin care am trecut în timp ce treceam prin indicele i2 (și pentru noi începe cu i2 = i1+1 = 4).
Când i2 = 4, combinațiile C(1, 47) au trecut, când i2 = 5, combinațiile C(1, 46) au trecut, când i2 = 6, combinațiile C(1, 45) au trecut.
Prin analogie completă, pentru i2 = 7 considerăm combinațiile prin care a trecut indicele i3.
Obtinem formula generala:
Indicele de combinație necesar = SUM (de la n = 0 la i1-1) C(2, 51-n) + SUM (de la n = i1+1 la i2-1) C(1, 51-n) + SUM (din n = i2+1 la i3-1) C (0, 51-n).Index de subset
În combinatorică există un obiect mai complex - împărțirea în submulțimi. De exemplu, împărțirea unui set de 52 de elemente în trei subseturi de, să zicem, 2, 3 și, respectiv, 47 de elemente, unde ordinea elementelor din fiecare submult este neimportantă. (Apropo, o combinație de 2 din 52 este pur și simplu un caz special de împărțire în două subseturi de 2 și, respectiv, 50 de elemente).
Din nou, fiecare astfel de partiție are propriul index.
Se pare că algoritmul nostru pentru găsirea indexului de combinație poate fi modificat pentru a găsi indexul de partiție.
Trebuie remarcat faptul că trebuie să aranjam indicii în „combinația externă” i1, i2 între ei și indicii i3, i4, i5 între ei, dar independent de primii doi.
De asemenea, trebuie luat în considerare faptul că într-o „combinație imbricată” lucrăm în esență cu un set de 50 de elemente, dar indicii i3, i4, i5 trebuie „deplasați” într-un anumit mod, astfel încât să nu se schimbe de la 0. la 51, dar de la 0 la 49:
(ca să spunem așa, tăiem indicii i1, i2 din setul nostru de 52 de elemente și apoi schimbăm setul rămas pentru a închide găurile, în timp ce indicii i3-i5 sunt mutați).
Trebuie avut în vedere că în interiorul fiecărei combinații „externe” avem exact C(3, 50) combinații „imbricate”.
Apoi algoritmul va fi redus la următoarele:
COMBINATION_INDEX (i1, i2 din 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 din 50 după schimbarea indexului). Aducerea algoritmilor la o complexitate constantă
Ar trebui să notez imediat că o „eroare” apare în formulă dacă, de exemplu, i1 = 0 (numărăm suma pentru n = de la 0 la -1) sau i2 = 1 (numărăm suma de la 1 la 0). De fapt, în astfel de cazuri, suma corespunzătoare ar trebui luată egală cu zero, iar rezultatul va fi corect.
Ar trebui să fiu atent și la complexitatea timpului a algoritmilor noștri: au complexitate liniară, cu condiția să considerați C ca fiind timp constant. Aceasta este deja mult mai bună decât forța brută.
Dar de fapt (în cazul nostru 52) nimic nu ne împiedică să reducem algoritmul la complexitate constantă. Pentru a face acest lucru, vom aplica cunoștințele de matematică și vom calcula analitic toate sumele.
De exemplu, numărul de combinații C(2, K), dacă îl „extindeți” sub forma unei formule K! / ((K-2)! * 2!), se reduce la un polinom de gradul II. Și din moment ce îl avem sub semnul sumei, putem aplica formulele pentru suma N-a puteri ale numerelor din seria naturală (vezi Wikipedia) și să obținem un singur polinom de gradul 3. Care, evident, are o complexitate constantă în timp. (Mai mult, „eroarea” pe care am citat-o la începutul subtitlului nu se manifestă în niciun fel; formula rămâne corectă).
Repet, asta pentru o dimensiune fixă a setului de bază. Cu toate acestea, sunt sigur că, cu ajutorul metaprogramarii, puteți „învăța” compilatorul, astfel încât să facă această lucrare pentru dvs. Postfaţă
În simulatorul meu de poker (Texas Hold'em), am vrut să calculez și să stochez probabilitățile de câștig în avans pentru toate combinațiile posibile de cărți de mână (2 piese) și toate cărțile flop (3 cărți pe masă). Aceasta corespunde împărțirii. cele 52 de subseturi de 2, 3, 47.
Calculat și salvat.
Dar când a venit timpul să citesc datele dintr-un fișier pentru o anumită combinație, chiar nu am vrut să calculez ceva mult timp sau să caut într-un fișier gigabyte. Acum doar determin offset-ul în fișier și citesc direct ceea ce am nevoie.
Ar fi interesant să existe o carte de referință despre algoritmi combinatori pentru toate obiectele combinatorii, inclusiv permutări, combinații, plasări, subseturi, combinații cu repetiții, plasări cu repetiții. Formule explicite
Legături
Vedeți ce este „Numărul de combinații” în alte dicționare:
Cărți