Dambudziko rekudzvanywa kwedata, mune yakareruka chimiro, rinogona kuenderana nenhamba uye zvinyorwa zvadzo. Nhamba dzinogona kududzirwa nenhamba ("gumi neimwe" yenhamba 11), mazwi esvomhu ("mbiri pamakumi maviri" ye1048576), mazwi etambo ("mapfumbamwe mashanu" ye99999), mazita chaiwo ("nhamba yechikara" ye666, "gore rekufa kwaTuring" ya1954), kana misanganiswa yazvo. Chero zita rakakodzera iyo iyo interlocutor inogona kunyatsoona kuti ndeipi nhamba yatiri kutaura nezvayo. Zviripachena, udza interlocutor wako "factorial of eight" inoshanda zvakanyanya kupfuura yakaenzana notation "zviuru makumi mana nemazana matatu nemakumi maviri". Mubvunzo une musoro unomuka pano: ndeipi chidimbu chipfupi chenhamba yakapihwa?
Muzivi Bertrand Russell akabudiswa muna 1908 , iyo inobata nyaya yenhamba notation kubva kune rimwe divi: Ndeipi nhamba diki isingade mabhii makumi masere?
Nhamba yakadaro inofanira kuvapo: kubva kune makumi masere eRussia mavara uye nzvimbo iwe unogona kugadzira 3480 chete mazita, izvo zvinoreva kuti uchishandisa makumi masere mavara iwe unogona kuratidza kwete kupfuura 3480 nhamba. Izvi zvinoreva kuti hazvibviri kudoma imwe nhamba isingapfuuri 3480 nenzira iyi.
Izvi zvinoreva kuti nhamba iyi ichaenderana nemazita "nhamba diki pane iyo makumi masere mavara haana kukwana", iyo ine mabhii 78 chete! Kune rumwe rutivi, nhamba iyi inofanira kuvapo; kune rumwe rutivi, kana nhamba iyi iripo, saka zita rayo harienderani nayo. Paradox!
Nzira iri nyore yekubvisa gangaidzo iri kureva kusarongeka kwezvirevo zvemashoko. Senge, kana chete seti yakatsanangurwa yekutaura yaibvumidzwa mune notation, ipapo "nhamba diki pane iyo makumi masere mavara haana kukwana" haingave chirevo chechokwadi, nepo zvinyorwa zvinobatsira senge "factorial of eight" zvaizoramba zvichigamuchirwa.
Pane nzira dzepamutemo here dzekutsanangura kutevedzana (algorithm) yezviito panhamba? Kune, uye muhuwandu - vanonzi programming mitauro. Panzvimbo pezvinyorwa zvemashoko, tichashandisa mapurogiramu (somuenzaniso, muPython) anoratidza nhamba dzinodiwa. Semuenzaniso, kune mashanu mapfumbamwe chirongwa chakakodzera print("9"*5). Ticharamba tichifarira chirongwa chipfupi chenhamba yakapihwa. Hurefu hwepurogiramu yakadaro inonzi nhamba; ndiwo muganho wetioretical umo nhamba yakapihwa inogona kudzvanywa.
Panzvimbo pekanganisika yaBerry, isu tinogona kufunga imwe yakafanana: Ndeipi nhamba diki iyo chirongwa che kilobyte haina kukwana kuburitsa?
Tichafunga nenzira yakafanana neyakare: kune 2561024 kilobyte zvinyorwa, zvinoreva kuti hapana anopfuura 2561024 manhamba anogona kuburitswa ne kilobyte zvirongwa. Izvi zvinoreva kuti imwe nhamba isingapfuuri 2561024 haigone kutorwa nenzira iyi.
Asi ngatinyore purogiramu muPython iyo inogadzira zvinyorwa zvese zvinogoneka kilobyte, inoamhanyisa kuti iite, uye kana ikaburitsa nhamba, yobva yawedzera iyi nhamba kuduramazwi reanosvikika. Mushure mekutarisa zvese zvinobvira 2561024, zvisinei kuti inotora nguva yakareba sei, chirongwa chinotarisa nhamba diki chisipo muduramazwi uye chinodhinda nhamba iyoyo. Zvinoita sezviri pachena kuti chirongwa chakadaro chinokwana mu kilobyte yekodhi - uye ichaburitsa iyo iyo nhamba isingagone kuburitswa ne kilobyte chirongwa!
Ko kubata chii manje? Izvo hazvichagone kuverengerwa kune kusarongeka kweiyo notation!
Kana iwe uchivhiringika nenyaya yekuti chirongwa chedu chinoda huwandu hwemuchadenga kuti ushande - duramazwi (kana bit array) yezvinhu 2561024 - saka iwe unogona kuita chinhu chimwe chete pasina icho: kune imwe neimwe ye2561024 manhamba, , pfuura nepakati pese 2561024 zvirongwa zvinogoneka, kusvika pasina yakakodzera. Hazvina mhosva kuti kutsvaga kwakadaro kunotora nguva yakareba kwazvo: mushure mekutarisa zvishoma pane (2561024) 2 pairs kubva kunhamba uye purogiramu, inopera uye inowana iyo inonyanya kukosha nhamba.
Kana kuti haizopedzi here? Zvechokwadi, pakati pezvirongwa zvose zvichaedzwa, pachava while True: pass (uye maanalogues ayo anoshanda) - uye nyaya yacho haizopfuuriri kupfuura kuyedza chirongwa chakadaro!
Kusiyana nekukanganisika kwaBerry, uko kubata kwaive mune kusarongeka kweiyo notation, mune yechipiri nyaya isu tine yakanyatso-disguised reformulation. . Ichokwadi ndechokuti hazvibviri kuona kuburitsa kwayo kubva purogiramu munguva inopera. Kunyanya, Kolmogorov yakaoma : hapana algorithm ingabvumira, kune imwe nhamba, kuwana hurefu hwepurogiramu pfupi inodhinda iyi nhamba; zvinoreva kuti hapana mhinduro kudambudziko raBerry - kutsvaga hurefu hwezita rakapfupika rezwi renhamba yakapihwa.
Source: www.habr.com