Algoritm so`zi va tushunchasi IX asrda yashab ijod etgan buyuk



Yüklə 400,41 Kb.
səhifə7/11
tarix19.05.2023
ölçüsü400,41 Kb.
#116841
1   2   3   4   5   6   7   8   9   10   11
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 c1c2c3, …, cn-1cn 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 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)


Yüklə 400,41 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8   9   10   11




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin