A probléma a szerencsés jegyet
Az egyik klasszikus példája a használata generáló függvények, hogy egy szerencsés jegyet.
Trolley (villamos) jegy számos amely hat számjegyű. A jegy tartják szerencsésnek, ha az összeg az első három számjegy megegyezik az összeg az utolsó három, például 024321. Az első számjegy a jegy száma lehet nulla. Köztudott, hogy az összeg a szerencsés jegyet hat szám egyenlő 55252. De ez a szám kapunk? Általában, hogyan lehet megoldani a nehéz problémát: minden pozitív egész n, adja meg a számát 2n értékes szerencsés jegyet?
Itt fogjuk vizsgálni néhány módszer, hogy megoldja ezt a problémát. Az összeg a szerencsés jegyet 2n számok lesznek Jele Ln.
dinamikus programozási módszer
Bemutatjuk a jelölést: - az n-jegyű értékes számok összege egyenlő k (a szám kezdődhet számjeggyel 0). Egyértelmű, hogy a jegy két részből áll: a bal oldali (n számjegy) és a jobb (szintén n számjegy), és mindkét rész azonos számjegyeinek összege. Száma szerencsés jegyet az összeg k egy része nyilvánvalóan egyenlő. Tehát az összes 2n értékes szerencsés jegyet egyébként
A felső összegzési index 9n. mivel a maximális szám egy része a jegy egyenlő 9n.
Most meg kell találnunk az összes értéket. Száma n-értékű jegyű számok összege k fejezhető száma (n-1) -aril számok, hozzáadunk n -edik számjegy, amely lehet egyenlő 0, 1 9:
Ebben az esetben azt feltételezzük, hogy hallgatólagosan n≥0. Definíció szerint.
Értékek kiszámítását az említett képlet legjobban képviseli az asztalra:
Bármennyi a táblázatban (kivéve) kapunk, ha a elemek összege 10, állva a bal és a tetején. Például egy piros színű tábla kiosztott szám 73 és szürke - számok, amelyek összege egyenlő. A nagyon száma 73 azt jelenti, hogy van annyi háromjegyű számok összege számjegyek 12.
Most meg kell összefoglalni a négyzetek a számok álló oszlopban n = 3. 1 2 3 2 6 2 +⋅⋅⋅= 55252. Ha az egyik volt, hogy kiszámítja a nyolc-jegyek, amely szükséges lenne kiszámítani az oszlop n = 4 értékre k = 36.
Módszer generáló függvények
A jegy két részből áll. Tekintsünk nyerő jegy, mondjuk, 271 334 és cserélje ki a számokat a második része az érték, ami nem elég, hogy a 9. Ez 271665. Most a számjegyeinek összege a jegy egyenlő 27. Nem könnyű észrevenni, hogy ez a téma megy minden szerencsés jegyet. Így a több szerencsés jegyet 2n számjegyek számával megegyező 2n értékű számok összege számjegy egyenlő 9n. tehát
Most az egyik jönne a technikát az előző bekezdésben és segítenek megtalálni a számot az oszlopban, n = 6, k = 27 sort. Kiderült, hogy pontosan 55252. azonban akkor használja a technikát előállító funkciókat.
Mi írjuk a generáló függvény G (z). együttható z k, amely egyenlő y.
Sőt, az egyik jegyű számot az összeg számjegyeit k (k = 0. 9) is képviselteti magát egy út. K> 9 - nulla lesz.
Vegye figyelembe, hogy ha a beépített függvény G a téren, akkor az együttható z k számával megegyező módon, hogy az összeg k két szám 0-9:
Általában, G N (Z) - generáló függvény érte a számokat. mivel a együtthatója z k kapott keresési összes lehetséges kombinációját n számjegyek 0-9, összegével egyenlő k. Átírni a generáló függvény más formában:
Ennek eredményeképpen meg kell nézni
Ehhez lássuk, mi fog kiderülni, ha, hogy felfedje a zárójelben a következő kifejezések (mi érdekli csak együtthatók z 27):
Megoldás integrálásával
Figyelem, ez a rész azoknak készült, akik ismerik során komplex elemzése.
Mi használjuk a generáló függvény G (z) az előző részben:
Mi alkotnak Laurent-sor az alábbiak szerint:
Az érték a0 ebben bomlás pontosan megegyezik [check]
Cauchy-féle integráltétel azt mondja, hogy
ahol az integrálás bármilyen egyszerű zárt görbe átívelő eredetét. Kényelmes tenni. integrálni a kör mentén (ez egyenértékű cseréje az átmenet poláris koordináták):
Most helyettesítheti itt H (z).
Könnyen belátható, hogy általában,
Megjegyezzük, hogy a valóságban, hogy megoldja ezt a problémát integrálásával rendkívül nehéz. A gyakorlatban, annál jobb a dinamikus programozási módszer.
Szintén egyik gyakorlat fogja kérni, hogy ebből a képlet:
amelynek kiszámítása úgy tűnik, hogy nagyon hatékony a mai napig.