Алгоритм

Mavzu: Algoritm haqida umumiy intuitive ta’rif Algoritm tushunchasi Inson hayoti davomida katta­kichik vazifalar yoki masa­ lalarni hal etishni o‘z oldiga maqsad qilib qo‘yadi. Odatda, u o‘z maqsadiga erishishi uchun bajarishi lozim   bo‘lgan  amal   yoki  ishlarini  hayotiy  tajribasi  yoki  o‘zlashtirgan  bilimiga asos­ lanib ma’lum bir tartibga keltiradi. Bunga hayotimizdan xilma­ xil misollar keltirish mumkin. misol 1.1­ Ko‘chadan o‘tish maqsad qilib qo‘yilgan bo‘lsin. U holda ko‘chadan o‘tayotgan kishi hammamizga odatiy hol bo‘lib qolgan quyidagi harakatlarni bajarishi lozim bo‘ladi: 1) chap tarafga qaralsin, agar transport vositasi yo‘q bo‘lsa, 2­ bandga o‘tilsin, aks holda 1­bandga o‘tilsin; 2) o‘ng tarafga qaralsin, agar transport vositasi yo‘q bo‘lsa, 3­ bandga o‘tilsin, aks holda 1­bandga o‘tilsin; 3) ko‘chadan o‘tilsin. 1.2­ Eni 6 metr va bo‘yi 10 metr bo‘lgan joyni to‘ldirish uchun sotib olinishi kerak misol bo‘lgan 12x25 sm (eni 12 sm va bo‘yi 25 sm) g‘ishtlar soni topilsin. Hisoblayotgan kishi geometriya fanidan olgan bilimiga asos­ lanib quyidagi ketma­ketlikdagi amallarni bajaradi: 1) joyning yuzasi 5joy santimetr o‘lchov birligida topilsin; 2) bir dona g‘ishtning yuzasi ^gisht santimetr o‘lchov birligida topilsin; 3) g‘ishtlar   soni   Sson   joyning   yuzasini   g‘ishtning   yuzasiga   nis­   bati   deb olinsin. 1.3­ Amal   bajarisin:   19632107   +   19702202.   Bu   amalni   qanday   bajargan   bo‘lar misol edingiz? Ha, to‘gri, bu sonlarni ustun ko‘rinishida deyarli quyidagicha qo‘shasiz: 1) sonlar   xonalari   to‘g‘ri   keladigan   tartibda   birinchisining   tagiga   ikkinchisi yozib olinsin; 2) sonlarning birlik xonasidagi raqamlarini qo‘shib, natijani birlik xonasidagi raqami birliklar tagiga yozilib, o‘nlik xonasi raqami dilda saqlansin; 3) sonlarning o‘nliklardagi va dildagi raqamlarni qo‘shib, natijani birlikdagi raqami o‘nliklar tagiga yozilib, o‘nlik raqami dilda saqlansin; va 3­banddagi  qoida yuzliklar, mingliklar va hokazo uchun tak­  rorlanadi. Bu amallar quyidagi korinishda sizga juda tanish: 19632107 + 19702202 39334309 Yuqoridagi misollarda keltirilgan amallar ketma­ketligi, boshqacha aytganda, ko‘rsatmalar   yoki   buyruqlar   ketma­ketligi   biror   kishi   tomonidan   bajarilgach, ko‘zlangan maqsadga erishi­ ladi. Bunday amallar ketma­ketligi yoki hayotimizda har kuni va har soatda uchrab turadigan turli qoidalar ichida biror zaruriy natijaga erishishga olib keladigan amallarni ketma­ket bajarishni talab etadigan qoidalar informatikaning asosiy tushunchalaridan bin algoritm so‘zi bilan ifodalanadi. Algoritm so‘zi IX asrda yashab (783­yilda tug‘ilgan) o‘z ilmiy ishlari xazinasi bilan dunyoga tanilgan vatandoshimiz buyuk astronom, matematik va geograf Abu Abdullo Muhammad ibn Muso al­Xorazmiy nomidan kelib chiqqan. Al­Xorazmiy arifme­ tikaga bag‘ishlangan «Hind hisobi haqida kitob» risolasida to‘q­ qizta hind raqamining sonlarni ifodalashdagi afzalliklari va ular yordamida har qanday sonni ham   qisqa   va   oson   yozish   mum­   kinligini   aytadi   va   hozirgi   kunda   hamma o‘quvchilar biladigan sonlar ustida, yuqoridagi 3­misoldagi kabi ustun ko‘rinishida amallar bajarish qoidalarini yoritadi. Ayniqsa, nol (0) qo‘llash­ ning ahamiyati haqida tushuncha berib, nolni yozmaslik nati­ janing xato chiqishiga olib keladi, degan.   Bu   risola   XII   asrda   Ispaniyada   lotin   tiliga   tarjima   qilingan   va   butun Yevropaga tarqatilgan. Bu tarjimaning XIV asrda ko‘chirilgan qo‘lyozmasi­ning yagona   nusxasi   Kembrij   universitetining   kutubxonasida   saqlanmoqda.   Risola «Dixit Alxhorithmi», ya’ni «Dediki al­ Xorazmiy» iborasi bilan boshlanadi. Algoritm deganda, biror maqsadga erishishga qaratilgan ijrochi baja­ rishi uchun mo‘ljallangan ko‘rsatma (buyruq)larning aniq, tushunarli va chekli ketma­ketligi tushuniladi. Bu algoritm tushunchasining matematik ta’rifi bo‘lmasa ham intuitiv ma’noda algoritmning mazmunini ochib beruvchi tavsifidir. Algoritmni intuitiv ma’noda bir necha   misollarda   izoh­   laymiz.   Biror­bir   narsani   taqiqlovchi   qoidalar   algoritm bo‘lol­   maydi,   masalan:   «Chekish   mumkin   emas»,   «Begonalarning   kirishi taqiqlanadi», «Kirish», «Chekish uchun joy» kabi biror­ bir narsaga ruxsat etuvchi qoidalar ham algoritmga xos emas. Lekin «Svetoforni yashil rangida o‘ting» juda sodda   bo‘lsa   ham   algoritmdir.   Demak,   yuqorida   keltirilgan   misollardagi   ko‘r­ satmalar ketma­ketligi algoritm va bu algoritmlarni bajarayotgan inson — ijrochi bo‘lar ekan. Algoritm ijrochisi faqat insonmi, degan savol berishingiz tabiiy. Bu savolga javob quyidagicha: Algoritm ijrochisi — algoritmda ko‘rsatilgan buyruq yoki ko‘r­ satmalarni bajara oladigan abstrakt yoki real (texnik yoki biologik) sistema. Ijrochi bajara olishi uchun algoritm unga tushunarli bo‘lishi lozim. Algoritm ijrochi tushunadigan tilgagina emas, balki uning bilim va malakasiga ham mos bo‘lishi kerak. Aks holda ijrochi birorta ham ko‘rsatmani bajara olmasligi mumkin. Ijrochi   bajara   olishi   mumkin   bo‘lgan   ko‘rsatma   yoki   buyruq­   lar   to‘plami ijrochining   ko‘rsatmalar   sistemasi  deyiladi.   Masalan,  «16  sonidan   kvadrat   ildiz chiqarilsin»   ko‘rsatmasi   2­sinf   o‘quvchisining   ko‘rsatmalar   sistemasiga   tegishli bo‘lmaydi, lekin 8­sinf o‘quvchisining ko‘rsatmalar sistemasiga tegishli bo‘ladi. Algoritm ijrochiga tushunarli bo‘lishi uchun ijrochining im­ koniyatlarini bilish lozim. Agar ijrochi inson bo‘lsa, u holda algoritm insonning imkoniyatlaridan kelib chiqib tuzilishi kerak. Bunda ko‘zlangan maqsad va algoritmdan kelib chiqib inson tushunadigan   til,   insonning   bilimi,   hayotiy   tajribasi,   kasbiy   malakasi,   yoshi, qolaversa, jismoniy imkoniyatlari hisobga olinishi zarur. Agar ijrochi texnik vosita (masalan, kompyuter, elektron soat, dastgohlar) bo‘lsa, u holda algoritm shu texnik vositaning imkoniyatlaridan kelib chiqib tuzilishi kerak. Agar   ijrochi   kompyuter   hisoblanib,   uning   dasturiy   ta‘mi­   notida   berilgan («Karra   jadvalini   hosil   qilish»)   algoritmni   bajara   oladigan   dastur   (masalan, elektron jadvallardan birortasi ham) bo‘lmasa, u holda hech qanday natijaga erishib bo‘lmaydi. Demak, berilayotgan har qanday ko‘rsatma ijrochining ko‘r­ satmalar sistemasidan olinishi, ya’ni ijrochi uni qanday baja­ rishni bilishi kerak ekan. Bu algoritmning  tushunarlilik  xossasini   ifodalaydi.   Shuni   ta‘kidlash   joizki, informatikada algoritmning asosiy ijrochisi sifatida kompyuter xizmat qiladi. Ijrochi Bu   qo‘llanmada   algoritm   tuzish   usullarini   o‘rgatish   uchun   sizni   bir   nechta Ijrochi bilan tanishtiramiz [1], lekin ular kom­ pyuter yoki inson emas, balki biz uchun abstrakt sistema. Misol sifatida Robot nomli ijrochi bilan tanishtiramiz. Robot   teng   o‘lchamdagi   kvadratlarga   bo‘lingan   tekislikda   yashaydi   (1.1­ rasm). U kvadratlarning birida joylashgan va ixtiyoriy qo‘shni kvadratga o‘tishi mumkin. Shu bilan birga Robot o‘zi turgan kvadratni bo‘yashi mumkin. Robot 5 ta ko‘rsatmani bajaradi: yuqoriga quyiga chapga o‘ngga bo‘ya Bulardan  yuqoriga,  quyiga,  chapga  va  o‘ngga  ko‘rsatmalari  Robotni  mos yo‘nalishlar  bilan  siljishga  majbur  qiladi.  Lekin  bo‘ya  ko‘rsatmasida  Robot harakatlanmaydi,  faqat  o‘zi  turgan  kvadratni  bo‘yaydi.  Agar kvadrat bo‘yalgan bo‘lsa u holda bo‘ya ko‘rsatmasida kvadratning rangi o‘zgarmaydi. Robotning hayotidagi voqealardan eng qizig‘i, ba’zi kvadrat­ lar orasida devor borligi   (1.2­rasm).   Odatda,   Robot   har   to­   mondan   devorlar   bilan   o‘ralgan   va kvadratlardan hosil bo‘lgan to‘g‘ri to‘rtburchak ichida joylashgan bo‘ladi. Lekin shu to‘g‘ri to‘rtburchak ichida ham devorlar bo‘lishi mumkin. Ba’zan   devorlar   murakkab   shaklni   hosil   qiladi,   bu   shaklni  labirint  deb atashadi. Robot devor ichidan o‘ta olmaydi. Agar devor ichidan o‘tmoqchi bo‘lsa, u holda Robot «sochilib» ketadi. Bunday halokatli holatlarga tushmaslik uchun quyidagi to‘rtta shartni tekshirish zarur: yuqori bo‘sh quyi bo‘sh chap bo‘sh o‘ng bo‘sh Bo‘sh so‘zi shu tomonda devor yo‘qligini bildiradi. Robot o‘zi turgan katakning devorinigina aniqlay oladi. O‘zi turgan kvadrat bilan devor orasida bitta kvadrat bo‘lsa ham uzoqdagi bu devorni «ko‘ra» olmaydi. U   yonida   turgan   de­   vorgagina   «tegib»   ko‘rishi   mumkin.   1.3­rasmda   turli holatlarda   yuqori   bo‘sh   degan   birgina   shartning   qiymatini   ko‘rish   mumkin. Tushunarliki, yuqori bo‘sh sharti (yoki yuqori bo‘sh da’vosi Rost bo‘lsa) Robot yuqoriga ko‘rsatmasini «sochilib» ketmasdan bajara olishini bildiradi. Bu kabi mulohazalar chap bo‘sh sharti va chapga ko‘rsat­ masi, yana boshqa juftliklar uchun ham to‘g‘ri. Ro‘yxatni yakunlash uchun Robot biladigan oxirgi shartni keltiramiz: bo‘yalgan Bu shart Robot turgan kvadratni bo‘yalgan yoki bo‘yal­ maganligini tekshirish imkonini beradi. Agar kvadrat bo‘yalgan bo‘lsa, shart ROST, aks holda YOLG‘ON bo‘ladi. Ko‘rib turibsiz, Robotning ko‘rsatmalari juda sodda. Lekin uni o‘rab turgan muhit   xilma­xil   imkoniyatlarga   boy.   Robotning   maydonida   turli   labirintlar, yo‘laklar,   har   xil   shakldagi   xonalar   va   boshqa   figuralar   yordamida   juda   ko‘p qiziqarli masalalar qo‘yish mumkin. Robotning mikrohayoti — algoritmik tafak­ kurni   rivojlantirish   uchun   a‘lo   darajadagi   mashq   maydonidir.   Ijrochilarni boshqalari   bilan   tanishtirishdan   avval   ularni   nimalar   farqlab   turishini   izohlab o‘tmoqchimiz. Ijrochini quyidagilar farqlab turadi: ijrochi muhiti; • ijrochining ko‘rsatmalar sistemasi; sodda amallar; • INKOR. • • Ijrochi muhiti — ijrochi «yashaydigan» yoki algoritmni baja­ radigan muhiti. Ijrochi   Robot   misolida   bu   katakli   maydon,   bo‘yalgan   kataklar   va   devorlar. Ularning joylashishi va Robotning turgan joyi muhitning aniq holatini beradi. Har   bir   ijrochi   qat‘iy   belgilangan   ro‘yxatdagi   —   ijrochining   ko‘rsatmalar sistemasidagi ko‘rsatmalarni bajara oladi. Har bir ko‘rsatma uchun qo‘llash sharti (muhitning qanday holatida ko‘rsatmaning bajarish mumkinligi) va ko‘rsatmani bajarilish   natijasi   belgilangan   bo‘lishi   kerak.   Masalan,  yuqoriga  ko‘rsat­   masi Robotning yuqorisida devor yo‘q bo‘lsagina bajarish mum­ kin. Bu ko‘rsatmaning bajarilish natijasi — Robot yuqoriga bitta katak siljiydi. Ko‘rsatma chaqirilgandan keyin Ijrochi  sodda amal bajaradi. Robot misolida — yuqoriga bitta katak siljish. INKOR — bu holat bo‘lib, ko‘rsatma muhitning mumkin bo‘lmagan holatida chaqirilganda yuz beradi. Robot misolida qarasak, agar u devor ichidan o‘tmoqchi bo‘lsa, «sochilib» ketadi va bu Robot uchun INKOR holatiga olib keladi. Yodingizda bo‘lsin: Ijrochi algoritm maqsadi haqida hech narsa bilmaydi, u berilgan ko‘rsatmalarni so‘zsiz bajaradi, xolos. Algoritmning xossalari Algoritmning   tavsifida   «biror   maqsadga   erishishga   qaratilgan»   jumlasi qo‘llanilgan. Bu maqsadni yuqorida keltirilgan mi­ sollarda ko‘rishimiz mumkin: ko‘chadan   o‘tish,   g‘ishtlar   soninihisoblash,   yig‘indini   hisoblash.   Bular algoritmning natijaviylik (cheklilik) xossasi bilan bog‘liq. Bu xossaning mazmuni shundan iboratki, har qanday algoritm ijrochi chekli qadamdan so‘ng oxir­oqibat ma’lum bir yechimga olib kelishi kerak. Shuni ta‘kidlash joizki, algoritm avvaldan ko‘zlangan maqsadga eri­ shishga olib kelmasligi ham mumkin. Bunga ba‘zan algoritmning   noto‘g‘ri   tuzilgani   yoki   boshqa   xatolik  sabab   bo‘lishi   mum­   kin. Ikkinchi   tomondan,   qo‘yilgan   masala   ijobiy   yechimga   ega   bo‘lmasligi   ham mumkin. Lekin salbiy natija ham natija deb qabul qilinadi. misol 1.4­ x2+x+1 = 0 kvadrat tenglama yechilsin. Bu   tenglamaga   quyida   keltirilgan  «ax2+bx+c  =   0   (a№0)   ko‘ri­   nishidagi kvadrat   tenglamani   yechish»   algoritmini   qo‘llab,   tenglama   yechimga   ega emasligini aniqlaymiz. Bu ham natija ekanligi sizga ma’lum. 1) diskriminant: D = b2—4ac hisoblansin; 2) agar  D  < 0 bo‘lsa, tenglama yechimga ega emas deb olinsin va 5­bandga o‘tilsin;  agar D = 0 bo‘lsa, yagona yechim ­ 2a o‘tilsin; 3) birinchi yechim —b— D ga, ikkinchi yechim b + ^ ga   teng   deb   olinsin   va   5­bandga ga teng deb olinsin; 4) tugallansin. 1.1­ mashq E’tibor  qilgan  bo‘lsangiz,  diskriminantning  noldan  kichikligi,  nolga  tengligi tekshirildi, ammo noldan kattaligi tekshirilmadi. Sababini o‘ylab ko‘ring! Demak, algoritm doimo chekli qadamdan iborat bo‘lishi va biror natija berishi kerak   ekan.   Bu   algoritmni  diskretlilik  (uzluklilik,   alohidalik)   xossasiga   olib keladi. Algoritmda masalani yechish jarayoni alohida olingan sodda ko‘rsatmalar ketma­   ketligini   qadam­baqadam   bajarishdan   iborat   bo‘lishi   kerak.   Bu   xossa misollardan   yaqqol   ko‘rinib   turibdi.   «Angliyada   avto­   mobilni   yo‘lning   chap qismida haydang» qoidasi talabnomabo‘lgani bilan uzluksizlik xarakteriga ega va shuning uchun ham algoritm hisobiga qo‘shilmaydi. E’tiboringizni yana bir narsaga qaratamiz. Keltirilgan mi­ sollarda quyidagi jumlalar bor: «Ko‘chadan o‘tish» (ariqdan yoki dengizdan emas), «Eni 6 metr va bo‘yi  10  metr   bo‘lgan   joyni»  (kilometr  emas),  «eni   12  santimetr   va  bo‘yi   25 santimetrli g‘ishtlar» (eni 5 santimetr va bo‘yi 100 santimetrli g‘ishtlar emas), «x2+x+1 = 0 kvadrat tenglama» (x2—1 = 0 kvadrat tenglama emas). Bu jumlalar va qavs   ichida   yozilganlarni   taqqoslasangiz,   olinadigan   natija   shu   jumlalardagi «qiymat»larga chambarchas bog‘liq ekanligini tushunasiz. Agar bu «qiymatlar» o‘zgarsa,   masalan,   qavs   ichidagilarga,   olinadigan   natija   umuman   bosh­   qacha bo‘lishini   ko‘rish   qiyin   emas.   Qiymat   so‘zini   qo‘shtirnoq   ichiga   olganimizga sabab, siz doimo qiymat so‘zini faqat sonlar bilan bog‘lab o‘rganib kelgansiz. Lekin,   bilingki,   biror   masala   uchun   qiymat   har   xil   turdagi   obyektlar   bo‘lishi mumkin   ekan.   Demak,   har   bir   algoritmning   natijasi   avvaldan   berilgan,   ya’ni boshlang‘ich   qiymatlarga   bog‘liq   bo‘lar   ekan.   Boshlang‘ich   qiymatlar   turli natijalarga olib kelishiga yana bir hayotiy misolga o‘zingiz javob bera olasiz: sizga va   mehmonga   kelgan   do‘stlarin­   gizga   pishiralayotgan   palovga   20   gramm   tuz solish o‘rniga 200 gramm tuz solishsa natija bir xil bo‘ladimi? Har  bir  algoritm  — bu amallarni  belgilovchi  qoida bo‘lib, ularning zanjiri natijasida   biz   boshlang‘ich   qiymatlardan   izlangan   natijaga   kelamiz.   Bunday amallar   zanjiri   algoritmik   jarayon,   har   bir   amal   —   algoritmning   qadami   deb ataladi. Yana   boshlang‘ich   qiymat   va   natija   bo‘lishi   mumkin   bo‘lgan   narsalarning tahliliga qaytamiz. Ko‘rdikki, har bir algoritm uchun boshlang‘ich qiymatlarning turli   hollarini   tanlash   mumkin.   Masalan,   g‘ishtlar   masalasi   algoritmi   uchun boshlang‘ich   qiy­   matlarni   tavsiflashda   «santimetr»   so‘zlarini   «uzunlik o‘lchovlari» kabi tushunish mumkin. Bu holda hosil bo‘ladigan natijaning miqdori o‘zgaradi, xolos. Ko‘p algoritmlar boshlang‘ich qiymatlarning turli hollari uchun o‘z kuchini saqlab qoladi. Qo‘shish algoritmini ixtiyoriy natural sonlar jufti uchun qo‘llash   mumkin.   Avval   aytib   o‘tilgan   algoritmlarning   aniqlangan   bu   xossasi (ularni   boshlang‘ich   qiymatlarning   juda   ko‘p   sondagi   hollariga   qo‘llash mumkinligi)  ommaviylik  deb ataladi. Yuqorida keltirilgan  «ax2+bx+c  = 0 (a^0) ko‘rinishidagi   kvadrat   tenglamani   yechish»   algoritmi   ixtiyoriy   a,   b,   c   haqiqiy sonlar uchun natija beradi, ya’ni algoritmning ommaviylik xossasi o‘rinli ekan. Algo­  ritmlaming  juda  ko‘p  xususiy  hollarda  ishlashi   shunday   o‘ta  muhim   va ahamiyatli xossa, shu sababli ancha vaqtgacha uni algoritmning ilmiy ta’rifiga kiritilishi   shart   deb   hisoblandi.   Bu   ko‘pgina   qoidalarni   fan   sohasidan   chiqarib tashlar (ularni «oz miqdordagi» ommaviyligi tufayli) va ham ilmiy tadqiqotni, ham ularning natijasini amaliyotda qo‘llashni qiyinlashtirar (balki bu ilmiy bo‘lmagan hol   bo‘lsa­chi?),   bu   esa   jiddiy   noqulaylikka   sabab   bo‘ladi.   Boshlang‘ich qiymatlarning faqat bitta — yagona holiga qo‘llash mumkin bo‘lgan algoritm ham katta ahamiyat kasb etadi. Ularga turli xil avtomatlardan (masalan, agar aniq bir tangaga moslangan gazeta sotadigan avtomat, yoki telefon­ avtomat) foydalanish algoritmlari tegishlidir, aniq bir joydan boshlanadigan va belgilangan joyga olib boradigan yo‘nalish bo‘yicha borish algoritmi va boshqalar. «Ommaviylik» atamasining mavhumligi mashhur, ba‘zan uyum paradoksi deb ataluvchi, Evbulid paradoksi orqali tasdiqlanadi. Paradoks mazmunini o‘zimizga savol berib va javobini berib tezda aniqlab olishimiz mumkin. Bitta tosh — uyummi? Yo‘q. Ikkita tosh­chi? Yana yo‘q. Uchtasi­chi? Oxir­ oqibat, biz yoki uyum mavjud emas degan xulosaga, yoki shunday sondagi toshlar to‘plami borki, undan bitta oshsa uyum hosil bo‘lishiga olib keladi, deb e’tirof etishga   majbur   bo‘lamiz.   U   yoki   bu   fikr   ham   haqiqatga   ziddir   va   bu   uyum atamasining   mavhumligining   natijasi   bo‘lib   hisoblanadi.   Nima   bo‘lganda   ham ommaviylik xossasidan oddiygina «bo‘yin tovlash» mumkin emas. Uni ta’riflashni ozgina o‘zgartirish hamda shuning asosida yuqorida aytib o‘tilgan mavhumlikni yo‘qotish zarur. «Ommaviylik» atamasiga qanday mazmun kiritish kerak? Bu savolga javob shunday.   Har   bir   algoritm   uchun   biror­bir   obyektlar   (narsalar,   buyumlar   va hokazo) sinfi mavjud va ularning barchasi boshlang‘ich qiymat sifatida olinishi mumkin, deb hisoblash zarur. Manfiymas butun sonlarni qo‘shish algoritmi uchun manfiymas   butun   sonlarning   barcha   juftligi;   avtomatdan   «Toshkent   oqshomi» gazetasini sotib olish algoritmi uchun — yagona obyekt — tanga shunday sinf bo‘la   oladi.   Algoritmning   ommaviyligi   —   mos   sinfning   barcha   obyektlarini qo‘llash   mumkinligidir,   ya’ni,   ularning   qandaydir   miqdorining   (chekli   yoki cheksiz)   qo‘llash   mumkin   emasligi   emas.   Mumkin   bo‘lgan,   ya’ni   joiz obyektlaming miqdori chekli yoki cheksizligi, yoki miqdori nolga teng bo‘lishi — bu shu sinfning xususiyatidir. Agar algoritm yordamida joiz boshlang‘ich qiymat asosida izlangan natijani olish mumkin bo‘lsa u holda  algoritmni joiz  boshlang‘ich qiymatga  qo‘IIash mumkin deyiladi. Agar boshlang‘ich qiymat joiz bo‘lsa ham natija olish mumkin bo‘lmasa, u holda unga algoritm qo‘IIash mumkin emas deyiladi. Endi   joiz   boshlang‘ich   qiymatlar   sinfi   qanday   ekanligini   ko‘rib   chiqamiz. Boshlang‘ich qiymatlar ba‘zan narsa yoki buyumlar, sonlar ekanini ko‘rdik. Bu fikr olingan natijalar uchun ham o‘rinli. Bu narsalar orasidagi umumiylik nimada? Algoritm — bu qoidalar va demakki, ular qandaydir tillarda ifoda­ langan, degan fikrni e’tiborga olsak, bu umumiylik ko‘rinadi. Bir necha marta bu qoidalarning aniq bajarilishi qanchalik muhim ekanligi haqida gapirib o‘tdik. Lekin bunday aniq bajarilishi boshlang‘ich qiymatlar (ular bilan birga izlangan natijalar ham) biror­bir  tilda, balki  yan­ gisida, batamom  tavsiflanishga imkon bersagina mumkin. Bu holda har bir boshlang‘ich qiymatga, har bir oraliq natijaga va nihoyat, izlangan natijaga qandaydir gap mos keladi. Yana, mazkur gapning «Mazmun»i bir qiymatli bo‘lishi zarur. Matematikada ko‘pincha maxsus usul qo‘llanadi. Bu usul  shundan iboratki, biror­bir   obyekt   boshqa   tabiatli   obyekt   bilan   almashtiriladi,   bunda   yangi obyektlarga   birlamchilari   bilan   bir   qiymatli   mos   bo‘ladi.   Ko‘rilayotgan   holda boshlang‘ich   qiymatlar   tilining   gaplari   bilan   boshlang‘ich   qiymatlarning   o‘zi orasida bir qiymatli moslik mavjud. Shu sababli, algoritmni matematik ta’riflashda boshlang‘ich   qiymatlar   va   izlangan   natijalar   tilning   gaplari   deb   hisoblanishi mumkin. Bunday almashtirish amaliyot nuqtayi nazaridan mumkinmi? Albatta, mumkin. Chunki,   algoritmning   o‘zida   boshlang‘ich   qiy­   matlar   emas,   ularning  nomi, jarayonni   bajarish   uchun  esa   amallar   va  hosil  bo‘ladigan  natijalarning  nomini bilish yetarli. Keltirilgan usul algoritm ta’rifini tor ma’noda bo‘lishiga olib keladi, deyish mumkin.   Bunday   fikr   asoslidir.   Lekin   bu   torayish   muhim   emas,   chunki   u algoritmlar beradigan imkoniyatlarni kamaytira olmaydi. Bu   kabi   yondashish   boshlang‘ich   qiymatlar   va   natijalar   turlarini   nisbatan kamaytiradi, ammo ular avvalgidek turli fizik tabiatga ega bo‘lishi mumkin, lekin biz   uchun   bu,   ularni   nazariyqaraganimizda,   turli   tillardagi   gaplar   kabidir. Narsalarning turlanishini biz tillarning turlanishiga keltirdik. To‘g‘ri, tillar ham kam emas. Ularni cheksiz to‘plam (faqat mavjudlari emas, balki mavjud bo‘lishi mumkin bo‘lganlari ham, ya’ni mumkinlari ham) deb hisoblash mumkin. Lekin har bir   algoritm   faqat   ikkita   til   bilan   bog‘langan:   bittasida   u   ta’riflangan, ikkinchisining   gaplari   boshlang‘ich   qiymatlar   hollarini   uning   uchun   mumkin bo‘lganlaridir.   Birinchi   tilni,   odatda,  algoritmik   til  deb,   ikkin­   chisini   — operandlar tili deb atashadi. Operandlar deb shunday obyektlarga aytiladiki, ular ustida algoritm talab qilgan amallar bajariladi. Operandlar tilining barcha gaplari joiz deb hisob­ lanadi, bu tilga tegishli bo‘lmagan biror­bir belgilar birikmasi ta’rif bo‘yicha joiz emas. Mavzu: Umumiy algoritmlar nazariyasiga doir asosiy kashfiyotlar. Rekursiya prinsipi. O‘zini chaqiradigan protseduralar masala Robot   kengligi   1   ga   teng   va   devorlar   bilan   o‘ralgan   gorizontal   to‘g‘ri to‘rtburchakning chap devoridan biror masofada turibdi. Robotni o‘ng devordan shuncha masofada bo‘lgan katakka o‘tka­ zing  Robot bu yerda turibdi Robot bu yerga o‘tishi kerak Masala juda sodda bo‘lib ko‘rinadi. Haqiqatan, agar Robot bilan chap devor orasidagi, aytaylik, ikkita katakni bilsak uni kerakli katakka jo‘natish qiyin emas: Robot avval o‘ng devor­ gacha boradi, keyin ikkita chapga yuradi. Murakkabligi shundan   iboratki,   chap   devorgacha   bo‘lgan   masofa   ixtiyoriy   bo‘lishi   mumkin, bizda   esa   bu   masofani   o‘lchash   uchun   biror   usul   ham,   o‘lchay   olsak   uning qiymatidan foydalana olish imkoniyati ham yo‘q. Bu vaziyatdan chiqish, bunaqasi tez­tez bo‘lib turadi, kutilmaganda sodir bo‘ldi. Yechim.   Qo‘yilgan   masalani   yecha   oladigan   prorsedurani   yozishga   harakat qilamiz. Bu protsedurani simmetriya deb ataymiz. Avvalo bizga masalani hech bo‘lmaganda Robot chap devor oldida turgan birgina holatda yechish mumkinligi yordam beradi. Bu holda Robot o‘ng devor oldiga borib to‘xtashi kerak: PROT simmetriya BOSHLANISH AGAR EMAS chap bo‘sh U HOLDA TOKI o‘ng bo‘sh BAJAR o‘ngga TAMOM AKS HOLDA TAMOM TAMOM Endi Robotning chap yonida devor bo‘lmasa, nima qilishi  kerakligi haqida o‘ylaymiz.   Keling,   chapga   bir   qadam   tash­   laymiz,   Robot   bilan   chap   devor orasidagi masofa qisqaradi. Balki masofa 0 bo‘lib qolishi ham mumkin! Bu esa simmetriya protsedurasi kerakli ishni bajarayotganini va biz uni chaqi­ rishimiz mumkinligini bildiradi. Protsedura ishlashi tuga­ ganidan keyin chapga bir qadam yurish kerak bo‘ladi, chunki Robotdan o‘ng devorgacha bo‘lgan masofa uning boshlang‘ich joyidan chap devorgacha bo‘lgan masofaga teng bo‘lishi kerak. Mana nima hosil bo‘ladi: PROT simmetriya BOSHLANISH AGAR EMAS chap bo‘sh U HOLDA TOKI o‘ng bo‘sh BAJAR o‘ngga TAMOM AKS HOLDA chapga simmetriya chapga TAMOM TAMOM Buni qarangki, yozilgan bu algoritm har qanday sharoitda ham to‘g‘ri ishlar ekan! Qo‘yilgan masalani yechadigan algoritm esa juda sodda ko‘rinishga ega: simmetriya Natijada  bizda juda  g‘alati  protsedura  hosil  bo‘ldi:  u  o‘zini   o‘zi   chaqiradi. Bunday protseduralarni rekursiv deb atashadi. E’tibor bilan uning ishini qadam­ baqadam o‘rganib chiqamiz. Robot bilan chap devor orasidagi boshlang‘ich masofa 0 ga teng bo‘lganda protsedura to‘g‘ri ishlashini ko‘rdik. Robot bilan chap devor orasidagi masofa bitta katak bo‘lganda qanday voqea ro‘y berishini ko‘rib chiqamiz. Protsedura   boshida   EMAS   chap   bo‘sh   sharti   YOLG‘ON,   shuning   uchun protseduradagi tarmoqlanish tuzilmasining AKS HOLDA so‘zidan keyingi qismi bajariladi. Bu qismda uchta ko‘rsatma bor: chapga simmetriya chapga Birinchi ko‘rsatmani bajargach, Robot chap devorga bitta katak yaqinlashadi, ya’ni devor yoniga borib qoladi. Keyin simmetriya protsedurasi bajariladi. Endi vaziyat o‘zgardi: Robot chap devor yonida turibdi. Bu vaziyatda protsedura to‘g‘ri ishlashini bilamiz va u o‘ng devor yoniga boradi. Uchinchi chapga ko‘rsatmasi uni o‘ng   devordan   bitta   chap   katakka   o‘tkazadi,   ya’ni   kerakli   katakka   tushadi   va protsedura ishi tugaydi. Siz, albatta, Robot bilan chap devor orasidagi masofa ikkita katak bo‘lganda protsedura ishining to‘g‘riligini qanday tekshi­ rishni tushungan bo‘lsangiz kerak. EMAS   chap   bo‘sh   sharti   YOLG‘ON,   demak,   protsedurada   tarmoqlanish tuzilmaning AKS HOLDA so‘zidan keyingi qismi bajariladi. Birinchi ko‘rsatmani bajargach, Robot  chap devorga bitta katak yaqinlashadi, ya’ni  devor bilan uni orasida bitta katak qoladi. Keyin simmetriya protsedurasi bajariladi va Robotni, yuqorida   ko‘rib   o‘tganimizdek,   o‘ng   devordan   bitta   chap   katakka   o‘tkazadi. Keyingi chapga ko‘rsatmasi uni o‘ng devordan ikkita chap katakka, ya’ni kerakli katakka o‘tkazadi. Mulohaza   yuritishning   bu   usuli   —  induksiya   bo‘yicha   mulohaza  —   bizga birinchi marta duch kelishi emas. U bizga chap devordan ixtiyoriy boshlang‘ich holatda protsedura ishining to‘g‘riligini tekshirish imkonini beradi. mashq Nima uchun oxirgi chapga ko‘rsatmasidan oldingi simmetriya protsedurasiga chap bo‘sh shartini tekshirmasa ham bo‘ladi? 7.2- mashq Robotning 7.2­rasmdagi holatlari uchun simmetriya protsedurasi masala Robot devorlar bilan o‘ralgan to‘g‘ri to‘rtburchakning ichida turibdi. Robotni boshlang‘ich holatidan to‘g‘ri to‘rtburchak mar­ kaziga nisbatan simmetrik bo‘lgan katakka o‘tkazuvchi algoritm tuzing. 7.1­ masala Robot kengligi 1 ga teng gorizontal yo‘lakda turibdi. Yo‘lak chap tomondan devor   bilan   chegaralangan,   o‘ng   tomon   —   cheksiz.   Robotni   shunday   katakka o‘tkazingki, bu katakdan chap devorgacha bo‘lgan masofa boshlang‘ish katakdan chap devorgacha bo‘lgan masofadan ikki marta katta bo‘lsin. Yechim. Bu masalada Robot  chap devor  yonida turgan  bo‘lsa,  nima qilish tushunarli: u o‘z joyida qolishi kerak. Quyidagicha protsedura tuzamiz: PROT ikkilangan sakrash BOSHLANISH AGAR EMAS chap bo‘sh U HOLDA AKS HOLDA TAMOM TAMOM Nuqtalar   o‘rniga   qanday   ko‘rsatmalar   qo‘yilishi   kerak?   Birinchi   bo‘lib, devorgacha bo‘lgan masofani kamaytirish, ya’ni vaziyatni soddalashtirish uchun chapga   ko‘rsatmasini   bajarish   kerakdir.   Keyin   yana   ikkilangan   sakrash protsedurasini chaqirish lozim. So‘ngra — devorgacha bo‘lgan masofa ikki marta katta bo‘lishi uchun o‘ngga ikki qadam tashlash kerak bo‘ladi. Demak, har bir chapga bir qadam uchun o‘ngga ikki qadam yurish mos keladi. mashq 1)Ikkilangan sakrash protsedurasini oxirigacha yozib chiqing. 2)EMAS chap bo‘sh shartini chap bo‘sh sharti bilan almashtirib, boshqa ikkilangan sakrash protsedurasi variantini yozing. 3)Agar   Robotning   chap   devorgacha   boshlang‘ich   masofasi   quyidagicha   bo‘lsa, Robotni ikkilangan sakrash protsedurasini bajarishidagi qadamlari ketma­ketligini yozib chiqing: a) ikkita katak; b) uchta katak. Rekursiyadan chiqish Rekursiv protseduralami har qanday Ijrochi uchun yozish mumkin. Masalan, Robotni kvadrat bo‘ylab yurishi uchun rekursiv protsedura yozaylik. masala Tomoni 5 ga teng kvadratni chizish rekursiv protsedurasini yozing. Javob. PROT rekursiv kvadrat BOSHLANISH oldinga oldinga oldinga oldinga oldinga o‘ngga rekursiv kvadrat TAMOM Bu   protsedura   qanday   ishlashini   ko‘rib   chiqamiz.   Demak,   rekursiv   kvadrat protsedurasi chaqirilganda oldinga oldinga oldinga oldinga oldinga o‘ngga ko‘rsatmalari   bajariladi.   Bunda   Robot   kvadratning   tomoni   bo‘ylab   yurib   90 gradusga  buriladi.  Keyin yana  rekursiv kvadrat   protsedurasi   chaqiriladi.  Robot kvadratning boshqa tomoni bo‘ylab yurib o‘ngga buriladi. Keyin yana rekursiv kvadrat protsedurasi chaqiriladi. Yana ikki tomon o‘tilgach kvadrat bo‘ylab yurish yakunlanadi.   Lekin   nimadir   bo‘ldi?   Robot   to‘xta­   masdan   yana   shu   kvadrat bo‘ylab yurishni davom ettirmoqda. Bu esa cheksiz davom etadi — algoritm siklga tushib qoldi. Vaziyat yoqimsiz. Biz doimo siklga tushib qolmaslikka harakat qilar edik. Bu holda undan qutulishning chorasi bormikan? Taas­ sufki, yo‘q. Haqiqatan, rekursiv protseduraning chaqirilishi cheksiz davom etmasligi uchun protseduraga chaqirilish yuzaga kelmaydigan shart kiritish kerak. Lekin bu Robotda bunday shart   yo‘q.   Robotning   algoritmi   uning   holatidan   qa’tiy   nazar,   bir   xilda bajarilaveradi. Shu kabi, Dehqon, Suvchi, Chigirtka, Oshiruvchi, Zohid kabi Ijrochilarda shart Sharti yo‘q Ijrochilar uchun rekursiv protseduralarni qo‘llamang! yo‘q. Bu Ijrochilar uchun rekursiv protseduraning qo‘llanishi yoki siklga tushib qolinadi yoki keyingi ko‘rsatmani bajarish mumkin bo‘lmay qolib, INKOR yuzaga keladi. Shuning uchun Bu   qo‘llanmada   ko‘rib   chiqilgan   Ijrochilardan   faqat   Kamayti­   ruvchi   va Rekursiv protseduralarni yozganda rekursiv chaqirish yuzaga kelmaydigan shart ko‘rsatilishi kerak. Robotda shart bor. Demak, faqat shu ikki Ijrochi uchun rekursiv protseduralarni yozish ma’noga ega. Bizning mulohazalarimizdan shunday xulosaga kelish mumkin: Bu   juda   kerakli   xulosa!   Shuning   uchun   ham   avvalgi   bo‘limda   algoritm namunalarini keltirganimizda, rekursiv protsedu­ ralarning shunday shartlarini va zaruriy amallarining tavsifini yozishdan boshlaganmiz. masala 7.3­ Quyidagi masalalarda rekursiv chaqirish yuzaga kelmaydigan shartlarni hamda bu holda qanday amallar bajarilishi zarurligini ko‘rsating: a) kamaytiruvchi tomonidan ixtiyoriy sondan 0 ni hosil qilish; b)robot o‘tish joyi bo‘lgan gorizontal devor tagida turibdi. O‘tish joyi chapda yoki o‘ngdaligi noma’lum. O‘tish joyini toping; d) robot   o‘tish   joyi   bo‘lgan   gorizontal   devor   tagida   turibdi.   O‘tish   joyi Robotdan chapda. Robot undan o‘tib boshlang‘ich holati ustiga borib turishi kerak; e) robotdan yuqorida bo‘yalgan katak bor. Robot maydonida devorlar yo‘q. Robotni bo‘yalgan katakdan yuqoridagi shunday katakka olib kelingki, Robot bilan bo‘yalgan katak orasidagimasofa Robotning boshlang‘ich holatidagi katak bilan bo‘yalgan katak orasidagi masofadan uch marta katta bo‘lsin. Qachon rekursiyasiz ishlash mumkin Ko‘rinishidan sodda ko‘ringani bilan rekursiya bilan ishlash ancha murakkab. Haqiqatan, Dehqon, Suvchi, Chigirtka uchun birinchi  algoritmlarimizni  eslang. Ularning to‘g‘riligini tekshirish juda oson edi. Biz Ijrochining har bir ko‘rsatmadan keyingi holatini kuzatib turar va barcha ko‘rsatmalar bajarilgandan keyin uning holati masala shartini qanoatlantirishiga ishonch hosil qilar edik. Takrorlash     unchalik   murak­ kablashtirmadi.   Ijrochining   harakati   avvalgidek   uning   holatiga   bog‘liq   emasdi. tuzilmasining   kiritilishi   tekshirishni Yagona qo‘shimcha qiyinchilik shundan iborat ediki, juda qisqa yozuvli algoritm bajarilishi natijasida Ijrochi juda ko‘p amallarni bajarishi kerak bo‘lardi. Shart kiritilishi algoritmning to‘g‘riligini tekshirishda bosh­ qacha aks etadi. Endi   Ijrochining  bajarishi   kerak  bo‘lgan   ko‘rsatmalar   ketma­ketligi   Ijrochining holatiga bog‘liq bo‘ldi — ish boshida Kamaytiruvchi ekranida qanday son aks etib turardi, Robot maydonida devorlar qanday joylashgan, Robot maydonining qaysi kataklari bo‘yalgan. Algoritmning oddiygina bajarilishi va to‘g‘ri natijaning olinishi algoritm to‘g‘ri ekanligiga   ishontira   olmaydi.   Algoritm   biz   tekshira   olgan   yoki   tekshirishni xohlagan hollardagina emas, balki ixtiyoriy holda ham to‘g‘ri ishlashiga ishonch hosil qilishimiz kerak. Albatta, ishonch hosil qilishning eng yaxshi usuli — bu algoritm ishining to‘g‘riligini isbotlashdir. Rekursiyani   qo‘llash   yana   tekshirish   qiyinchiligini   chuqur­   lashtiradi. Haqiqatan, biz endi qaysi ko‘rsatma bajarilayotganini kuzatibgina qolmasdan, bu ko‘rsatma qayerdan paydo bo‘lganini ham bilishimiz kerak. Aytaylik, 7.1­masala yechimidagi simmetriya rekursiyasi ishini tekshirayotib, navbatdagi   chapga   ko‘rsatmasi   rekursiv   protsedurani   uchinchi   yoki   beshinchi chaqirishda   paydo   bo‘lgani   va   hokazoni   yodda   saqlashimiz   kerak.   Yana   agar rekursiv protseduralar algoritmda ko‘p bo‘lib, bir­birini chaqirsa­chi? Tekshirish   qiyinligi   —   bu   rekursiyalardan   foydalanishdan   tiyilishning sabablaridan   faqat   bittasidir.   Boshqa   sabablar   ham   bor:   rekursiyali   dasturlar rekursiyasiz dasturlarga nisbatan kom­ pyuterda bajarayotganda sekin ishlaydi va xotiradan   ko‘p   joy   talab   qiladi;   rekursiyali   dasturlarni   rekursiyasiz   dasturlarga almashtirayotganda masalaga boshqa tomondan qarashga yor­ dam beruvchi ajoyib fikrlar   paydo   bo‘lishi   mumkin.   Shu   sababli,   masalaning   rekursiv   yechimini topgach, yana o‘ylab ko‘ring: rekursiyasiz ishlash mumkin emasmikan? masala Kamaytiruvchi uchun ixtiyoriy sonni eng kam qadamda 0 ga olib keluvchi   sonlar   uchun   protsedurangiz rekursiv   protsedura   bajarilayotgandagi Kamaytiruvchining ko‘rsatmalar ketma­ketligini yozing: tuzing.   Quyidagi a) 5; b) 9; d) 14. Kataklarni   bo‘yab,   Robot   bilan   ishlaganda   rekursiyadan   qutulish   mumkin. Bunda   bo‘yalgan   kataklar   xotira   vazifasini   o‘taydi.   Bu   holda   bo‘yalgan   sharti Robot bu katakdan o‘tgan yoki o‘tmaganini bilish uchun imkon beradi. masala Robot   devordan   yuqorida   qandaydir   masofa   uzoqlikda   turibdi.   Quyidagi imkoniyatlarda   Robotni   devorgacha   olib   borib   joyiga   qaytarib   olib   keluvchi protsedura tuzing: a) rekursiyani ishlatish mumkin; b) bo‘yash mumkin, rekursiyani ishlatish mumkin emas. Bu masalalardan birortasi ham sizga qiyinchilik keltirib chiqarmaydi, deb umid qilamiz. Oraliq chaqirish protsedura     orqali   rekursiv Ba’zan   protseduralarni   yozganda   uning   o‘zini   o‘zining   ichida   boshqa protsedura  orqali  chaqirgan qulay. To‘g‘ri  to‘rtburchakni  bo‘yash  masalasining rekursiv yechimini qaraymiz. masala Robot devorlar bilan o‘ralgan to‘g‘ri to‘rtburchakning chap quyi burchagida turibdi. To‘g‘ri to‘rtburchakning ichida devorlar yo‘q. To‘g‘ri  to‘rtburchakning barcha kataklarini bo‘yash algoritmini tuzing. Yechim.   Ikkita   rekursiv   protsedurani   qo‘llaydigan   bo‘yash   algoritmini yozamiz: PROT to‘g‘ri to‘rtburchakni bo‘ya BOSHLANISH AGAR EMAS bo‘yalgan U HOLDA yo‘lakni bo‘ya va qayt TAMOM TAMOM va PROT yo‘lakni bo‘ya va qayt BOSHLANISH TOKI yuqori bo‘sh BAJAR bo‘ya yuqoriga TAMOM TOKI quyi bo‘sh BAJAR quyiga TAMOM AGAR o‘ng bo‘sh U HOLDA o‘ngga to‘g‘ri to‘rtburchakni bo‘ya TAMOM TAMOM Endi algoritm bitta ko‘rsatmadan iborat bo‘ladi. to‘g‘ri to‘rtburchakni bo‘ya Bizning yechimimizda to‘g‘ri to‘rtburchakni bo‘ya protsedurasi yo‘lakni bo‘ya va   qayt   protsedurasini   chaqiradi.   O‘z   navbatida,   yo‘lakni   bo‘ya   va   qayt protsedurasi to‘g‘ri to‘rtburchakni bo‘ya protsedurasini chaqiradi. Shunday qilib, to‘g‘ri to‘rtburchakni bo‘ya protsedurasi o‘zini­o‘zi oraliq yo‘lakni bo‘ya va qayt protsedurasi orqali, yo‘lakni bo‘ya va qayt protsedurasi o‘zini o‘zi oraliq to‘g‘ri to‘rtburchakni bo‘ya protsedurasi orqali chaqiradi. Bu holda ikkala protsedurani rekursiv deb hisoblaymiz va ular bilan oddiy protsedura kabi muomala qilamiz. Mavzu: Algoritmlarni baholash me’zonlari va tahlil qilish usullari. Ikki tomonlama algoritmlar. Chiziqli ro’yxatlar va ular ustida asosiy amallar. Algoritm sifatini baholashning mezonlari 2.1.                 Algoritmni to’g’riligini tekshirish Dastur   to’g’riligini   isbotlashning   eng   keng   tarqalgan   turi   ­   bu   uni   testlardan o’tkazishdir. Algoritmni   tekshirishda   nazoratchi   boshlang’ich   ma’lumotlarni   majmui algoritmik test deb nomlanadi. To’g’ri   deb   shunday   algoritmga   aytiladiki,   u   masalaning   qo’yilishida   talab qilinadigan natijani har qanday ruxsat etilgan boshlang’ich ma’lumotlar bilan ham shakllantirib biladi. Odatda, dastur bergan natijalar ma’lum bo’lgan yoki qo’lda hisoblangan ma’lumotlar bilan taqqoslanadi, va ular to’g’riligi aniqlansa dastur to’g’ri   ishlaydi   degan   hulosaga   kelish   mumkin.   Ammo   bu   usul   bilan foydalanuvchini   hamma   shubhalardan   xalos   qilib   bo’lmaydi,   ya’ni   dastur ishlamaydigan hamma holatlarni hisobga olib bo’lmaydi. Gudman va Xidetniyemi [2] lar tomonidan algoritm to’g’riligini isbotlash uchun quyidagi uslubiyat taklif qilingan. Algoritm 0 dan m gacha bo’lgan qadamlar ketma­ketligi ko’rinishida tavsiflangan deb tahmin qilaylik.Har bir qadam uchun qandaydir asoslanishni taklif etamiz. Xususan,   qadamdan   oldin   va   keyin   ishlaydigan   shartlar   haqida   lemma   kerak bo’lishi mumkin. Shu bilan birgalikda, algoritm chekliligining isbotini ham taklif etamiz, va hamma ruxsat etilgan kiritish ma’lumotlarini tekshirib, hamma mumkin bo’lgan chiqarish ma’lumotlarni olamiz. Algoritmni to’g’riligi bilan samaradorligi o’rtasida hech qanday aloqa yo’qligini ta’kidlab o’tamiz.Aslida hamma talablarga bir xil yahshi javob beradigan algoritm kamdan­kam ishlab chiqiladi. Algoritmni amalga oshirish Algoritmni amalga oshirish deganda, EHM uchun dasturni yozish deb tushuniladi. Buning uchun quyidagi savollarga javob berish kerak: 5.1. 5.2. 5.3. 5.4. 5.5. 5.6. Dastur yozish yoki tuzishning hilma­hil usillari va uslublari mavjud. Asosiy o’zgaruvchilarni aniqlash. O’ zgaruvchilarning turlarini aniqlash. Nechta massiv yoki fayllar va qanday kattalikda ular kerak bo’ladi? Bog’lanilgan ro’yhatlardan foydalanish ma’nolimi? Qanday dasturiy qismlar kerak bo’lishi mumkin (tayyor bo’lsa ham)? Qaysi dasturlash tilini tanlash? Algoritmni va uning murakkabligini tahlil qilish Algoritmni tahlil qilishdan maqsad ­ algoritmga ma’lumotlarni aniq muvaffaqiyatli qayta ishlash uchun kerak bo’ladigan xotira hajmi va ishlash vaqtining baholari va chegaralarini   olish.   Bir   masalani   yechadigan   ikki   algoritmni   taqqoslash   uchun qandaydirsonli mezon topish kerak. Faraz qilaylik, A ­ qandaydir bir turkumdagi masalalarni yechadigan algoritm, n ­ esa shu turkumdagi alohida bir  masalaning kattaligi.Umumiy holda, n ­ oddiy skalyar yoki massiv yoki kiritiladigan ketma ­ ketlikning uzunligi bo’lishi mumkin. / л   (n) ­ n kattalikdagi ixtiyoriy masalani yechadigan algoritm A bajarish kerak bo’lgan   asosiy   amallami   (qo’shish,   ayirish,   taqqoslash,...)   yuqori   chegarasini beradigan ishchi funksiya. Algoritmningsifatini baholash uchun quyidagi mezonni ishlatamiz. Agar  f A ( n )   o’sish tartibi  n   dan bog’liq bo’lgan polinomdan katta bo’lmasa, A algoritm polinomial deb aytiladi, aks holda algoritm A eksponensial hisoblanadi. Shular bilan birgalikda tahlil jarayonida ko’p matematik fanlarda standart bo’lgan iboralar ishlatiladi. f A (n) funksiya O[g(n)] deb belgilanadi, va lim ­­­­ = const Ф 0 bo’lganda, uni n “ g ( n ) tartibi katta n lar uchun g(n) deb qabul qilinadi. Demak f(n)=O[g(n)]. f A (n) funksiyasi o[z(n)] deb katta n lar uchun belgilanadi, va unda lim = 0 n “ z ( n ) sharti bajariladi. Bu begilar “katta O” va “kichik o” deb nomlanadi. Agar  f(n)=O[g(n)] bo’lsa, ikkala funksiya ham n ^ w bo’lganda bir xil tezlikda o’sadi. Agarf(n)=O[g(n)] bo’lsa,unda g(n), f(n) nisbatan ancha tez o’sadi. Demak, p (n)  ­ qandaydir n o’zgaruvchidan bog’liq va k darajadagi polinom fA (n) = oPk (n) bo’lganda algoritm polynomial uchun fA (n) = о [ pk (n)] yoki hisoblanadi, aks holda algoritm eksponensial. Eksponensial   algoritm   yahshi   ishlamaydigan   deb   hisoblanadi.Agar   algoritmlar eksponensial   bo’lsa,   ular   orasida   eng   samaralisini   topish   kerak,   n   kattalikdagi masalani  о(2n)  qadamda yechadigan algoritm  о(n.)  yoki  о(nn) qadamda masalani yechadigan algoritmdan afzalroq.Dasturni tekshirish Biz   dasturni   har   bir   qismini   tekshiradigan   kirituvchi   ma’lumotlar   to’plamini tanlashimiz kerak.Ko’p murakkab algoritmlarni matematik tomondan tadqiq qilish yoki   juda   qiyin   yoki   mumkin   emas.   Bunday   holatlarda   algoritmni   faoliyat jarayonida va qiyinligi bo’yicha tekshiradi. Bundan tashqari dasturlarni hisoblash imkoniyatlarini   aniqlash   uchun   ham   testlash   maqsadga   muvofiq.Ko’p   dasturlar qandaydir kiritiladigan ma’lumotlar bilan yahshi ishlasa, boshqalari bilan yomon ishlaydi.“Yahshi”   lardan   “yomon”   larga   o’tish   “mayin”   bo’lish   kerak.Testlash uchun   ma’lumotlar   dasturning   qiyinligiga,   mavjud   vaqt   resurslariga,   kiritish­ chiqarishsoniga bog’liq holda tanlanadi. Bu yerda analitik va eksperimental tahlil bir­birini to’ldiradi. Hujjatlashtirish O’zingiz yozmagan dastur kodini o’qish juda qiyin.Bu muammoni hujjatlashtirish yordamida   yechsa   bo’ladi.   Hujjatlashtirish   o’z   ichiga   hamma   yordamchi ma’lumotlarni   oladi   va  dasturda  nima   bajarilishini   tushuntirib  beradi,   xususan, blok­sxemalardagi   boshqarishni   uzatish,   berilganlarni   kiritish­chiqarish   shaklini batafsil   tavsif   qilish,   siklning   parametrlari,   yordamchi   local   va   global proseduralarni bajarilishi va boshqalar. Hujjatlashtirishning eng asosiy qoidasi bu “boshqalar yozgan dasturlarni qanday ko’rishni istasangiz, o’zingiz ham dasturni shunday ko’rinishda rasmiylashtiring”. Masalalar yechish. 1 ­ misol. Berilgan to 'rt xonali butun sonning raqamlari ko paytmasini toping. Mavzu: Tarmoqlar. Daraxtlar, ularning turlari. Tanlash va joylashtirish turkumidagi murakkablikka ega saralash algoritmlari. Algoritmni tasvirlash usullari Algoritmlarni   tasvirlashning   turli   usullari   mavjud.   Quyida   algoritmlarni tasvirlashning keng tarqalgan usullarini ko‘rib chiqamiz. 1. Algoritmning so‘zlar yordamida ifodalanishi Avval   keltirilgan   bir   qator   misollar   inson   og‘zaki   nutqida   qo‘llaniladigan so‘zlar orqali ifodalangan edi (masalan, ko‘chadan o‘tish algoritmi, g‘ishtlar sonini hisoblash   algoritmi).   Algoritmning   bunday   tasvirlash   usulida   ijrochi   uchun ko‘rsatma jumlalar orqali ko‘rsatma shaklida beriladi. Qo‘llanmada, asosan, shu usuldan foydalanamiz. 2. Algoritmning formulalar yordamida ifodalanishi Bu   usul   matematika,   fizika,   kimyo   va   biologiya   kabi   fanlarda   ko‘plab qo‘llanilaniladi. Yodingizda bo‘lsa, so‘zlar yordamida ifodalangan g‘ishtlar sonini hisoblash algoritmini formula orqali ifodalagan edik. Formuladagi «+», «—», «х», «:»  kabi arifmetik amallarning tartibiga rioya qilgan holda bajarilishi ham algo­ ritmga misol bo‘ladi. Avval berilgan ««ax2+ bx+c =0 (аф 0) ko‘rinishidagi kvadrat tenglamani yechish» algoritmining quyidagi formula orqali ifodasi bilan tanishsiz: ­b ±\Jb2 ­ 4ac x1,2 = 2a Bilasiz, formuladagi amallar ma’lum bir tartib bilan bajarilishi shart. 3. Algoritmning jadval yordamida ifodalanishi Algoritmning   bu   ko‘rinishda   berilishi   ham   sizga   tanish.   Ma­   salan, matematikada qo‘llanib kelinayotgan Bradis jadvali deb nomlangan to‘rt xonali matematik   jadval,   lotareya   yutuqlar   jadvali,   Mendeleyev   kimyoviy   elementlar jadvali. Bunday jad­ vallardan foydalanish ma’lum bir algoritm qo‘llashni talab etadi. Biror   funksiyaning   grafigini   chizish   uchun   ham   funksiyaning   argument qiymatlariga mos qiymatlar jadvalini hosil qilamiz. Bu ham algoritmning jadval ko‘rinishiga misol bo‘ladi. 4. Algoritmning grafik shaklda ifodalanishi Algoritmning bu ko‘rinishda ifodalanishi matematikada chi­ zilgan grafik, kerakli uyni oson topish uchun dahalarda o‘rnatil­ gan uylarning joylashish sxemasi, avtobuslarning yo‘nalish sxemasi orqali sizga tanish. Algoritmlash asoslarini o‘rganishning yana bir qulay grafik shakli —  blok­ sxema  usulidir. Blok­sxemalar bir yoki bir nechta buyruq yoki ko‘rsatmani aks ettiruvchi   maxsus   geometrik   shakllar   —   bloklardan   tashkil   topadi.   Bloklar yo‘nalish chiziqlari orqali tutashtiriladi. misol R radiusli doiraning yuzasini hisoblash algoritmi tuzilsin. Avval aytib o‘tilganidek, algoritmda boshlang‘ich qiymatlar o‘rniga ularning nomlari   ishtirok   etishi   mumkin   va   bu   algoritm­   ning   ommaviylik   xossasiga aloqadorligini   bildiradi.   Bu   masalada   ham   radiuslar   guruhi  R  nomi   bilan berilmoqda   va   uning   joiz   boshlang‘ich   qiymati   ixtiyoriy   haqiqiy   son   bo‘lishi mumkin.   Eslatib   o‘tamiz,   algoritmda   turli   nomlar   ishtirok   etishi   va   ular boshlang‘ich qiymatlar va natijalar nomi bo‘lishi ham mumkin. Masalaning quyida keltirilgan yechimidagi  S  nomi masalani yechimi bo‘ladigan natijalar guruhining nomidir. Bu masala algoritmini ikki xil usulda: so‘zlar yordamida va grafik shaklda tuzamiz: 1) Boshlanish; 2) R ning qiymati  aniqlansin; 3) R ning R ga ko‘paytirib,  S deb olinsin; 4) S ni 3,14 ga ko‘paytirib,  S deb olinsin; 5) javob sifatida S yozilsin; 6) tugallansin. S:=3.14*R*R 5. Algoritmning dastur shaklida ifodalanishi Ma’lumki,   kompyuter   dasturlar   asosida   ishlaydi   va   bosh­   qariladi.   Siz hozirgacha   MS   Word,   MS   Paint   va   MS   Excel   kabi   amaliy  dasturlar  bilan ishladingiz. Lekin har bir amaliy dastur ham juda katta va murakkab algoritmning bir   ko‘rinishidir.   Demak,   bu   kabi   algoritmlar   bajarilishi   uchun   ular  algoritm ijrochisiga, ya’ni kompyuterga tushunarli bo‘lishi lozim. Odatda,   algoritmning   kompyuter   tushunadigan   tilda   yozilishi  dastur  deb ataladi.   Kompyuter   tushunadigan   til   esa  dasturlash   tili  deb   ataladi.   Jahonda hozirgi   kunda   minglab   dasturlash   tillari   mavjud   va   yana   rivojlanib   bormoqda. Hozirgi kunda keng tarqalgan va o‘rganish uchun qulay bo‘lgan BASIC, Pascal, VBA, Delphi, C dasturlash tillari o‘rganiladi. Algoritmning asos turlari Qo‘llanmada, asosan, algoritmuk tafakkurning rivojlan­ tirishini maqsad qilib qo‘ygan bo‘lsak­da, algoritm to‘g‘risida tasavvuringizni kengaytirish maqsadida yana ba’zi ma’lumotlarni berishni lozim topdik. Har qanday algoritm mantiqiy tuzilishiga, ya’ni bajarilishiga qarab uch asosiy turga bo‘linadi:  chiziqli (ketma­ketlik), tarmoq­ lanuvchi  va  takrorlanuvchi. Algoritmikada   bu   algoritmlar   asosida   turli­tuman   yangi   algoritmlar   hosil qilinadiki, ular ham o‘z navbatida mustaqil ahamiyatga ega bo‘ladi. Chiziqli   algoritmlar.  Bu   turdagi   algoritmlarda   hech   qanday   shart tekshirilmaydi.   Shu   sababli   barcha   ko‘rsatmalar   ketma­   ket   bajarib   boriladi. «G‘ishtlar   sonini   hisoblash»,   «Doira   yuzini   hisoblash»­   algoritmlari   chiziqli algoritmlarga misol bo‘ladi. Le­ kin hayotimizdagi juda ko‘p jarayonlar shartlar asosida bosh­ qariladi. Tarmoqlanuvchi   algoritmlar.  Shartga   muvofiq   bajariladigan   ko‘rsatmalar  tarmoqlanuvchi   algoritm­   lar  deb   ataladi. ishtirok   etgan   algoritmlar Algoritmlarning bu turi hayotimizda har kuni va har qadamda uchraydi. Eshikdan chiqishimiz   eshik   ochiq   yoki   yopiqligiga,   ovqatlanishimiz,   qornimiz   och   yoki to‘qligiga yoki taomning turiga, ko‘chaga kiyinib chiqishimiz ob­havoga, biror joyga borish uchun transport vositasini tanlashimiz to‘lash imkoniyatimiz bo‘lgan pulga   bog‘liqdir.   Demak,   tarmoqlanuvchi   algoritmlar   chiziqli   algoritmlardan tanlash imkoniyati bilan farqlanar ekan. Avval   yoritilgan   «Ko‘chadan   o‘tish»,   «Kvadrat   tenglamani   yechish» algoritmlari ham tarmoqlanuvchi algoritmlarga misol bo‘ladi. misol Algoritmi formula yordamida berilgan funksiyaning   qiymatini   hisoblashga   doir   tarmoqlanuvchi   algo­   ritmni   blok­ sxema yordamida tasvirlaymiz:  1) Boshlanish; 2) A va B kiritilsin; 3) agar A > B bo‘lsa 4­bandga o‘tilsin; Berilgan   ikkita  A  va  B  sonlardan   kattasini   topish   (IKT   nomi   bilan ataluvchi) algoritmini so‘zlar va blok­sxema yordamida tuzing. aks holda 5­bandga o‘tilsin; 4) natija A deb olinsin va 6­bandga o‘tilsin; 5) natija B deb olinsin; 6) tugallansin. Bu misoldan quyidagicha xulosa chiqarish mumkin: agar A > B shart bajarilsa 5­banddagi  ko‘rsatma bajarilmaydi, aks holda, ya’ni  A < B  bo‘lsa, 4­banddagi ko‘rsatma   bajarilmaydi.   IKT  algoritmi  tarmoqlanishni  yaqqol  tasavvur  qilish imkoniyatini beradi. Takrorlanuvchi   (siklik)   algoritmlar.  Masalalarni   tahlil   etish   jarayonida algoritmdagi   ba’zi   ko‘rsatmalar   takroran   bajarilishini   kuzatish   mumkin. Hayotimizda ham juda ko‘p jarayonlar tak­ rorlanadi. Masalan, darslarning har hafta  takrorlanishi,  har   kuni   nonushta  qilish  yoki  maktabga  borish  va hokazo. Ko‘rsatmalari takroriy bajariladigan algoritmlar  takrorlanuvchi algoritmlar deb ataladi. Takrorlanuvchi algoritmlar  «I  := I +  1»,  «S := S +  I»  yoki «P : = P *  I» ko‘rinishidagi   ko‘rsatmalarning   ishtiroki   bilanajralib   turadi   (*   —   ko‘paytirish amali). Bunday ko‘rsatmalarning mazmunini tushunish uchun takrorlanishning bir nechta qada­ mini ko‘rib chiqamiz. Odatda,   yig‘indi   uchun   boshlang‘ich   qiymat   (inglizchadan   SUMM,   ya’ni yig‘indi ma’noli so‘zning bosh harfi) S:= 0 va ko‘paytma uchun (inglizchadan PRODUCT, ya’ni ko‘paytma ma’noli so‘zning bosh harfi) P: = 1 deb olinadi, chunki bu qiymatlar, ya’ni 0 va 1 lar, mos ravishda, yig‘indi va ko‘paytmaning natijasiga ta‘sir etmaydi: 1­ qadamda I := 1 bo‘lsin: S := S + I = 0 + 1 = 1, P := P * I = 1 * 1 = 1; 2­ qadam: I := I + 1 = 1 + 1 = 2: S := S + I = 1 + 2 = 3, P: = P * I = 1 * 2 = 2; 3­ qadam: I := I + 1 = 2 + 1 = 3: S := S + I = 3 + 3 = 6, P := P * I = 2 * 3 = 6; 4­ qadam: I := I + 1 = 3 + 1 = 4: S := S + I = 6 + 4 = 10, P := P * I = 6 * 4 = 24. Algoritmikada, matematikada bunday bo‘lishi mumkin emas, I = I + 1 deb yozilishi mumkin. Bu yozuvda avval o‘ng tomondagi qiymat hisoblanib, so‘ng bu qiymat chap tomondagi nomning qiymati deb olinadi. 1.8­ 1 dan 1000 gacha bo‘lgan sonlar yig‘indisini, ya’ni S = 1+2+3+...+ 1000 ni misol hisoblash algoritmini tuzing. C Boshlanish j ­ ­ ­ ­T­­­­­ 1) Boshlansin; 2) S = 0 deb olinsin (ya’ni S:= 0); 3) I   ning   qiymati   1   deb olinsin (ya’ni I:= 1); 4) S   ga   I   qo‘shilib,   S   deb olinsin (ya’ni S:= S+I); 5) I   ga   1   qo‘shilib   I   deb olinsin (ya’ni I:= I+1); 6) agar I < 1000 bo‘lsa 4­bandga o‘tilsin; 7) javob deb S olinsin; 8) tugallansin. So‘zlar   bilan   ifodalangan   algoritmda   blok­sxema   bilan   mu­   tanosiblikni bildirish   uchun   qavslar   ichida   izohlar   berib   bordik.   Odatda,   takrorlanuvchi algoritmlarda «I:= I+1» ifoda sanagich deb yuritiladi. Bu misol yechimini chiziqli algoritm  shaklida  tashkil  etish  ham  mumkin. Buning uchun arifmetik progres­ siyaning   1000   ta   hadi   yi‘gindisini   hisoblash   formulasidan   foydalanish   kifoya (algoritmni mustaqil tuzing). Lekin keyingi misolda bunday qilish ancha mushkul. misol 1.9­ 2   xonali   sonlar   ichidan   raqamlari   yig‘indisi   7   ga   teng   sonlar   yig‘indisini hisoblash algoritmini tuzing ([a] — a sonining butun qismi, / — bo‘lish amali). Ko‘rib  o‘tilgan  algoritmlarga  nazar   ziqli, tarmoqlanuvchi  yoki  takrorlanuvchi  qismlardan  tashkil  topganligini  kuzatish mumkin. tashlasak,  algoritmlar  chi­ Demak,   inson   hayotida   uchraydigan   algoritmlar,   asosan,   shu   uch   turdagi algoritmlarning uzviy birligi sifatida namoyon bo‘ladi. Nazorat savollari va topshiriqlar 1. Algoritm nima?Misollarkeltiring. 2. Algoritmning qanday xossalarini bilasiz ? 3. Boshlang ‘ich qiymatlar deganda nimani tushunasiz ? 4. Hamma bajara olishi uchun algoritm qanday xossaga ega bo ‘lishi kerak? 5.Tushunarlilik   xossasi   bajariladigan   va   bajarilmaydigan   ko*rsatmalar   ketma­ ketligiga misollar keltiring. 6.Ko   ‘rsatmalar   ijrochiga   tushunarli   bo   ‘lishi   uchun   qanday   sistemadan   olinishi kerak? 7.Ijrochi algoritmni so ‘zsiz bajarishi uchun qanday xossa ahamiyatli? Javobingizni izohlang. 8. Algoritmning diskretlilik xossasini misollar yordamida tushuntiring. 9. Algoritmning natijaviylik xossasini misollar yordamida tushuntiring. 10.Natijaviylik   xossasi   bajarilmaydigan   ko   Rsatmalar   ketma­ketligiga   misollar keltiring.Algoritmning ommaviylik xossasini misollar yordamida tushuntiring. 11.Algoritmning qanday tasvirlash usullari bor? 12.Algoritmning so ‘zlar orqali ifoda etilishiga hayotiy misollar keltiring. 13.Qaysi fanlarda algoritmni formulalar yordamida berish qulay? 14.Algoritmning   formulalar   orqali   ifoda   etilishiga   fizika   fanidan   misollar keltiring. 15.Algoritmning jadval ko‘rinishida berilishiga misollar keltiring. 16.Algoritmning grafik shaklda berilishiga misollar keltiring. 17.Blok­sxemaning asosiy elementlariga misollar keltiring. 18.Algoritmning dastur shaklida berilishiga misollar keltiring. 19. Qanday algoritmlar chiziqli algoritm deb ataladi? Chiziqli algoritmlarga hayotiy misollar keltiring. 20. Qanday algoritmlar tarmoqlanuvchi algoritm deb ataladi? Tarmoqlanuvchi algoritmlarga hayotiy misollar keltiring. 21. Qanday algoritmlar takrorlanuvchi algoritm deb ataladi? Takrorlanuvchi algoritmlarga hayotiy misollar keltiring. 22. Chiziqli,   tarmoqlanuvchi   va   takrorlanuvchi   algoritmlarning   bir­biridan farqini tushuntiring. 23.Uchta sondan kattasini (UKT) aniqlab beruvchi algoritm tuzing. 24.Berilgan sonning ishorasini aniqlovchi algoritm tuzing. 25. Quyidagi   ko   ‘rsatmalar   ketma­ketligi   qanday   algoritm   turiga   misol   bo ‘ladi? Algoritmlar natijasini aniqlang: a)  a: =3, x: =2 *a +a *a; b) x:=1, x: =x+11, x:=x*x­ 4; d) a:=15, b:=a, a:=a­b; a = ?, x= ? x=? a=?, b=? 26. Quyidagi   ko   ‘rsatmalar   ketma­ketligi   qanday   algoritm   turiga   misol   bo ‘ladi? Algoritmlar natijasini aniqlang: a) 1) a:=3; 2) agar a > 2 bo ‘lsa, u holda x:=2*a+a *a va 4­bandga o ‘tilsin; 3) x:= 9­a*x; 4) javobi x yozilsin; 5) tugatilsin; b) 1) x:=1; 2) agar x > 2 bo ‘lsa, u holda x:=x+11 va 4­bandga o ‘tilsin; 3) x:=x*x­4; 4) javobi x yozilsin; 5) tugatilsin; d) 1) a:=15; 2) b:= a; 3) agar a > b bo ‘lsa, u holda a:=a­b va 5­bandga o ‘tilsin; 4) a:=a+b; 5) javobi a, b yozilsin; 6) tugatilsin. Qo‘shimcha masalalar R­1. Robot kengligi 1 katak bo‘lgan gorizontal yo‘lakda turibdi. Undan chapda qayerdadir bo‘yalgan katak bor. Robotni turgan katagidan bo‘yalgan katakka borib, yana joyiga qaytarib keltiradigan algoritm tuzing. R­2.  Robot   kengligi   1   katak   bo‘lgan   yuqoridan   va   quyidan   devor   bilan chegaralangan gorizontal  yo‘lakda  turibdi. Undan o‘ngda qayerdadir  bo‘yalgan katak bor. Robot turgan katagiga bo‘yalgan katakka nisbatan simmetrik bo‘lgan chapdagi katakka borishi kerak (7.3­rasm). Mos algoritmni tuzing. R­3. Robot kengligi 1 katak bo‘lgan gorizontal yo‘lakda turibdi. Undan chapda qayerdadir devor bor. Robotni turgan katagidan devorgacha olib borib, yana joyiga Robot bu yerda turibdi Robot bu yerga o‘tishi kerak 7.3­rasm. qaytarib olib keladigan algoritm tuzing. R­4.  Robotni   o‘zidan   yuqorida   joylashgan   gorizontal   devor   yoniga   olib keladigan rekursiv algoritm tuzing. R­5. Robot o‘tgan katagini bo‘yab ketishi mumkin bo‘lsa, u holda a) R­1 b) R­3 masalalarni rekursiyasiz yeching. K­1.  Samarador   Kamaytiruvchi   uchun   rekursiv   protsedurani   chaqiradigan algoritm tuzing. Mavzu: Rekursiya va rekursiv funksiyalar. Matematik induksiya. Rekursiv va iteratsion algoritmlarni qiyoslash Programma       ta’minotini       yaratish       amalda       murakkab       jarayon hisoblanadi.   Programma   tuzuvchi   programma   kompleksini   bir   butunlikdagi   va uning har bir bo‘lagining ichki mazmunini va ularning sezilmas farqlarini hisobga olishi kerak bo‘ladi. Programmalashga tizimli yondoshuv shundan iboratki, programma tuzuvchi  oldiga qo‘yilgan masala oldindan ikkita, uchta va undan ortiq nisbatan kichik masala ostilarga bo‘linadi. O‘z navbatida bu masala ostilari ham   yana kichik masala ostilariga bo‘linishi mumkin. Bu jarayon toki mayda masalalarni oddiy standart amallar yordamida yechish mumkin bo’lguncha davom etadi. Shu yo‘l bilan masalani dekompozitsiyalash  amalga oshiriladi. Ikkinchi tomondan, programmalashda shunday holatlar kuzatiladiki, unda programmaning turli joylarida mazmunan bir xil algoritmlarni  bajarishga   to‘g‘ri keladi.     Algoritmning     bu     bo‘laklari asosiy yechilayotgan masaladan ajratib olingan   qandaydir   masala   ostini   yechishga   mo‘ljallangan   bo‘lib,   yetarlicha mustaqil qiymatga (natijaga) egadir. Misol uchun quyidagi masalani ko‘raylik:  Berilgan a ,a ,…,a , b ,b ,…,b  c ,c ,…,c  va x,y,z haqiqiy sonlar 0 1 30 0 1 30 0 1 30 yechish   xa+ x (a 30 29 1 0 2 (b­ ) a+…+    30  ( xc 1 z 30 ) 29 30 ) b+…+ y b+ y   29 ) 1  ... c 30 30 0 z ( xc 0 ifodaning qiymati hisoblansin. Bu misolni yechishda kasrning surat va maxrajidagi ifodalar bir xil algoritm bilan hisoblanadi va programmada har bir ifodani (masala osti) hisoblash uchun bu algoritmni   3   marta   yozishga   to‘g‘ri   keladi.   Masaladagi   30­darajali   ko‘phadni hisoblash algoritmini, masalan, Gorner algoritmini alohida, bitta nusxada yozib, unga turli parametrlar­ bir safar a vektor va x qiymatini, ikkinchi safar b vektor va y   qiymatini   hamda   c   vektor   va   (x+z)   qiymatlari   bilan   murojaat   qilish   asosiy masalani yechish mumkin bo‘ladi. Funksiyalar qo‘llanishining yana bir sababini quyidagi masalada ko‘rishimiz mumkin – berilgan chiziqli tenglamalar  sistemasini Gauss, Kramer, Zeydel usullarining birortasi bilan yechish talab qilinsin. U holda asosiy programmani quyidagi bo‘laklarga bo‘lish maqsadga muvofiq bo‘lar edi: tenglama koiffitsentlarini kiritish bo‘lagi, yechish usulini tanlash bo‘lagi, Gauss, Kramer, Zeydel usullarini amalga oshirish uchun alohida bo’laklar, natijani chop qilish   bo‘lagi.   Har   bir   bo‘lak   uchun   o‘z   funksiyadir   majmuasi   yaratib,   zarur bo‘lganda ularga bosh funksiya tanasidan murojaatni amalga oshirish orqali bosh masala yechish samarali hisoblanadi. Bunday hollarda programmani ixcham va samarali qilish uchun C++ tilida programma   bo‘lagini   alohida   ajratib   olib,   uni   funksiya   ko‘rinishida   aniqlash imkoni mavjud. Funksiya bu – C++ tilida masala yechishdagi kalit elementlaridan biridir. Funksiya parametrlari va argumentlari:[1(177­187), 3(51­56), 4(67­72)] Programmada   ishlatiladigan   har   qanday   funksiya   e’lon   qilinishi   kerak.   Odatda funksiyalar   e’loni   sarlavha   fayllarda   e’lon   qilinadi   va   #include   direktivasi yordamida programma matniga qo‘shiladi. Funksiya e’lonini funksiya prototipi tavsiflaydi   (ayrim   hollarda   signatura   deyiladi).   Funksiya   prototipi   quyidagi ko‘rinishda bo‘ladi:  (); Bu yerda  ­ funksiya ishlashi natijasida y tomonidan qaytaradigan   qiymatning   turi.   Agar   qaytariladigan   qiymat   turi   ko‘rsatilmagan bo‘lsa, kelishuv bo‘yicha funksiya qaytaradigan qiymat turi int deb hisoblanadi, ­ vergul bilan ajratilgan funksiya parametrlarining turi va nomlari ro‘yxati. Parametr nomini yozmasa ham bo‘ladi. Ro‘yxat bo‘sh bo‘lishi ham mumkin. Funksiya prototiplariga misollar: int almashsin(int,int); double max(double x, double y); void func(); void chop_etish(void); Funksiya prototipi tushirib qoldirilishi mumkin, agar programma matnida funksiya aniqlanishi uni chaqiradigan funksiyalar matnidan oldin yozilgan bo‘lsa. Lekin bu holat yaxshi uslub hisoblanmaydi, ayniqsa o‘zaro bir­biriga murojaat qiluvchi funksiyalarni e’lon qilishda muammolar yuzaga kelishi mumkin. Funksiya   aniqlanishi   –   funksiya   sarlavhasi   va   figurali   qavsga   (‘{‘,’}’) olingan qandaydir amaliy mazmunga ega tanadan iborat bo‘ladi. Agar funksiya qaytaruvchi   turi   void   turidan   farqli   bo‘lsa,   uning   tanasida   albatta   mos   turdagi parametrga ega return operatori bo‘lishi shart. Funksiya tanasida bittadan ortiq return   operatori   bo‘lishi   mumkin.   Ularning   ixtiyoriy   birortasini   bajarish   orqali funksiyadan   chiqib   ketiladi.   Agar   funksiyaning   qiymati   programmada ishlatilmaydigan bo‘lsa, funksiyadan chiqish uchun parametrsiz return operatori ishlatilishi mumkin yoki umuman return ishlatilmaydi. Oxirgi holda funksiyadan chiqish – oxirgi yopiluvchi qavsga yetib kelganda ro‘y beradi. Funksiya programmaning birorta modulida yagona ravishda     aniqlanishi kerak, uning e’loni esa funksiyani ishlatadigan modullarda necha marta yozilishi mumkin. Funksiya aniqlanishida sarlavhadagi barcha parametrlar nomlari yozilishi shart.  Odatda   programmada   funksiya   ma’lum   bir   ishni   amalga   oshirish   uchun chaqiriladi. Funksiyaga murojaat qilganda, u qo‘yilgan masalani yechadi va o’z ishini tugatishida qandaydir qiymatni natija sifatida qaytaradi Funksiyani   chaqirish   uchun   uning   nomi   va   undan   keyin   qavs   ichida argumentlar ro‘yxati beriladi: (, ,..., ); 1 2 n Bu   yerda   har   bir     ­   funksiya   tanasiga   uzatiladigan   va   keyinchalik hisoblash   jarayonida   ishlatiladigan   o‘zgaruvchi,   ifoda   yoki   o’zgarmasdir. Argumentlar ro‘yxati bo‘sh bo‘lishi mumkin. Funksiyalar ham o‘z tanasida boshqa funksiyalarni, o‘zini ham chaqirishi mumkin.   O‘z   tanasida   o‘zini   chaqiradigan   funksiyalarga   rekursiv   funksiyalar deyiladi. Oldingi     boblarda   ta’kidlab     o‘tilganidek,     C++   tilidagi     har   qanqay programmada albatta main() bosh funksiyasi bo‘lishi kerak. Ayni shu   funksiyani yuklagich  tomonidan  chaqirilishi   bilan   programma bajarilishi boshlanadi. Quyidagi   rasmda   bosh   funksiyadan   boshqa   funksiyalarni   chaqirish   va ulardan qaytish sxemasi ko‘rsatilgan. void F1(int Radius, char symbol) { … return; } int F2(bool YesNo, int Count, short Key ) { … return 0; } int main () { int x, b; Bool a; Char s; Short c; … F1(x,s); A=(x>0); … F2(a,b,c); … return 0; } 1­rasm. Bosh funksiyadan boshqa funksiyalarni chaqirish va qaytish Programma   main()   funksiyasini   bajarishdan   boshlanadi   va   “f1(x,y);”   – funksiya chaqirishgacha davom etadi va keyinchalik boshqaruv f1(x,y) funksiya tanasidagi   amallarni   bajarishga   o‘tadi.   Bunda   Radius   parametrining   qiymati sifatida   funksiya   x   o‘zgaruvchi   qiymatini,   Symbol   parametri   sifatida   y o‘zgaruvchisining   qiymati   ishlatiladi.   Funksiya   tanasi   return   operatorigacha bajariladi.   Return   operatori   boshqaruvni   main()   funksiyasi   tanasidagi   f1() funksiyasi chaqirilgan operatordan keyingi operatorga o‘tishni ta’minlaydi, ya’ni funksiyadan   qaytish   ro‘y   beradi.   Shundan   keyin   main()   funksiyasi   operatorlari bajarilishda davom etadi va “f2(a,b,c);” – funksiya chaqirishi orqali boshqaruv f2() funksiya tanasiga o‘tadi va hisoblash jarayonida mos ravishda YesNo sifatida a o‘zgaruvchisining,   cout   sifatida     o‘zgaruvchisining   va   key   sifatida   c o‘zgarchuvchisining   qiymatlari   ishlatiladi.   Funksiya   tanasidagi   return   operatori yoki   oxirgi   operator   bajargandan   keyin   avtomatik   ravishda   bosh   funksiyaga qaytish amalga oshiriladi. Aksariyat hollarda main() funksiyasining parametrlar ro‘yxati bo‘sh bo‘ladi. Agar   programmani   ishga   tushirishda,   buyruq   satrida   ma’lum   bir   parametrlarni uzatish (berish) zarur bo‘lsa, main() funksiyasining sintaksisi o‘zgaradi: int main(int argc, char* argv[]); Bu   yerda   argc   –   uzatiladigan   parametrlar   soni,   argv[]­   bir­biridan punktuatsiya belgilari (va probel) bilan ajratilgan parametrlar ro‘yxatini o‘z ichiga olgan massivga ko‘rsatkich. Quyida   funksiyalarni   e’lon   qilish,   chaqirish   va   aniqlashga   misollar keltirilgan: //  funksiyalar e’loni int mening_funksiyam(int Number, float Point); char Belgini_uqish(); void bitni_urnatish(short Num); void Amal_yoq(int,char);_ //  funksiyalarni chaqirish  result= mening_funksiyam (Varb1,3.14); symb=Belgini_uqish(); bitni_urnatish(3); Amal_yoq(2,Smb1); // funksiyalarni aniqlash int mening_funksiyam (int Number, float Point); {int x; … return x;} char Belgini_uqish(); { char Symbo1; cin>>Symbo1; return Symbo1; }; void bitni_urnatish(short number) (global_bit=global_bit|number;}; void Amal_yoq(int x, char ch){}; Funksiyaning programmadagi o‘rnini yanada tushunarli bo‘lishi uchun son kvadratini hisoblash masalasida funksiyadan foydalanishni ko’raylik.   Funksiya prototipini   sarlavha.h  sarlavha faylida   joylashtiramiz: long Son_Kvadrati(int); Asosiy   programmaga     ushbu     sarlavha       faylini     qo‘shish     orqali Son_Kvadrati() funksiya e’loni programma matniga kiritiladi: #include  #include “sarlavha.h” int main() { int uzgaruvchi=5; cout< long Son_kvadrati(int); int main() { int uzgaruvchi=5; cout<”; cin>>n; cout<<’[‘<>  sarlavha faylida joylashgan(3­ilova qarang):   foydalaniladi.       Bu     funksiyalar #include  #include  void chop_qilish (double Numb, double aniqlik=1,bool bayroq=true); int main() {double Mpi=­3.141592654; chop_qilish(Mpi,4, false); chop_qilish(Mpi,2); chop_qilish(Mpi); return 0; } void chop_qilish(double Numb, double aniqlik=1,bool bayroq=true) {if(!bayroq)Numb=fabs1(Numb); Numb=(int)(Numb*pow(10,aniqlik)); Numb=Numb/pow(10,aniqlik); cout< // funksiya prototipi  int sum (int a; int b); int main() { // lokal  o’zgaruvchi int x=r; cout< int f1(); int f2(); int main() { cout< //global o’zgaruvchi e’loni int test=100; void Chop_qilish(void); int main() { //lokal o’zgaruvchi e’loni int test=10; //global o’zgaruvchi chop qilish funksiyasini chaqirish Chop_qilish(); cout<<”Lokal o’zgaruvchi: “<