Inkinga yokucindezelwa kwedatha, ngendlela yayo elula, ingahlobana nezinombolo kanye nemibhalo yazo. Izinombolo zingachazwa ngezinombolo ("ishumi nanye" inombolo 11), izinkulumo zezibalo ("ezimbili kwengamashumi amabili" kwe-1048576), izinkulumo zezintambo ("amashumi amahlanu" ka-99999), amagama afanele ("inombolo yesilo" ngo-666, "Unyaka wokufa kukaTuring" ka-1954), noma inhlanganisela yakho ngokungafanele. Noma yikuphi ukuqokwa kufanelekile lapho u-interlocutor anganquma ngokucacile ukuthi iyiphi inombolo esikhuluma ngayo. Ngokusobala, tshela umkhulumeli wakho "i-factorial yesishiyagalombili" esebenza kahle kakhulu kunombhalo olinganayo "izinkulungwane ezingamashumi amane namakhulu amathathu namashumi amabili". Umbuzo ophusile ophakamayo lapha: imuphi umbhalo omfushane wenombolo ethile?
Isazi sefilosofi uBertrand Russell sanyatheliswa ngo-1908 , ethinta indaba yokubhala inombolo ukusuka kolunye uhlangothi: Iyiphi inombolo encane kakhulu engadingi izinhlamvu ezingamashumi ayisishiyagalombili?
Inombolo enjalo kufanele ibe khona: kusuka ezinhlamvu ezingamashumi ayisishiyagalombili zesiRashiya nezikhala ungenza amagama angu-3480 kuphela, okusho ukuthi usebenzisa izinhlamvu ezingamashumi ayisishiyagalombili ungakwazi ukukhomba izinombolo ezingaphezu kuka-3480. Lokhu kusho ukuthi akunakwenzeka ukuqoka inombolo ethile hhayi ngaphezu kuka-3480 ngale ndlela.
Lokhu kusho ukuthi le nombolo izohambisana nokuqokwa "inombolo encane kunazo zonke izinhlamvu ezingamashumi ayisishiyagalombili ezinganele", enezinhlamvu ezingu-78 kuphela! Ngakolunye uhlangothi, le nombolo kufanele ibe khona; ngakolunye uhlangothi, uma le nombolo ikhona, igama layo alihambisani nayo. Indida!
Indlela elula yokuchitha le ndida iwukubhekisela ekungashosheni kwamagama. Njengokuthi, uma kuphela isethi echazwe ngokukhethekile yezinkulumo evunyelwe ku-notation, khona-ke "inombolo encane kunazo zonke izinhlamvu ezingamashumi ayisishiyagalombili ezinganele" bekungeke kube inothi elivumelekile, kuyilapho imibhalo ewusizo efana "i-factorial yesishiyagalombili" izohlala yamukeleka.
Ingabe zikhona izindlela ezisemthethweni zokuchaza ukulandelana (i-algorithm) yezenzo ezinombolweni? Kukhona, futhi ngobuningi - zibizwa ngokuthi izilimi zokuhlela. Esikhundleni sezimpawu zomlomo, sizosebenzisa izinhlelo (isibonelo, ngePython) ezibonisa izinombolo ezidingekayo. Isibonelo, ama-nines amahlanu uhlelo lufanelekile print("9"*5). Sizoqhubeka nokuba nentshisekelo kuhlelo olufushane kakhulu lwenombolo ethile. Ubude bohlelo olunjalo bubizwa ngokuthi izinombolo; umkhawulo wetiyori lapho inombolo enikeziwe ingacindezelwa khona.
Esikhundleni sendida kaBerry, manje singacabangela efanayo: Iyiphi inombolo encane kakhulu uhlelo lwe-kilobyte enganele ukuyikhipha?
Sizobonisana ngendlela efanayo nangaphambili: kunemibhalo engu-2561024 kilobyte, okusho ukuthi azikho izinombolo ezingaphezu kuka-2561024 ezingakhishwa ngezinhlelo ze-kilobyte. Lokhu kusho ukuthi inombolo ethile engekho ngaphezu kuka-2561024 ayikwazi ukutholakala ngale ndlela.
Kodwa ake sibhale uhlelo ku-Python olukhiqiza yonke imibhalo ye-kilobyte engenzeka, iwaqhube ukuze asetshenziswe, futhi uma ekhipha inombolo, bese wengeza le nombolo kusichazamazwi salezo ezifinyelelekayo. Ngemva kokuhlola wonke amathuba angu-2561024, kungakhathaliseki ukuthi kuthatha isikhathi eside kangakanani, uhlelo lubheka inombolo encane kunazo zonke engekho kusichazamazwi bese luphrinta leyo nombolo. Kubonakala kusobala ukuthi uhlelo olunjalo luzongena ku-kilobyte yekhodi - futhi luzokhipha yona kanye inombolo engakwazi ukukhishwa ngohlelo lwe-kilobyte!
Yini oyibambayo manje? Ngeke kusathintwa ukungahleleki kombhalo!
Uma udidwe ukuthi uhlelo lwethu luzodinga inani lememori yezinkanyezi ukuze lisebenze - isichazamazwi (noma i-bit array) yezakhi ezingu-2561024 - khona-ke ungenza into efanayo ngaphandle kwayo: inombolo ngayinye yezinombolo ezingu-2561024, ngokulandelana. , hamba kuzo zonke izinhlelo ezingaba ngu-2561024, kuze kube yilapho kungabikho okufanele. Akunandaba ukuthi ukusesha okunjalo kuzohlala isikhathi eside kakhulu: ngemuva kokuhlola amapheya angaphansi kuka-(2561024)2 kusuka kunombolo kanye nohlelo, kuzophela futhi kutholakale leyo nombolo ethandwa kakhulu.
Noma ngeke iqede? Ngempela, kuzo zonke izinhlelo ezizozanywa, kuzoba khona while True: pass (kanye nama-analogues asebenzayo) - futhi indaba ngeke iqhubeke nokuhlola uhlelo olunjalo!
Ngokungafani nendida kaBerry, lapho ukubanjwa kwakungahlelekile kwe-notation, esimweni sesibili sine-reformulation efihleke kahle. . Iqiniso liwukuthi akunakwenzeka ukucacisa ukuphuma kwalo ohlelweni ngesikhathi esinqunyelwe. Ikakhulukazi, ubunzima be-Kolmogorov : ayikho i-algorithm engavumela, inombolo ethile, ukuthola ubude bohlelo olufushane kakhulu oluphrinta le nombolo; okusho ukuthi asikho isisombululo senkinga kaBerry - ukuthola ubude begama elifushane kakhulu lenombolo enikeziwe.
Source: www.habr.com