Qadimiy Algoritmlar: Misrlik Kasrlardan Nimalarni O'rganish Mumkin

Har safar recursive function yozganingizda yoki greedy algorithm ishlatganingizda, minglab yillar oldin yashagan matematiklarning izidan borasiz. Misrlik kasrlar — bu faqat butun sonlarning teskarisidan foydalanadigan matematik ifodalar — insoniyat tarixidagi eng qadimiy hujjatlashtirilgan algoritmlardan biri hisoblanadi. Va ular ko'rinishidan ko'ra anchagina murakkab.

Misrliklar Qanday Muammoni Yechanismlar

Bugungi kasrlar bizga tabiiy ko'rinadi: 3/7, 5/12, 17/23. Lekin bu yozuv usuli Yevropada 18-asrgacha keng tarqalmagan edi. Undanda oldin, agar siz kasrni ifodalashni xohlasangiz, uni birlik kasrlarga — surati 1 ga teng kasrlarga ajratishingiz kerak edi.

Misrliklar amaliy muammoga duch kelishdi: 7 ta nonni 8 kishiga adolatli taqsimlash kerak. Javob oddiy 7/8 yozish emas edi. Buning o'rniga ular boshqacha yo'l tutishar edi: 1/2 + 1/4 + 1/8.

Bu oddiy ko'rinadigan usul chuqur matematik fikrlashni talab qilar edi. Va shu bilan Misrlik kasr algoritmining asoslari yaratildi.

Greedy Algoritm, Qadimiy Usul

Bu yerda developerlar uchun qiziqarli qism boshlanadi. Misrliklar har qanday kasrni Misrlik kasrga aylantirish uchun greedy algorithm — ya'ni "ahmakcha" algoritm — ishlatishar. Uning mohiyati shundan iborat: eng katta mumkin birlik kasrni tanla, ayir, keyin takrorla.

4/23 ni misol qilib olamiz. Algoritm so'raydi: 23/4 dan katta eng kichik butun son qaysi? Bu 6. Demak 1/6 dan boshlaymiz, 4/23 dan ayiramiz, natijada 1/138 hosil bo'ladi. Va tayyor: 4/23 = 1/6 + 1/138.

Bu usul har doim ishlaydi — 1880-yilda isbotlangan matematik teorema. Garchi yevropaliklar buni 12-asrda Fibonachchidan boshlab bilishar edi.

Bu Zamonaviy Developerlar Uchun Nimani Anglatadi

Birinchi qarashda bu faqat tarixiy qiziqarli faktdek tuyuladi. Lekin algoritmda nima sodir bo'layotganini ko'ring:

1. Recursive decomposition — murakkab muammoni soddaroq subproblemlarga ajratish
2. Greedy selection — har bir qadamda local optimal tanlov qilish
3. Termination proof — qoldiq doim kichiklanib boradi, bu esa tugallanishni kafolatlaydi

Bu tushunchalar zamonaviy algoritmik fikrlashning asosini tashkil etadi. Recursive function yozganingizda, siz qadimiy matematiklarning ishlatgan mantiqiy tuzilmasini qo'llayapsiz.

Tarixiy Bohran

Bu yerda e'tirof etish kerak bo'lgan noquyati tarix bor. Misrlik kasr usuli yunon matematikasidan minglab yillar oldin paydo bo'lgan. Lekin yevropalik matematiklar 19-asrda Raynd papirusini "qayta kashf etganda", bu usul ko'pincha yunon olimlariga tegishli deb atalardi — garchi uning haqiqiy ildizlari qadimiy Misrda bo'lsa.

Bu pattern — Afrika va boshqa yevropacha bo'lmagan tsivilizatsiyalarning hissalarini matematik tarixdan o'chirish — bugungi kunda ham kompyuter fanini o'qitish va muhokama qilishda davom etmoqda.

Matematik Sirli Qoldiq

Ba'zi olimlar "Misrlik uchlik" deb atadigan qiziqarli puzzle bor: 13, 17 va 173. Agar buni 3 + 1/13 + 1/17 + 1/173 sifatida interpreter qilsangiz, bu ifoda π ni to'rt xona aniqlikda yaqinlashtiradi — Misrning odatda keltiriladigan 3.16 qiymatidan ham aniqroq.

Bu Atay mi, yo'qmi — matematika tarixchilari orasida bahs davom etmoqda.

Qadimiydan Zamonaviyga

Misrlik kasrlar davomli kasrlar bilan bog'liq — kompyuter fanida va sonlar nazariyasida hali ham o'rganiladigan mavzu. Greedy algoritm yondashuvi resurs taqsimlash, scheduling va optimallashtirish muammolarida zamonaviy qo'llanmalarga ega.

Shunday qilib, recursive function ni debug qilayotganingizda yoki greedy yondashuv nega ishlashini tushuntirayotganingizda, eslab qoling: siz 4000 yildan ortiq tarixga ega matematik an'analarda ishtirok etayapsiz.

Ba'zida eng qadimiy algoritmlar hali ham eng yaxshisidir.