Unul dintre exemplele clasice de utilizare a funcțiilor de generare este problema biletelor fericite.
Biletul de troleibuz (tramvai) are un număr format din șase cifre. Biletul este considerat norocos dacă suma primelor trei cifre este egală cu suma ultimelor trei, de exemplu, 024321. Primul număr bilet de cifre poate fi zero. Se știe că numărul de bilete norocoase de la șase cifre este de 55252. Dar cum a fost obținut acest număr? În general, cum să rezolve o problemă mai complicată: pentru orice număr întreg pozitiv n indică numărul de bilete fericite cu valoare 2n?
Aici vom lua în considerare câteva metode cunoscute pentru rezolvarea acestei probleme. Numărul de bilete fericite de la 2 cifre va fi notat cu simbolul Ln.
Metoda de programare dinamică
Introducem notația: - numărul de numere n-evaluate cu suma cifrelor egale cu k (numărul poate începe cu cifra 0). Este clar că orice bilet este format din două părți: stânga (n cifre) și pe dreapta (dar și n cifre), și în ambele părți ale aceeași sumă a cifrelor. Numărul de bilete cu noroc cu suma k dintr-o parte este evident egal. Prin urmare, numărul total de bilete de noroc de 2n cifre este
Indicele de sumare superior este 9n. deoarece suma maximă a cifrelor dintr-o parte a biletului este de 9n.
Acum rămâne să găsim toate valorile. Numărul n-evaluate cifre, cu suma k poate fi exprimată prin numărul (n-1) Numerele -ary, adăugând la acesta n-lea cifre, care poate fi egal cu 0, 1. 9:
Aici se presupune implicit că pentru n≥0. Punem prin definiție.
Calcularea valorilor acestei formule este mai bine reprezentată prin utilizarea tabelului:
Orice număr din acest tabel (cu excepția) este obținut prin însumarea a 10 elemente care sunt pe partea stângă și pe partea de sus a acestuia. De exemplu, în tabelul roșu este alocat numărul 73, și gri - numărul, suma cărora este egală. Numarul 73 inseamna exact ca exista numere de trei cifre cu suma cifrelor 12.
Acum trebuie să însumăm pătratele numerelor din coloana n = 3. 1 2 +3 2 +6 2 +⋅⋅⋅= 55252. Dacă ar fi trebuit să se ia în considerare biletele de opt cifre, ar fi necesar să se calculeze coloana n = 4 la o valoare de k = 36.
Metoda de generare a funcțiilor
Biletul este compus din două părți. Luați în considerare orice bilet câștigătoare, să zicem, 271 334 și să înlocuiască cifrele din a doua parte a valorii, care nu este de ajuns pentru a 9. Aceasta este 271665. Acum, suma cifrelor biletului este egal cu 27. Este ușor de observat că această concentrare merge cu orice bilet norocos. Astfel, numărul de bilete norocoase de la 2 cifre este egal cu numărul de numere de 2 cifre cu o sumă de cifre egală cu 9n. Asta este
Acum am putea folosi tehnica paragrafului anterior și găsim numărul în coloana n = 6 și în rândul k = 27. S-ar dovedi exact 55252. Dar aici poți folosi tehnica de generare a funcțiilor.
Se scrie funcția de generare G (z). a cărui coeficient este egal cu z k.
Într-adevăr, un număr unic cu o sumă de cifre k (pentru k = 0. 9) poate fi reprezentat într-un fel. Pentru k> 9, există moduri zero.
Rețineți că dacă G este pătrat, atunci coeficientul z k este egal cu numărul de modalități de a obține suma k folosind două cifre de la 0 la 9:
În cazul general, G n (z) este funcția generatoare pentru numere. deoarece coeficientul la z k este obținut prin căutarea tuturor combinațiilor posibile de n cifre de la 0 la 9 egale cu suma k. Rescriem funcția de generare într-o altă formă:
În cele din urmă, trebuie să găsim
Pentru a face acest lucru, să vedem ce se va întâmpla dacă extindem parantezele în următoarea expresie (suntem interesați doar de coeficienții pentru z 27):
Soluție prin integrarea
Atenție, această secțiune este destinată celor care cunosc cursul CTEP.
Folosim funcția de generare G (z) din secțiunea anterioară:
Să compunem seria Laurent după cum urmează:
Valoarea lui a0 în această extindere va fi exact [verificați]
Cauza teorema integrala spune asta
unde integrarea se face pe orice curbă închisă simplă care cuprinde originea. Convenabil de luat. să se integreze de-a lungul unui cerc (o astfel de înlocuire este echivalentă cu o tranziție la coordonatele polare):
Acum înlocuim H (z).
Este ușor de văzut că în cazul general
Să constatăm că, în realitate, este extrem de dificil să rezolvăm această problemă prin integrare. În practică, metoda de programare dinamică funcționează cel mai bine.
De asemenea, într-unul din exerciții se va sugera derivarea formulei:
a căror calcul este foarte eficient astăzi.
Articole similare
Trimiteți-le prietenilor: