1-мавзу. Алгоритмик масалани ечиш асослари 4соат

 Машқлар 
Қадимий халқ бошқотирмаси. Дарё қирғоғида деҳқон, бўри, эчки ва карам бор. Деҳқон ўз 
қайиғида уларни нариги соҳилга олиб ўтиши керак. Бироқ, қайиқда фақатгина 2 та жой бор - деҳқон 
ва яна бир объект учун (яъни бўри, эчки ёки карам). Деҳқон бўлмаса бўри эчкини, эчки карамни еб 
қўйиши мумкин. Деҳқонга бу масалани ечиш учун ёрдам беринг ёки масала ечимга эга эмаслигини 
исботланг. (Эслатма, аниқлик учун деҳқонни вегетариан , лекин у карамни ёқтирмайди деб 
ҳисоблаймиз, шунинг учун қайиқда у карамни ҳам, эчки ҳам ея олмайди. Бундан ташқари, деҳқон 
“Қизил китоб” га киритилган ноёб зотдаги бўрига дуч келганни ҳисобга олиши керак.) 
Замонавий халқ бошқотирмаси. Тўрт одам йўлда бир йўналишда ҳаракатланишмоқда ва 
кўприкни кесиб ўтишни хоҳлайдилар. Сизнинг вазифангиз уларга 17 дақиқада нариги соҳилга 
ўтишга ёрдам беришдир. Кўча қоронғу ва уларда 1 та фонарча бор. Мост устида бир вақтда икки 
кишигина юра олади, бундан ташқари икки кишининг бирида фонар бўлиши керак. Фонарни бир 
қирғоқдан иккинчи қирғоқга отиб бўлмайди, уни фақат кўприк устидан олиб ўтиш мумкин. 
Кўприкдан ўтиш учун ҳамма ҳар хил вақт сарфлайди: биринчи одам- 1 дақиқа, иккинчи - 2 дақиқа, 
учинчи- 5 дақиқа ва тўртинчи - 10 дақиқа. Агар кўприк устидан икки киши ўтадиган бўлса, уларнинг 
юриш тезлиги секин юрувчи тезлиги билан тенглашади. Масалан, кўприкдан 1 ва 4 кишилар ўтса, 
нариги соҳилга 10 минутда боришади. Агар 4 одам фонарни нариги қирғоқга қайтарадиган бўлса, 
масала бошланган пайтдан 20 дақиқа ўтади ва сиз масалани ечишга улгурмайсиз. (эслатма, 
Интернетда тарқалган миш-мишларга кўра, Сиетл яқинида жойлашган, дастурий таъминот ишлаб 
чиқарувчи машҳур компаниялардан бири, ушбу топшириқни суҳбат учун даъвогарларга тақдим 
этар экан.) 
Қуйида келтирилган формулалардан қайси бирини а,б,c мусбат сонлар билан томонлар 
узунлигини кўрсатилган учбурчак майдони ҳисоблаш алгоритми сифатида ишлатиш мумкин? 
а) S =
√p(p − a)(p − b)(p − c), бунда p=(a+b+c)/2; 
б) S = ½ bc sinA, ,бунда А- b ва c томонлар орасидаги бурчак; 
c) S = ½ aha, бунда ha- a томонга туширилган баландлик. 
ах2+бх+c= 0 квадрат тенгламанинг ҳақиқий илдизини топиш учун псевдокодда алгоритм 
ёзинг. (а, б ва c - ихтиёрий ҳақиқий коеффисиентлар.) Илдизни топиш учун сқрт (х) функсиясидан 
фойдаланишингиз мумкин.
Ўнлик соноқ системасидаги мусбат сонни иккилик саноқ системасига ўтказиш алгоритмини 
тасвирланг: 
сўзлар билан 
псевдокодда. 
Карточкадан пул олиш жараёнида, банкомат билан ишлаш алгоритмини тасвирланг. 
(алгоритимни сўзлар билан ёки псевдокодда тасвирлашингиз мумкин.) 
а) П сонлар ҳисоблаш масаласи аниқ ишланишини мумкинми?
б) Ушбу масала нечта ечимга эга?
в) Ушбу масала ечимини Интернетда қидириб кўринг. 
, ЭКУБни қидиришдан бошқа масала ечими учун бир қанча алгоритмлар мавжуд бўлган 
масалаларга мисоллар келтиринг. Алгоритмлардан қай бири оддийроқ? Қайсиниси самаралироқ? 
Қуйида келтирилган сонли массивнинг икки элементлари орасидаги минимал фарқни 
қидирув алгоритмини анализ қилинг.
АЛГОРИТМ МинДистанcе ( А( 0… н-1) 
// Кирувчи маълумотлар: А (0..н-1)массив элементлари
// Чиқувчи маълумотлар: икки элемент орасидаги минимал фарқ А 
дмин ←∞
фор и<-0 то н - 1 до 
фор ж<- 0 то н - 1 до 
Иф и=ж анд |А[и]- А [ж]| < дмин 
дмин ← |А[и] - А[ж]| 
ретурн дмин
Бу масала ечими алгоритмини янада такомиллаштира оласизми, агар ҳа бўлса, унга қанча 
ўзгаришлар кирита оласиз? (лозим бўлса, бошқа алгоритм танлаш мумкин. Агар келтирилган 
алгоритмни яхшилай олмасангиз, уни амалга оширишни такомиллаштира оласизми?) 

---

10. Асл келиб чиқиши венгриялик, Америкалик математик Жорж Поя томонидан Ҳоw то Солве 
ит номли машҳур алгоритмик масалалар ечиш китоби ёзилган. Поя ўзи томонидан келтирилган 
фикрларни тўрт пунктдан ташкил топган, резюме тарзида умумлаштиради. Бу резюмени Wеб дан 
топинг (ёки энг яхшиси китобни ўзини ўқиб чиқинг) ва 1.2 бўлимда келтирилган алгоритмик 
масалалар ечими планини солиштиринг. Уларнинг умумийлиги нимада? Фарқичи?