Algoritm so`zi va tushunchasi IX asrda yashab ijod etgan buyuk
Download 255.05 Kb.
|
algaritmlarni lo yakuniy javoblari
|
c1=c2q2+c3
c2=c3q3+c4 c3=c4q4+c5 ………… cn-2=cn-1qn-1+cn cn-1=cnqn qoldiqli bo`lish natijasida qoldiqlar uchun c2>c3>c4… munosabat o`rinli bo`ladi, bundan tashqari qoldiqlar nomanfiy sonlardir. Shu sababli bu qoldiqlar orasida nolga teng bo`ladigani albatta uchraydi. cn uchun noldan farqli oxirgi qoldiqni olamiz. Bu holda cn-1 soni cn ga bo`linishi ravshan. Hosil qilingan c1, c2, c3, …, cn-1, cn ketma-ketlik a va b sonlari uchun Evklid ketma-ketligi deyiladi. Ketma-ket qoldiqli bo`lish yordamida bunday ketma-ketlikni hosil qilish usuli Evklid algoritmi deb ataladi. 10.ERATOSFEN GʻALVIRI. Berilgan yetarlicha katta sonni tub koʻpaytuvchilarga ajratish eng ogʻir muammolaridan biri hisoblanadi, hozirgacha buni yechishning amaliy tejamkor usuli mavjud emas. Oddiy sinash usulini qoʻllashga toʻgʻri keladi. Bu masalaning xususiy holi – berilgan sonning tubligini aniqlashdir.Shu munosabat bilan natural sonlar qatorining berilgan intervalida barcha tub sonlarni aniqlash masalasi tugʻiladi. Bu masalani hal qilishda quyidagi teorema muhim ahamiyatga ega. Teorema. Ixtiyoriy n natural sonning eng kichik tub boʻluvchisi n dan oshmaydi. Isboti. Agar boʻlsa, u holda , sonlarning biri dan katta,. Ikinchisi esa dan kichik, faqat n aniq kvadrat boʻlgandagina Xususiy holda n ning tub boʻluvchisi ham dan oshmaydi. Endi Eratosfen “gʻalviri” ni koʻrib chiqamiz. Agar n dan katta boʻlmagan barcha tub sonlarni topish kerak boʻlsa, biz ikkidan boshlab, N gacha boʻlgan barcha natural sonlarni yozib chiqamiz, hosil boʻlgan jadvalda ikkidan keyin har bir ikkinchisini, uchdan keyin har bir uchinchisini, beshdan keyin har bir beshinchisini. 7 dan keyin har bir yettinchisini va h.k. bu jarayonni dan oshmaydigan p tub songacha davom ettirib, p ga boʻlinadigan sonlarni oʻchiramiz. Oʻchirilmay qolgan sonlar n dan oshmaydigan tub sonlar boʻladi, chunki biz N dan oshmaydigan barcha karali sonlarni oʻchirib tashladik. Bu usul Eratosfen “gʻalviri” deyiladi. 11. Chiziqli algoritmlar XX asrning 70-yillarida golland olimi Edsger Deykstra (1930 – 2002) har qanday algoritm uning nima maqsadda tuzilganligi va murakkabligidan qat’iy nazar, uchta: ketma-ketlik, tarmoqlanish va takrorlanish algoritmik konstruksiyalaridan foydalanilgan holda yozilishi mumkinligi haqidagi g‘oyani ilgari surdi va tо‘liq asoslab berdi. Chiziqli algoritm deb, barcha ko‘rsatmalari hech qanday shartsiz, faqat ketma-ket bajariladigan jarayonlarga aytiladi. Har qanday algoritm mantiqiy tuzilishi, ya’ni bajarilish tartibiga ko‘ra uchta asosiy turga bo‘linadi: chiziqli, tarmoqlanuvchi va takrorlanuvchi. Edsger Deykstra (1930 – 2002) Download 255.05 Kb. Do'stlaringiz bilan baham: 
|