203-guruh talabasi Berdiyev Ramazonning Algoritmlarni loyihalash fanidan


Download 46.52 Kb.
Sana07.03.2020
Hajmi46.52 Kb.

203-guruh talabasi Berdiyev Ramazonning

Algoritmlarni loyihalash fanidan

2 - labaratoriya mashg’uloti topshirig’i natijalari


  1. Quyidagi nazariy savollarga javob bering

  1. Algoritmlarni baholash kriteriyalari haqida ma’lumot bering

Algoritmni tahlil qilishda quyidagi usullar mavjud:

1.Algoritmlarning eksperimental (empirik) taqqoslash - dasturni ishlatish jarayonida vaqt (xotira) buyicha taqqoslash

2.Algoritmlarning asimptotik taxlili - turli faktorlarga bogliq holda vaqt (xotira) ni nazariy baxolash.

Agar fA(n)  o’sish tartibi n dan bog’liq bo’lgan polinomdan katta bo’lmasa, A algoritm polinomial deb aytiladi, aks holda algoritm A eksponensial hisoblanadi.

Bundan tashqari quyidagi baholashlar mavjud:


  • f(n)=O(1) – o’zgarmas;

  • f(n)=O(log n) – Logarifmik;

  • f(n)=O(n) – Chiziqli;

  • f(n)=O(nc) – Polinominal;

  • f(n)=O(cn) – eksponensial;

  • f(n)=O(n!) – faktorial.


b) Quyidagi masalalar uchun algoritm tuzing va uni tahlil qiling. Dastur kodini yozib natija oling.

  1. Stolda A1 × B1 × C1 o'lchamdagi quti va A2 × B2 × C2 o'lchamdagi quti joylashgan. Ushbu qutilardan birini ikkinchisining ichika kirishi mumkinligini aniqlash dasturini tuzing. Qutilarga ixtiyoriy tomonini 90 daraja aylantirishga ruxsat berilgan.

Kirish ma'lumotlari

Birinchi quti tomonlari A1, B1 va C1. Ikkinchi quti tomonlari A2, B2 va C2 musbat sonlar berilgan



Chiquvchi ma’lumotlar

Agar qutilar bir xil bo'lsa, "Qutilar teng" ni chiqaring. Agar birinchi qutini ikkinchisiga qo'yish mumkin bo'lsa, "Birinchi quti ikkinchisidan kichikroq" ni chiqaring. Agar ikkinchi qutini birinchisiga qo'yish mumkin bo'lsa, "Birinchi quti ikkinchisidan kattaroq" ni chiqaring. Aks holda, "Qutilar taqqoslanmaydi" ni chiqaring.


Misollar

T/r.

Kiruvchi ma’lumotlar

Chiquvchi ma’lumotlar

1

1 2 3
3 2 1

Qutilar teng

2

2 2 3
3 2 1

Birinchi quti ikkinchisidan kattaroqdir

3

2 2 3
3 2 3

Birinchi quti ikkinchisidan kichikroq

4

3 4 5
2 4 6

Qutilar taqqoslanmaydi

Algoritmni amalga oshirish. (dastur)

#include

#include
using namespace std;

int main()

{

int a,b,c, a2,b2,c2;

int a1[3], b1[3];

for(int i=0; i<3; i++)

{

cin>>a1[i];

}

for(int i=0; i<3; i++)

{

cin>>b1[i];

}

sort(a1, a1+3);

sort(b1, b1+3);

int t1=0, t2=0, t3=0;

for(int i=0; i<3; i++)

{

if (a1[i]==b1[i]) t1++;

if (a1[i]>b1[i]) t2++;

if (a1[i] t3++;

}

if(t1==3) cout<<"Boxes are equal";

else

if((t2+t1)==3) cout<<"The first box is larger than the second one";

else

if((t3+t1)==3) cout<<"The first box is smaller than the second one";

else

cout<<"Boxes are incomparable";

return 0;

}
Dasturni tekshirish (Yechim olish)

buni uzing ishlab natija ol


  1. Quyidagi ketma-ketlik bo’yicha yig’indini aniqlang.

S=1+1+2+1+2+3+1+2+3+4+….1+2+3+…n (n<=1000000)

Kiruvchi ma’lumotlar: n soni kiritiladi

Chiquvchi ma’lumotlar: S yig’inchi hisoblanadi



Kiruvchi

Chiquvchi

1

1

1

2

4

20

Algoritmni amalga oshirish. (dastur)

#include

using namespace std;
int main()

{

int n,summ=0,summ2=0;

cout<<"n:= ";cin>>n;
for(int i=0;i<=n;i++)

{

summ+=i;

summ2+=summ;

}

cout<<"S:= "<

return 0;

}

Sikl chiziqli qiyinlikka ega, ya'ni O(n)
Dasturni tekshirish (Yechim olish)




  1. Tovada bir vaqtning o’zida k ta kotletni qovurish mumkin. kotletning bir tomonini pishirish uchun uni uzluksiz m minut qovurish kerak. N ta kotletni qovurish uchun eng qisqa vaqtni aniqlang k>n

Kiruvchi ma’lumotlar: 30000 dan oshmagan k,m,n butun sonlar kiritiladi

Chiquvchi ma’lumot: kotletlarni qovurish uchun minimal vaqt (minutda) chiqariladi.



Kiruvchi

Chiquvchi

1

1 1 1

2

2

2 2 1

4




  1. TATU Samarqand filiali talabalari shahar bo’ylab avtobusda sayohat qilishni rejalashtirdi. Talabalar ko’p bo’lganligi uchun ular 437 sm li 2 qavatli avtobus buyurtma qilishdi. Shahardagi barcha ko’priklardan ularning avtobusi o’ta olish muammosi paydo bo’ldi. Ularda barcha ko’priklarning balandligi ma’lumoti bor. Avtobus nechta ko’prikda o’ta olmasligini aniqlash algoritmini va dasturini tuzing.

Kiruvchi ma’lumotlar: birinchi satrda n ko’priklar soni. Ikkinchi satrda ularning uzunliklari berilgan.

Chiquvchi ma’lumotlar: nechta ko’prikdan o’ta olmasligini aniqlang. Agar bunday ko’priklar bo’lmasa. “NO” yozuvini chiqaring

T/r.

Kiruvchi

Chiquvchi

1

1
763

NO

2

3
763 245 113

2 ta ko’prik

3

1
437

1 ta ko’prik

Algoritmni amalga oshirish. (dastur)

#include

using namespace std;
int main()

{

int n,qadam=0;

cout<<"Ko'priklar sonini kiriting: ";cin>>n;

int size[n];

cout<<"Ularning uzunliklarini kiriting: ";

for(int i=0;i

{

cin>>size[i];//son kiritish

}
for(int j=0;j

{

if(size[j]<=437)//nechta ko’prikdan o’ta olishini hisoblash

qadam++;

}
if(qadam==0)

cout<<"NO"<<endl;

else

cout<" ta ko'prik"<<endl;
return 0;

}

Sikl chiziqli qiyinlikka ega, ya'ni O(n)
Dasturni tekshirish (Yechim olish)





Download 46.52 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling