|
var i,k:integer; n:integer;
a:array[byte] of integer; label qq;
procedure opr(nn:integer);
begin i:=2;
while(nn>0) do
begin
if nn mod i=0 then write(i,' ');
i:=i+1;
nn:=nn div i;
end;
end;
begin
readln(n);
k:=1;
for i:=2 to n do
while (n mod i=0) do
begin a[k]:=i; write(a[k],' '); n:=n div i ; k:=k+1; end;
writeln;
readln;
end.
2-misol:
∫
qiymatini hisoblovchi dastur tuzing.
procedure TForm1.Button1Click(Sender: TObject);
var
h,a,x,d,b,s:real;
n:integer;
begin
a:=0; s:=0;
b:=5;
n:=10000;
h:=(b-a)/n;
x:=a;
while (x
begin
d:=sqr(x);
s:=s+d*h;
x:=x+h;
end;
end;
end.
F
OYDALANILGAN ADABIYOTLAR RO’YHATI:
1.
Thomas H. Cormen va b. Intruduction to algorithms. Massachusetts Institute of
Technology. London 2009.(5-10pp)
2.
Слинкин Д.А.Основы программирования на Турбо-Паскале: Учебно-методическое
пособие для студентов вузов. Шадринск: Изд-во Шадринского пединститута, 2003.
- 244 с. (10 -p)
3.
M.U.Ashurov, N.D.Mirzaxmedova .Turbo Pascal dasturlash tili.(uslubiy
qo‘llanma),Toshkent TDPU – 2011 (3-10pp)
2-MAVZU: ALGORITMLAR SAMARADORLIGINI BAHOLASH
Reja
1.
Algoritmlar texnologiya sifatida.
2.
Samaradorligi
3.
Algoritmlar va boshqa texnologiyalar
Algoritmlar texnologiya sifatida.
Kompyuteringizning tezligi va xotira miqdorini abadiy oshirish mumkin, deylik. Bu
holatda algoritmlar o’rganish kerakmi? Bor bo'lishi mumkin, lekin faqat namoyish etish uchun,
echim usulini cheklangan vaqti bor va u to'g'ri javob beradi.
Kompyuterlar juda tez bo’lganda, masalani echishga har qanday konkret usul mos
kelarmidi.
Albatta, bugungi kunda juda samarali kompyuterlar, lekin ularning ishlashi juda katta
bo'lishi mumkin emas. Xotira ham arzon, lekin bepul bo'lishi mumkin emas. Shunday qilib,
hisob-vaqti - cheklangan resurs, shuningdek xotira miqdori ham. Siz donolik bilan bu resurslarini
boshqarishingiz kerak,bunga algoritmlardan, vaqt va xotira xarajatlaridan samarali foydalanish
kerak.
Samaradorligi
Har xil masalalarni yechish uchun mo'ljallangan, turli xil algoritmlar, samaradorligi
bo'yicha sezilarli darajada farq qiladi. Bu farqlar juda katta bo'lishi mumkin ekan. Masalan, ikki
saralash algoritmlar, 2-darsta muhokama qilinadi. Birinchisini bajarish uchun, saralashni
joulashtirish, bunga vaqt kerk bo’ladi, shunday baxolanmoqda c
1
n
2
, n- bu saralash
elementlarning soni, c
1
bo’lsa bu – doimiy, n ga bog’liq emas. Shunday qilib, bu algoritmni
vaqti taxminan n2 proportsional.
Ikkinchi algoritm amalga oshirish uchun, saralash birlashtirishi, vaqt talab etadi, taxminan
c
2
n lg n ga teng, lg n- bu log
2
n qisqa yozuvi, c
2
bu - boshqa doimiy n ga bog’liq emas.Odatda
doimiy usul qo'shimchalar doimiy birlashish usulidan kichikroq, c
1
< c
2
. Doimiy omillar
algoritmni ish vaqtiga juda kan ta’sir qiladi,n ga bog'liq omillardan ko’ra, shunga ishonch xosil
qilaylik.Saralashni joylashtirish algoritmni ish vaqtini shunday yozaylik c
1
n n,birlashtirish
saralashini esa c
2
n lgn.
Joylashtirish saralashi n omilga ega, birlashtirish saralashi esa lg n ga ega bu esa sezarli
darajada kamligini ko’rishimiz mumkin.Kiritish hajmi n etarlicha katta bo'lganda qo'shish
saralashi odatda tezroq bo’ladi, saralash ob'ektlar kichik hajmdagi birlashtirishda, katta n uchun
ahamiyatsiz qiymati lgn nisbatan n to'liq doimiy farqi qadriyatlar o'rnini qoplash, aslida
birlashish yanada sezilarli namoyon bo’ladi, saralash afzalligi ziyoda.Bu doimiy c
1
, c
2
dan necha
marta kam muhim emas.Saralash elementlarini sono ishshi bilan burilish nuqtasi hosil
bo’ladi,shunda birlashish saralashi yanada samarali bo'ladi.
Misol tarzida ikkita A va B kompyuterlarni ko’rib chiqamiz.A kompyuteri ancha tezroq,
va unda joylashtirish saralashi algoritmi ishlaydi, B kompyuter esa sekin va unda saralash
algoritmi birlashtirish usuli bilan ishlaydi.Har ikkita kompyuterlar bir nechta saralashni bajarishi
kerak.Kompyuter A sekundiga o'n milliard ko'rsatmalar bajaradi, B kompyuter sekundiga faqat
o'n million ko'rsatmalar bajaradi,shuhday qilib A kompyuteri ming marta B kompyuterdan tez.
Saralash birlashishi yuqori darajadagi til yordamida bir programct tomonidan amalga oshirilgan.
Bu kompilyator juda samarali emas edi, va natija 50n lg n ko'rsatmalarga bajaradigan kod paydo
bo’ldi.
O'n million raqamlarini tartiblashtirish uchun A kompyuterga kerak bo’ladi:
B kompyuterga kerak bo’ladi
Ko'rib turganingizdek, kod bilan foydalanish, ish vaqti sekin ko’tarilganda,yomon
komilyator bilan ham eng sekin kompyuterda ham17 marta kam vaqt talab qiladi.
Qo’shish usuli joylashtirish usulidan samaraliroq ekanligini quyida keltirilgan jadlal
ma’lumotlarini tahlili orqali keltiramiz.
komput
erlar
Saralanadigan
sonlar soni
Saralovchi
algoritm
Talab qilinadigan vaqt
A(tez
ishlovchi
1sekundda
10mlrd amal
bajaradi)
10 ml
nta (
taqr
iban 80 mb
)
Joylashtirish usuli
(tajribali dasturchi
tomonidan
yaratilgan algoritm
saralash uchun
2n
2
amal
bajariladi)
=20000 sec
(5,5 soatdan ko’proq)
B(sekin
ishlovch-
1sekund
da 10 mln
amal
bajaradi)
Qo’shish
usuli
(o’rta
darajali dasturchi
tomonidan
yaratilgan algoritm
saralash uchun
50nlgn
amal
bajariladi))
Do'stlaringiz bilan baham: |
