Рисунок.
Схема ва блок схема структураси ўқувчиларга информатика курсидан маълум. Биз кейинчалик ҳам алгоритмларни айнан шундай шаклидан фойдаланамиз Бундай ёндошувда алгоритм ғояси ва негизини мантиқан тассавур қилиш, хамда бу шаклдан алгоритмлаш тилларидан бирортасига ўтиш осонлашади.
Мустақил вазифа сифатида квадрат тенглама дискриминантни мумкин бўлган қийматларини ҳисобга олиб, уни ечишнинг блок схемасини тузинг ва шунга мос равишда келтириладиган жавобни шакиллантиринг.
Хисоблаш машиналарининг яратилиши техник тараққиётнинг зарур қадами бўлиб,катта хажмдаги ҳисоб китобни талаб қиладиган масалалар синфи пайдо бўлиши билан боғлиқдир. Ҳисоблаш машиналарининг пайдо бўлиши ўз навбатида ҳисоблаш машиналарини бошқариш учун маълум кўрсатмаларни тузиш муаммосини келтириб чикарди. Шундай қилиб,ХМ учун алгоритмларни лойихалаш ва бу алгоритмларга мос равишда дастурлар тузиш зарурияти вужудга келди. Замонавий компьютерларни тезкорлигига қарамасдан, кундан кунга катта ҳажмдаги хисоб-китоб талаб қилувчи шундай янгидан-янги масалалар вужудга келаяптики,уларни ечиш учун замонавий компьютерлар хотиралари хам етмаяпти. Курс давомида биз бир неча бор бундай масалаларга эътибор каратамиз.
Мутахасисларга яхши маълум бўлган,шахматга боглиқ яна бир мисолни келтирамиз: от билан суриш қоидаси бўйича амалга ошириладиган А1 катакдан бошланувчи ва барча катаклар бўйлаб бир маротабадан ўтиб А1 катакка қайтиб келувчи маршрутни аниқланг.
Агар бу масалани графлар назарияси терминларидан фойдаланиб ифодаласак, учлари шахмат тахтаси катакларида жойлашган, қирралари эса от суриш қоидаси бўйича харакатланувчи шахмат фигураси босиб ўтган катакларни туташтирувчи чизиқлар бўлган, Гамильтон графи хосил бўлади .
Бу ерда маршрутларни мавжуд вариантлари сони формула ёрдамида ҳисобланади. Кўринишидан оддий бўлган мисолда хам биз жуда кўп вариантларга дуч келаяпмиз. Агар бундай графда хар бир қирра маълум ўтиш нархига эга бўлса ва биз мавжуд маршрутлардан нархи бўйича энг арзон маршрут танлашимиз керак бўлса, бундай масалани хатто замонавий тезкор ЭҲМлар хам еча олмайди. Шу билан бирга маршрутларни ўзаро солиштириш учун ЭҲМ хотирасида хар бир маршрут ҳақида ахборот саклашимиз керак, бундай маълумотни сақлаш учун шундай катта хотира хажми керак бўладики, бу хажмдаги маълумот учун замонавий ЭҲМ хотираси етарли эмас. Шунинг учун алгоритмларни лойихалашда биз уларни хисоблаш ҳажми буйича ҳамда тузилган алгоритмни реализация қилиш учун ҳотира хажми бўйича ҳам баҳолашимиз керак.Кейинчалик хар бир таклиф қилинган алгоритмни айнан шу кўрсаткич бўйича баҳолаймиз.
Келтирилган ёндошувни тасаввур этиш учун бирор нуқтада кўп хад қийматини ҳисоблаш жараёнини кўрайлик. Бунинг учун зарур бўлган амаллар сонини аниқлаймиз.
Биринчи ёндошув – тўғридан тўғри ёндошув бўлиб,унда арифметик амаллар кетма-кет ҳисобланади. Хар бир қўшилувчи учун кўпайтиришлар сони мос равишда: Қўшишлар сони эса Хаммаси бўлиб та амал бажарилади.
Иккинчи ёндошув – Горнер схемаси бўйича ҳисоблаш бўлиб,унда кўпҳад кўринишда бўлади. Бу ерда зарур амаллар сони : та кўпайтирув ва та қўшишдан иборат. Иккичи ёндошув самарадорлиги кўриниб турибти.
Маълум бир масала алгоритмини лойиҳалашга ўтишдан олдин,масала коррект қўйилганига ишонч хосил қилишимиз керак.Яъни,биринчидан масала ечими мавжудлиги,иккинчидан эса, агар бирор кўшимчалар бўлмаса, ечим ягоналиги. Бунинг учун мавжудлик ва ягоналикни таъминловчи барча шартлар бўлиши зарур. Тасаввур қилиш учун қуйидаги мисолни кўрайлик:
133 000 сўм пулга нархлари 5 000, 11 000 ва 18 000 сўм дан бўлган 10 дафтар сотиб олиш керак.Ҳар бир тур дафтарни сонини аниқланг.
Ечим. Нархлари 5 000, 11 000 ва 18 000 сўм бўлган дафтарлар сонини мос равишда x, y и z деб белгиласак,масала шартига кўра тенгламалар системаси ҳосил бўлади:
Маълумки, бундай система чексиз кўп ечимга эга бўлиб Диофант системаси деб аталади. Бизга зарур бўлган ечимни ажратиб олиш учун, ушбу чекловни киритамиз: дафтарлар сони бутун мусбат сон бўлиши кераклигидан,биз фақат бутун мусбат ечимларни оламиз. Шуни хисобга олиб, системадан ечимнинг умумий формуласини топамиз:
ва шундай қилиб шартга кўра лигидан бўлганда бутун мусбат сонлар ва оламиз.
Do'stlaringiz bilan baham: |