Vuto la kuponderezana kwa data, mu mawonekedwe ake osavuta, lingafanane ndi manambala ndi zolemba zawo. Manambala amatha kuwonetsedwa ndi manambala ("khumi ndi chimodzi" kwa nambala 11), mawu a masamu ("ziwiri mu makumi awiri" za 1048576), mawu a zingwe ("zisanu zisanu" za 99999), mayina enieni ("chiwerengero cha chilombo" pa 666, "Chaka cha imfa ya Turing" za 1954), kapena zophatikizira zake mosagwirizana. Matchulidwe aliwonse omwe interlocutor amatha kudziwa bwino nambala yomwe tikukamba ndi yoyenera. Mwachiwonekere, uzani interlocutor wanu "factorial ya eyiti" bwino kwambiri kuposa mawu ofanana "makumi anayi mazana atatu mphambu makumi awiri". Funso lomveka likubuka apa: Kodi mawu achidule kwambiri pa nambala yoperekedwa ndi ati?
Wanthanthi Bertrand Russell lofalitsidwa mu 1908 , yomwe ikukhudza nkhani yolemba manambala kuchokera mbali inayi: Ndi nambala yanji yaying'ono yomwe sifunika zilembo makumi asanu ndi atatu?
Chiwerengero choterocho chiyenera kukhalapo: kuchokera ku zilembo makumi asanu ndi atatu za Chirasha ndi malo mukhoza kupanga mayina 3480 okha, zomwe zikutanthauza kuti pogwiritsa ntchito zilembo makumi asanu ndi atatu mungathe kutchula manambala osapitirira 3480. Izi zikutanthauza kuti n'zosatheka kutchula nambala inayake osapitirira 3480 motere.
Izi zikutanthauza kuti nambala iyi idzafanana ndi dzina "chiwerengero chochepa kwambiri chomwe zilembo makumi asanu ndi atatu sizikwanira", yomwe ili ndi zilembo 78 zokha! Kumbali imodzi, chiwerengerochi chiyenera kukhalapo; Komano, ngati nambalayi ilipo, ndiye kuti dzina lake silikugwirizana nalo. Zodabwitsa!
Njira yosavuta yochotsera chododometsa ichi ndi kunena za kusakhazikika kwa mawu. Monga, ngati gulu lodziwika bwino la mawu ndilololedwa muzolembazo, ndiye "chiwerengero chochepa kwambiri chomwe zilembo makumi asanu ndi atatu sizikwanira" sizingakhale zolemba zovomerezeka, pomwe zolemba zothandiza ngati "factorial ya eyiti" zikanakhala zovomerezeka.
Kodi pali njira zofotokozera motsatira (algorithm) ya zochita pa manambala? Pali, ndipo mochuluka - amatchedwa zilankhulo zamapulogalamu. M'malo molemba mawu, tidzagwiritsa ntchito mapulogalamu (mwachitsanzo, mu Python) omwe amawonetsa manambala ofunikira. Mwachitsanzo, kwa zisanu ndi zinayi pulogalamuyo ndiyoyenera print("9"*5). Tidzapitiriza kukhala ndi chidwi ndi pulogalamu yaifupi kwambiri ya nambala yoperekedwa. Kutalika kwa pulogalamu yotereyi kumatchedwa manambala; ndi malire ongoyerekeza omwe nambala yoperekedwa ikhoza kukakamizidwa.
M'malo modabwitsa za Berry, tsopano titha kuganiziranso zofananira: Ndi nambala yanji yaying'ono kwambiri yomwe pulogalamu ya kilobyte sikwanira kutulutsa?
Tidzalingalira mofanana ndi kale: pali malemba a 2561024 kilobyte, zomwe zikutanthauza kuti nambala zosaposa 2561024 sizingatuluke ndi mapulogalamu a kilobyte. Izi zikutanthauza kuti chiwerengero china chosaposa 2561024 sichikhoza kutengedwa motere.
Koma tiyeni tilembe pulogalamu mu Python yomwe imapanga zolemba zonse za kilobyte, kuziyendetsa kuti zichitike, ndipo ngati zitulutsa nambala, ndikuwonjezera nambala iyi ku dikishonale ya omwe atha kupezeka. Pambuyo poona zotheka zonse 2561024, mosasamala kanthu kuti zitenga nthawi yayitali bwanji, pulogalamuyo imayang'ana nambala yaing'ono yomwe ikusowa mu dikishonale ndikusindikiza nambalayo. Zikuwoneka zoonekeratu kuti pulogalamu yotereyi idzakwanira mu kilobyte ya code - ndipo idzatulutsa chiwerengero chomwe sichikhoza kutulutsidwa ndi pulogalamu ya kilobyte!
Chagwira ndi chiyani tsopano? Sichingakhalenso chifukwa cha kusakhazikika kwa zolembazo!
Ngati mukusokonezedwa ndi mfundo yakuti pulogalamu yathu idzafunika kukumbukira kukumbukira zakuthambo - dikishonale (kapena bit array) ya zinthu 2561024 - ndiye mutha kuchita zomwezo popanda izo: pa nambala iliyonse ya 2561024, nayenso. , dutsani mapulogalamu onse a 2561024, mpaka palibe oyenera. Zilibe kanthu kuti kusaka koteroko kudzakhala nthawi yayitali kwambiri: mutayang'ana pang'ono (2561024)2 awiriawiri kuchokera pa nambala ndi pulogalamuyo, idzatha ndikupeza nambala yofunikira kwambiri.
Kapena sichidzatha? Zowonadi, pakati pa mapulogalamu onse omwe adzayesedwe, padzakhala while True: pass (ndi analogues ake ogwira ntchito) - ndipo nkhaniyi sidzapitirira kuposa kuyesa pulogalamu yotere!
Mosiyana ndi chododometsa cha Berry, pomwe kugwidwa kunali mwamwayi wa notation, chachiwiri tili ndi kukonzanso kobisika. . Chowonadi ndi chakuti sikutheka kudziwa zotsatira zake kuchokera ku pulogalamu mu nthawi yomaliza. Makamaka, zovuta za Kolmogorov : palibe algorithm yomwe ingalole, pa nambala yoperekedwa, kupeza kutalika kwa pulogalamu yaifupi kwambiri yomwe imasindikiza nambala iyi; zomwe zikutanthauza kuti palibe njira yothetsera vuto la Berry - kupeza kutalika kwa mawu achidule a nambala yoperekedwa.
Source: www.habr.com