Algoritmlarni murakkablik darajalasining tahlili, murakkablik darajasini baholash usullari
![- 1) + 1 = 2x bo'ladi Bundan ma'lum bo'ladiki, x qiymati parametr sifatida qabul
qilinishi kerak. . Vaqt murakkabligi funktsiyasi quyidagicha bo'ldi:
Bunday holda, vaqtning murakkabligi ma'lumotlar parametriga - faktorial
funktsiya argumentining qiymatiga chiziqli bog'liqligini aytishimiz mumkin.
2-misol . Ikki vektor A = (a1, a2, ..., ak), B = (b1, b2, ..., bk) skalyar ko'paytmasini
hisoblash.
i uchun:=l To k Do AB:=AB+A[i]*B[i];
Bu masalada kiritilgan ma'lumotlarning o'lchami n = 2k. Amalga oshirilgan
operatsiyalar soni 1 + 3k = 1 + 3(n/2). Bu erda V= k= n/2 ni olishimiz mumkin.
Algoritmning murakkabligi A va B vektorlari elementlarining qiymatlariga bog'liq
emas. Oldingi misolda bo'lgani kabi, bu erda vaqt murakkabligining ma'lumotlar
parametriga chiziqli bog'liqligi haqida gapirish mumkin.
Ikki nazariy muammo odatda algoritmning vaqt murakkabligi parametri
bilan bog'liq. Birinchisi, savolga javob topishdan iborat: muammoni hal qilish
algoritmini takomillashtirish orqali vaqt murakkabligi qiymatining qaysi
chegarasiga erishish mumkin? Bu chegara vazifaning o'ziga bog'liq va shuning
uchun o'ziga xos xususiyatdir.
Ikkinchi muammo algoritmlarni vaqt murakkabligi bo'yicha tasniflash bilan
bog'liq. Ta(V) funktsiyasi odatda V bilan o'sadi. U qanchalik tez o'sadi? Ta ning V
ga chiziqli bog'liqligi (biz ko'rib chiqqan misollarda bo'lgani kabi), kvadratik
bog'liqlik va yuqori darajali bog'liqlik algoritmlari mavjud. Bunday algoritmlar
polinom deyiladi. Va shunday algoritmlar mavjudki, ularning murakkabligi har
qanday polinomga qaraganda tezroq o'sadi. Ko'pincha nazariyotchilar - algoritm
tadqiqotchilari tomonidan hal qilinadigan muammo quyidagi savoldir: berilgan
masala uchun ko'p nomli algoritm mumkinmi?
Algoritmlarni tahlil qilishda tez-tez uchraydigan funktsiyalar:
jurnal n (logarifmik vaqt),
n (chiziqli vaqt),
n jurnal n ,
n 2 (kvadrat vaqt),
2 n (eksponensial vaqt).
Birinchi to'rtta funktsiya past o'sish sur'atiga ega va ishlash muddati ushbu
funktsiyalar tomonidan baholanadigan algoritmlarni tez deb hisoblash mumkin.
Eksponensial funktsiyaning o'sish tezligi ba'zan "portlovchi" sifatida tavsiflanadi.
Taqqoslash uchun, murakkabligi (operatsiyalar soni) ushbu funktsiyalar tomonidan
aniq aks ettirilgan algoritmlar mavjud deb faraz qilaylik. Bu algoritmlar sekundiga
10 12 amal tezlikda ishlaydigan kompyuterda bajarilsin. Kirish uzunligi bilan n ≤](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_7.png)
![struct student
{
char name[15];
char surname[20];
int year;
} student_1, student_2, student_3;
Bu holda student strukturali tip bilan birga uchta konkret struktura
kiritiladi. Bu strukturalar student ismi (name[15]), familiyasi (surname[20]),
tugilgan yilidan (year) iborat.
Strukturali tip ta’riflanganda tip nomi ko‘rsatilmay, konkret stьrukturalar
ro‘yxati ko‘rsatilishi mumkin:
struct
{Elementlar_ta’riflari}
Konkret_strukturalar_ro‘yxati.
Quyidagi ta’rif yordamida uchta konkret struktura kiritiladi, lekin
strukturali tip kiritilmaydi.
struct
{
char processor [10];
int frequency;
int memory;
int disk;
} IBM_486, IBM_386, Compaq;](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_18.png)
![Struct goods list[100];
complex set [80];
Bu ta’riflarda list va set strukturalar nomlari emas, elementlari strukturalardan
iborat massivlar nomlaridir. Konkret strukturalar nomlari bo‘lib set[0],set[1] va
xokazolar xizmat qiladi. Konkret strukturalar elementlariga quyidagicha murojaat
qilinadi: set[0].real– set massivi birinchi elementining real nomli komponentasiga
murojaat.
Misol uchun kompleks son modulini hisoblash dasturini keltiramiz:
double modul(complex a)
{return sqrt(a.real*a.real+a.imag*a.imag}
Ikki kompleks son yig‘indisini hisoblash funksiyasi:
complex add(complex a, complex b)
{ complex c;
c.real=a.real+b.real;
c.imag=a.imag+b.imag;
return c;
}
Strukturalar uchun xotiradan joy ajratish. Struktura uchun ajratilgan joy
xajmini quyidagi amallar yordamida aniqlash mumkin:
Sizeof (strukturali_tip_nomi);
Sizeof (struktura_nomi);
Sizeof struktura_nomi.](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_20.png)
![Oxirgi holda struktura nomi ifoda deb karaladi. Ifodaning tipi aniqlanib, xajmi
hisoblanadi.
Misol uchun:
Sizeof (struct goods)
Sizeof (tea)
Sizeof coat
Murakkab tiplar ya’ni massivlar va strukturali tiplar uchun xotiraga talab
ularning ta’rifiga bog‘liqdir. Masalan double array[10] ta’rif xotiradan 10*sizeof
bayt joy ajratilishiga olib keladi.
Struct mixture
{
int ii;
long ll;
char cc[8];
};
Bu ta’rif har bir Struct mixture tipidagi ob’ekt xotirada sizeof(int)
+sizeof(long)+8*sizeof(char) bayt joy egallashini ko‘rsatadi. Ob’’ekt aniq xajmini
quyidagi amal hisoblaydi:
Sizeof(struct mixture)
Xotirani tekislash. Strukturali tip kiritilishi bu tip uchun xotiradan joy
ajratilishiga olib kelmaydi. Har bir konkret struktura (ob’ekt) ta’riflanganda, shu
ob’ekt uchun elementlar tiplariga qarab xotiradan joy ajratiladi. Xotiradan joy zich
ajratilganda struktura uchun ajratilgan joy xajmi har bir element uchun zarur
bo‘lgan xotira xajmlari yigindisiga teng bo‘ladi. SHu bilan birga xotiradan joy zich
ajratilmasligi ham mumkin ya’ni elementlar orasida bo‘sh joylar ham kolishi](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_21.png)
![mumkin. Bu bo‘sh joy keyingi elementni xotira qismlarining qabul qilingan
chegaralari bo‘yicha tekislash uchun koldiriladi.
Strukturalarga yakin tushuncha bu birlashma tushunchasidir. Birlashmalar
union xizmatchi suzi yordamida kiritiladi. Misol uchun
union
{
long h;
int i,j;
char c[4]
}UNI;
Birlashmalarning asosiy xususiyat shundaki uning hamma elementlari bir xil
boshlang‘ich adresga ega bo‘ladi.
Birlashmalarning asosiy avfzalliklaridan biri xotira biror qismi qiymatini har
xil tipdagi qiymat shaklida karash mumkindir.
Misol uchun quyidagicha birlashma
union
{
float f;
unsigned long k;
char h[4];
}fl;](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_22.png)
![Xotiraga fl.f=2.718 xaqiqiy son yuborsak uning ichki ko‘rinishi kodini fl.l
yordamida ko‘rishimiz, yoki aloxida baytlardagi qiymatlarni fl.h[0]; fl.h[1] va
xokazo yordamida kurishimiz mumkin.
Satrlarni ulash amalini bajarishga mo„ljallangan strcat(satr1,satr2) va
strncat(satr1, satr2, n) funksiyalari mavjud bo„lib, ular <string.h>funksiyalar
kutubxonasida aniqlangan. Bunda satr1 – tarkibiga qo„shimcha satr
ulanayotgan satr, satr2 – esa boshqa satrga ulanadigan satr. strcat(satr1, satr2)
funksiyasi satr1 ning orqasidan satr2 ni ulaydi. strncat(satr1, satr2,n) funksiyasi
esa satr1 ning orqasidan satr2 ning dastlabki n ta belgisini ulaydi.
Bu fikrlarni quyidagi dasturni tahlil qilish yo„li bilan tushunish mumkin.
#include <iostream.h>
#include <string.h>
int main ()
{
char satr1 [60]=”men 26-“, satr6[30]=”men vrach”;
char satr2[30]=”maktabda o„qiyman”;
char satr4 [60]=”men 36-“, satr5[60]=”men 16-”;
char satr3 [30]=”kollej talabasiman“
strcat (satr1, satr2);
strcat (satr4, satr3); strncat (satr5, satr3,15);
cout <<satr1<< \n <<satr4<< \n <<satr5 \n ; ‟ ‟ ‟ ‟ ‟ ‟
strncat (satr6,” bo„laman”,4); cout<< \n <<satr6<< \n ;
‟ ‟ ‟ ‟
strncat (satr6,”dimki”,3); cout<<satr6<< \n ;
‟ ‟
system (“pause”);
return 0;
}
Dastur natijasi quyidagicha bo„ladi. Uni tahlil qiling.
men 26-maktabda o„qiyman](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_23.png)
![men 36-kollej talabasiman
men 16-kollej talabasi
men vrach bo„
men vrach bo„ldim
Satrlarni solishtirish (taqqoslash) funksiyalari
C++ da satrlarni solishtirish uchun quyidagi funksiyalardan foydalaniladi.
1. Strcmp(satr1, satr2) funksiyasi. Bu funksiya satr1 satrining har bir belgisi
satr2 satrining mos nomerlaridagi belgilarini ASCII kodlari bo„yicha solishtiradi.
Eslatma: Lotin alifbesining kichik harflari kodi katta harflari kodidan 32 ga ortiq
qilib kodlangan va solishtirish natijasi qandaydir n butun soniga qiymat
sifatida berilishi kerak. Masalan, n=strcmp (s1.s2)
Agar
s1>s2bo„lsa n>0
s1=s2bo„lsa n=0
s1<s2bo„lsa n<0 bo„ladi
n ning qiymati birinchi farq qiluvchi belgilar kodlarini solishtirish bilan aniqlanadi.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{
int j,i,s,n,m; char k1[20]="",k2[20]="";
char satr1[60]="Dasturlash ";char *kor1=satr1;
char satr2[60]="dasturlash ";char *kor2=satr2;
m=strcmp(kor1,kor2); cout<<" m="<<m;
n=strcmp(kor2,kor1); cout<<" n="<<n<<'\n';
system("pause");](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_24.png)
![return 0;
}
satr1 va satr2 larning birinchi belgilari P va p larning kodlari farq qilayapti.
Shuning uchun dastur natijasi m=-1; n=1 kabi bo„lmoqda.
2. Agar satrlarni solishtirishda harflarning registrlarini (ya ni katta yoki‟
kichikligini) farqlash kerak bo„lmasa, u holda strcmpi(satr1, satr2)
funksiyasidan foydalaniladi. Bu hol quyidagi dasturda o„z aksini topgan.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{
int j,i,s,n,m;
char satr1[60]="Dasturlash ";char *kor1=satr1;
char satr2[60]="dasturlash ";char *kor2=satr2;
char satr3[60]="pragraMMalash ";char *kor3=satr3;
m=strcmpi(kor1,kor2); cout<<" m="<<m;
n=strcmpi(kor2,kor3); cout<<" n="<<n<<'\n';
system("pause");
return 0;
}
Dastur natijasi m=0, n=1 kabi bo„lishini tushunish qiyin emas.
3. Agar ikkita satrning faqat dastlabki n ta belgilarini solishtirish talab etilgan
bo’lsa, strncmp(satr1,satr2,n) funksiyasidan foydalaniladi. Quyidagi dasturni
tahlil qilib bunga ishonch hosil qilish mumkin.
#include <iostream.h>
#include <string.h>](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_25.png)
![using namespace std;
int main()
{
int j,i,s,n,m;
char satr1[60]="dasturlash ";char *kor1=satr1;
char satr2[60]="dasturlash ";char *kor2=satr2;
m=strncmp(kor1,kor2,6); cout<<" m="<<m;
n=strncmp(kor1,kor2,7); cout<<" n="<<n<<'\n';
system("pause");
return 0;
}
Dastur natijasi m=0, n=32 kabi bo’ladi. Ikkita satr berilgan. Ularning farq qiluvchi
belgilarini aniqlash dasturini tuzing.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{
int j, i, s, n, m; char k1[20]="", k2[20]="";
char satr1[60]="Progoamalash tillarini o„rganamiz"; char *kor1=satr1;
char satr2[60]="Programalash tillarini o„rganamiz"; char *kor2=satr2;
for(i=1; i<=32; i++) {
strncpy(k1, kor1, 1);strncpy(k2, kor2, 1); kor1+=1; kor2+=1; n=strcmp(k1, k2);
if(n!=0) cout<<i<<"-chi belgisi har xil, ular: "<<k1<< " va " <<k2<<'\n';
}
system("pause");](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_26.png)
![return 0;
}
Dastur natijasi quyida keltirilgan. Mustaqil tahlil qiling.
1-chi belgisi har xil, ular: p va P
5-chi belgisi har xil, ular: o va r
8-chi belgisi har xil, ular: a va f
25-chi belgisi har xil, ular: R va r
26-chi belgisi har xil, ular: c va g
32-chi belgisi har xil, ular: Z va z
Agar satrdagi belgilari ichida harflar bo„lsa, ularni bosh harflardan
kichik harflarga almashtirsh uchun strlwr(satr) funksiyasidan, aksincha kichik
harflarni bosh harflarga almashtirish uchun esa strupr(satr) funksiyasidan
foydalaniladi. Masalan,
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{
char satr2[30]="maktabda o„qiyman";
strupr(satr2);
cout<<satr2<<'\n';
char satr3[30]="MEN TALABAMAN";
strlwr(satr3);
cout<<satr3<<'\n';
system("pause");
return 0;
}](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_27.png)
![Dastur natijasi quyidagicha bo’ladi
MAKTABDA O’QIYMAN
men talabaman kabi bo’ladi
Berilgan satrni teskari tartibda yozish uchun strrev(satr) funksiyasidan
foydalaniladi. Masalan,
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{
char satr3[30]="TALABAMAN";
strrev(satr3);
cout<<satr3<<'\n';
system("pause");
return 0;
}
Dastur natijasi
NAMABALAT
kabi bo’ladi
C++ da berilgan satrdan biror belgini yoki satrning biror qismini izlashga
mo’ljallangan bir nechta funksiyalar mavjud. 1. Satrdan tayin belgini izlash
uchun strchr(satr, „belgi ) funksiyasi aniqlangan bo„lib, agar belgini satr‟
tarkibidan topsa, funksiya satrning o„sha belgisini va undan keyingi belgilarini
qiymat sifatida oladi. Masalan,
#include <iostream>
#include <string.h>
using namespace std;
int main()](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_28.png)
![{
char satr3[30]="134567389";
char satr4[30]="gfdrcx98mjhk";
char *satr,*satr1;
satr=strchr(satr3,'3');cout<<satr<<'\n';
satr1=strchr(satr4,'m');cout<<satr1<<'\n';
system("pause");
return 0;
}
Dastur natijasi quyidagicha bo„ladi
34567389
mjhk
2. Satrlardan birinchi farq qiluvchi belgini, ya ni satr1 dan satr2 da bo’lmagan‟
birinchi belgini topish uchun strspn (satr1, satr2) funksiyasidan foydalaniladi.
Bu funksiya satr1 ning har bir belgisini satr2 dan izlab chiqadi. Qaysi belgisini
topmasa, o’sha belgi indeksiga teng qiymatni oladi. Masalan, quyidagi dasturni
tahlil qilish bilan bunga ishonch hosil qilish mumkin.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ int i,j,k;
char satr1[30]="asalkning yechish";
char satr2[30]="asdfghjhkjl nkdfiggjjk";
j=strspn(satr1,satr2);
cout<<"satr1 ning satr2 dan farq qiluvchi birinchi belgisi nomeri="<<j<<'\n';
system("pause");](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_29.png)
![return 0;
}
Dastur natijasi quyidagicha bo’ladi. satr1 ning satr2 dan farq qiluvchi birinchi
belgisi nomeri=10 kabi bo’ladi
3. Birinchi satrdan ikkinchi sairda bo„lgan birinchi belgini topish uchun strcspn
(satr1,satr2) funksiyasidan foydalaniladi.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ int i ,j, k;
char satr1[30]="asalkning yechish";
char satr2[30]="dfghjhkjl nkdfiggjjk";
j=strcspn(satr1,satr2);
cout<<"satr1 ning satr2 da bo„lgan birinchi belgisi nomeri="<<j<<'\n';
system("pause");
return 0;
}
Dastur natijasi quyidagicha bo’ladi. satr1 ning satr2 da bo„lgan birinchi belgisi
nomeri = 3
4. Strpbrk (satr1, satr2) funksiyasi satr1 tarukibidagi belgilarni satr2 dan
izlaydi. Agar topsa, satr1 ning topilgan belgidan o„ngdagi qismini qiymat
sifatida oladi. Topmasa funksiya NULL qiymatni oladi.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ int i,j,k;](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_30.png)
![char satr1[30]="asan5ng yechish";
char satr2[30]="df3hjhkjmkdfijjk";
char*n;
n=strpbrk(satr1,satr2);
cout<<"satr1 ning satr2 da bo„lgan birinchi belgisidan o„ngdagi
qismi="<<n<<'\n';
system("pause");
return 0;
}
Dastur natijasi quyidagicha bo’ladi. satr1ning satr2 da bo„lgan birinchi belgisidan
o’ngdagi qismi = hish
5. Bir satr tarkibida ikkinchi satrning bor yoki yo„qligi aniqlash uchun
strstr(satr1, satr2) funksiyasidan foydalaniladi. Bu funksiya satr1 ning
tartibidan satr2 ni izlaydi. Agar topsa, satr1ning o„sha topilgan joyidan o„ng
qismiga teng qiymatni oladi. Agar topmasa NULL qiymatni oladi. Misol.
Dastlabki bir nechta natural sonlar ro„yxati berilgan. Ixtiyoriy tanlangan son
nomining ro„yxatda bor yoki yo„qligini aniqlash dasturini tuzing.
#include <iostream.h>
#include <string.h>
using namespace std;
int main()
{ int i,j,k;
char satr1[]="bi, ikki, uch, to„rt, besh, olti";
char satr2[30];
char*n;
cout<<"son nomini kiriting\n";cin>>satr2;
n=strstr(satr1,satr2); cout<<" kipitilgan son ro„yxatda ";
if (n==NULL) cout<<"yo„q\n"; else cout<<"bor\n";](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_31.png)
![system("pause");
return 0;
}
Ko’pincha sonlarni qayta ishlashni talab qiluvchi masalalarda sonni matematik
almashtirishlardan foydalanib qayta ishlagandan ko„ra uni satr ko„rinishda
qayta ishlab, keyin satrni songa aylantirib qo„yish ancha qulay bo„ladi. Buning
uchun S++ dagi <stdlib.h> funksiyalar kutubxonasidagi quyidagi funksiyalardan
foydalaniladi.
1. Atigi (satr) funksiyasi. Bu funksiya turi butun (int) bo„lib, satr
ko„rinishida berilgan sonni butun turga aylantiradi. Satrni to„liq songa aylantirish
uchun satrning belgilari to„liq raqamlar bo„lishi kerak. Agar satrning
boshidagi bir nechta belgilarigina raqamlardan iborat bo„lsa, atoi() funksiyasi
faqat shu qismini songa aylantiradi va qolgan qismini tashlab yuboradi. Agar satr
raqam bilan boshlanmagan bo„lsa, funksiya 0(nol) ga teng qiymatni oladi.
Yuqorida keltirilgan fikrlarni quyidagi dastur misolida tahlil qiling.
#include <iostream.h>
#include <stdlib.h>
using namespace std;
int main()
{ int i,j,k,n,m;
char satr1[30]="215625", satr2[30]="25";
char satr3[30]="2154254254698",
satr4[30]="7458TALA215AN",satr5[]="assalom";
k=atoi(satr1); n=atoi(satr2); i=atoi(satr3); j=atoi(satr4); m=atoi(satr5);
cout<<"i="<<i<<"\nj="<<j<<'\n'; cout<<"k="<<k<<"\nn="<<n5<<'\n';
cout<<"m="<<m<<'\n';
system("pause");
return 0;
}](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_32.png)
![Dastur natijasi quyidagicha bo„ladi
i=-1819327894
j=7458
k=215625
n=25
m=0
Satrni songa aylantirishda son tur chegarasidan chiqib ketsa C++ kutilmagan
natijani chop etadi. Masalan, dastur i parametri uchun shunday qiymat tanlangan
2. atof(satr) funksiyasi. Bu funksiya ham atoi() funksiyasi kabi ishlaydi. Faqat bu
funksiyaning qiymati long turiga mansub bo„ladi. Bundan tashqari funksiyaga
float yoki double turi berilsa, satr ko„rinishidagi sonni double ko„rinishidagi,
ya ni sonning mantissasi va tartibini ko„tsatish bilan yoki o„nli kasr‟
ko„rinishiga o’tkazadi. Agar songa aylantirilayotgan satr chegaradan chiqib
ketsa, funksiya kutilmagan qiymatni oladi.
#include <iostream.h>
#include <stdlib.h>
using namespace std;
int main()
{
int k,n,m; double i,j ;
char satr1[]="3.14D15E+2";
char satr3[30]="21.34254254E15", satr4[30]="745.8215";
n=atoi(satr1); i=atof(satr3); j=atof(satr4);
cout<<"i="<<i<<"\nj="<<j<<<<"\nn="<<n<<'\n';
system("pause");
return 0;
}
Dastur natijasi quyidagicha bo„ladi](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_33.png)
![i=2.13425e+016
j=745.822
n=3
3. itoa (n,satr,m) funksiyasi. Bu funksiya int turiga mansub bo„lgan n sonini m lik
sanoq sistemasiga o„tkazib, satr turiga o„tkazadi va hosil bo„lgan qiymatni satr
massivga beradi. ltoa(n,satr,m) funksiyasi vazifasi ham itoa() funksiyasi
vazifasi kabi. Faqat ltoa() funksiyasi long turiga mansub sonlarni ham
satrga aylantiradi. Quyidagi dasturni tahlil qilib, bunga ishonch hosil qilish
mumkin.
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int main()
{
int n=3245,m; long int i,j=568324557; long double k=5.6e4;
char satr1[20],satr2[20], satr3[20],satr4[20],satr5[20],satr6[20],*satr7;
itoa(n,satr1,2); itoa(n,satr2,8);itoa(n,satr3,16);itoa(n,satr4,10);
cout<<"satr1="<<satr1<<"\nsatr2="<<satr2<<"\nsatr3="<<satr3<<"\nsatr4="<<
satr4<<'\n';
ltoa(j,satr1,2); ltoa(k,satr2,8);ltoa(j,satr3,16);ltoa(j,satr4,10);
cout<<"satr1="<<satr1<<"\nsatr2="<<satr2<<"\nsatr3="<<satr3<<"\
nsatr4="<<satr
4<<'\n';
itoa(n,satr5,10);ltoa(j,satr6,10);satr7=strstr(satr6,satr5);cout<<"
satr7="<<satr7<<'\n';
system("pause");](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_34.png)
![char satr[20];
gcvt(i,n,satr);cout<<"i ning satr korinishi="<<satr<<'\n';
gcvt(m,n,satr);cout<<"m ning satr korinishi="<<satr<<'\n';
gcvt(k,n,satr);cout<<"k ning satr korinishi="<<satr<<'\n';
system("pause");
return 0;
}
Dastur natijasi quyidagicha bo’ladi.
i ning satr korinishi=4562
m ning satr korinishi=1.235e+006
k ning satr korinishi=12.46
7. Tartiblash va saralash masalalarini algoritmlashtirish. Ma lumotlarni‟
tartibga solish turlari. Ma lumotlar tuzilmasini saralash usullari.
‟
Saralash deganda, eng oddiy bo’lgan arraydagi ma’lumotlarni saralashni
nazarda tutamiz va bu kabi saralash algoritmlarining olti xili ni ko’rib chiqamiz:
1. Selection sort (Tanlab saralash)
2. Bubble sort (Pufakchali saralash)
3. Insertion sort (Joylashtirib saralash)
4. Quick sort (Tezkor saralash)
5. Merge sort (Qo’shib saralash)
6. Radix sort
Ularning deyarli hammasi (6- sidan tashqari ) ma ’ lumotlarni taqqoslab ko ’ rish
orqali saralaydi va tayyor saralangan arrayni javob sifatida beradi . Birinchi 3 ta
algoritm O(n²) vaqtda ishlasa, 4–5 lari O(nlogn) vaqtda ishlaydi. Algoritmlar bir xil
ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda
ularning hammasi nimaga kerak degan haqli savol tug’iladi.](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_36.png)
![9. Algoritmlashtirishda graflar nazariyasi, graflarni algoritmlashtirish .
Dastlab graflar haqida qisqacha tarixiy ma'lumotlar, grafning abstrakt
matematik tushuncha sifatidagi ta'rifi va u bilan bog'liq boshlang'ich
tushunchalar, graflarning geometrik ravishda, maxsus turdagi ko'phad yordamida,
qo'shnilik va insidentlik matritsalari vositasida berilishi yoritiladi.
So'ngra grafning elementlari ustida sodda amallar, graflarni birlashtirish, biriktirish
va ko'paytirish amallari, mar- shrutlar va zanjirlar, grafning bog'lamliligi
tushunchasi, Eyler va Gamilton graflari , graflarda masofa tushunchasi, minimal
masofali yo'l haqidagi masala, daraxt va unga ekvivalent
tushunchalar, grafning siklomatik soni bayon qilinadi. Graflar nazariyasi bo'yicha
tadqiqotlar natijalari inson faoliyatining turli sohalarida qo'llaniladi.
Graf — obyektlar to plaminingʻ grafik ko rinishi bo lib, unda ba zi juft ʻ ʻ ʼ
obyektlar linklar orqali bog lanadi. O zaro bog langan obyektlar uchlari deb
ʻ ʻ ʻ
ataladigan nuqtalar bilan ifodalanadi, uchlarini bog laydigan bo g inlar esa qirralar
ʻ ʻ ʻ
deb nomlanadi. Rasmiy ravishda, graf bir juft to plamdir (V, E), bu yerda V —
ʻ
uchlarning to plami, E — uchli juftlarni bog laydigan qirralarning to plami. Biz
ʻ ʻ ʻ
hozir uyidagi grafni ko rib chiqamiz:
ʻ  . Yuqoridagi grafda . V = {a, b, c, d, e} E =
{ab, ac, bd, cd, de}. Graf ma lumotlar tuzilmasi. Matematik
ʼ graflarni ma lumotlar ʼ
tuzilmasida ifodalash mumkin. Biz uch massivi va qirralarning ikki o lchovli
ʻ
qatoridan foydalanishimiz mumkin. Oldinga davom etishdan oldin, ba zi muhim
ʼ
atamalar bilan tanishib chiqaylik. • Vertex — grafning har bir tuguni vertex
shaklida taqdim etiladi.
Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi)
to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir. Grafning elementlari
tarkibi va munosabatlar tuzilishi beriladi. Grafning tarkibiy qismlari bu uning
tugunlari va qirralaridir. К с о и н . Graflar haqida. Tarmoq. Bir nechta juft
tugunlararo qirralardan iborat bo’lgan turlicha yo’llar to’plami mavjud bo’lishi
mumkin. Yopiq yo’llar – sikllarning mavjud bo’lishi tarmoqlarga xos xususiyatdir.
Yonaltirilmagan graf yoki simmetrik bog’liqlik.
10. Kombinatorika elementlarini dasturlash va algoritmlashtirish
Kombinatorikaning to'liq ko'lami umuman kelishilmagan Ga
binoan H.J.Rayser , mavzuni ta'rifi qiyin, chunki u juda ko'p matematik
bo'linmalarni kesib o'tadi. [2]
Hududni kombinatorika bilan bog'liq bo'lgan
muammolar turlari bilan tavsiflash mumkin](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_42.png)
![ The sanab chiqish ba'zan cheklangan tizimlar bilan bog'liq bo'lgan juda umumiy
ma'noda kelishuvlar yoki konfiguratsiyalar deb ataladigan ko'rsatilgan tuzilmalarni
(hisoblash),
The mavjudlik berilgan mezonlarga javob beradigan bunday tuzilmalar,
The qurilish ushbu tuzilmalarning, ehtimol ko'p jihatdan va
optimallashtirish , "eng katta", "eng kichkina" bo'lsin yoki boshqa biron bir narsani
qoniqtiradigan bir qancha imkoniyatlar orasida "eng yaxshi" tuzilmani yoki
echimni topish maqbullik mezonlari .
"Kombinatorial" yo'naltirishlar. Kompyuter fanidagi kombinatorial mantiq
uchun qarang Kombinatorial mantiq .
Kombinatorika maydonidir matematika birinchi navbatda natijalarni olish
uchun vosita va maqsad sifatida hisoblash va ba'zi xususiyatlarini hisoblash bilan
bog'liq cheklangan tuzilmalar . Bu matematikaning boshqa ko'plab sohalari bilan
chambarchas bog'liq va ko'plab dasturlarga ega mantiq ga statistik fizika ,
dan evolyutsion biologiya ga Kompyuter fanlari , va boshqalar.
Leon Mirskiy dedi: "kombinatorika - bu bir-biriga bog'liq bo'lgan bir qator
tadqiqotlardir, ammo ularning maqsadlari, usullari va erishilgan muvofiqlik
darajasi jihatidan bir-biridan farq qiladi." [3]
Kombinatorikani aniqlashning bir usuli,
ehtimol, uning bo'linmalarini ularning muammolari va texnikasi bilan tavsiflashdir.
Bu quyida keltirilgan yondashuv. Shu bilan birga, ba'zi bir mavzularni
kombinatoriya soyaboniga qo'shish yoki qo'shmaslik uchun faqat tarixiy sabablar
mavjud. [4]
Avvalo cheklangan tizimlar bilan bog'liq bo'lsa-da, ba'zi kombinatorial
savollar va texnikalar cheksizgacha kengaytirilishi mumkin
(xususan, hisoblanadigan ) lekin diskret sozlash.
Kombinatorika u hal qiladigan muammolarning kengligi bilan mashhur.
Kombinatoriya muammolari ko'plab sohalarda paydo bo'ladi sof matematika ,
xususan algebra , ehtimollik nazariyasi , topologiya va geometriya , [5]
shuningdek,
uning ko'plab dastur sohalarida. Ko'plab kombinatorial savollar tarixiy ravishda
bir-biridan ajratilgan holda ko'rib chiqilgan maxsus ba'zi bir matematik kontekstda
yuzaga keladigan muammoni hal qilish. Keyingi yigirmanchi asrda esa kuchli va
umumiy nazariy usullar ishlab chiqilib, kombinatorika o'z-o'zidan matematikaning
mustaqil tarmog'iga aylandi. [6]
Kombinatorikaning eng qadimgi va eng qulay
qismlaridan biri grafik nazariyasi o'z-o'zidan boshqa sohalar bilan ko'plab tabiiy
aloqalarga ega. Kombinatorika tez-tez kompyuterda formulalar va taxminlarni
olish uchun ishlatiladi algoritmlarni tahlil qilish .
XULOSA
Algoritm ijrochiga tushunarli bo’lishi uchun ijrochining imkoniyatlarini
bilish lozim. Agar ijrochi inson bo’lsa, u holda algoritm insonning
imkoniyatlaridan kelib chiqib tuzilishi kerak. Bunda ko‘zlangan maqsad va
algoritmdan kelib chiqib inson tushunadigan til, insonning bilimi, hayotiy tajribasi,](/data/documents/10612a64-480c-4acb-9e0c-f31bbe9d0802/page_43.png)
REJA: KIRISH 1. Ma’lumotlar tuzilmasi, tuzilmalar ustida bajariladigan amallar. Dasturlash texnalogiyalari 2. Algoritmlarni murakkablik darajalasining tahlili, murakkablik darajasini baholash usullari. 3. Ma lumotlar tuzilmasida satrli va belgili turlarni dasturlashtirish‟ 4. Dinamik xotiradan foydalanish, dinamik xotirani ishlatishda ko rsatkich turlari ‟ 5. Murakkab turlarni algoritmlashtirish va dasturlash. Vektorlar va massiv ma lumotlarini algoritmlashtirish ‟ 6. Struktura turi, struktura dasturlash va algoritmlash 7. Tartiblash va saralash masalalarini algoritmlashtirish. Ma lumotlarni ‟ tartibga solish turlari. Ma lumotlar tuzilmasini saralash usullari. ‟ 8. Qidiruv algoritmlari. Axborot izlashning asosiy tamoyillari. Kеtma-kеt izlash. Izlashning tеzlashtiririlgan usullari. 9. Algoritmlashtirishda graflar nazariyasi, graflarni algoritmlashtirish. 10. Kombinatorika elementlarini dasturlash va algoritmlashtirish XULOSA FOYDANILGAN ADABIYOTLAR
KIRISH Algoritm ijrochiga tushunarli bolishi uchun ijrochining imkoniyatlarini bilish lozim. Agar ijrochi inson bo’lsa, u holda algoritm insonning imkoniyatlaridan kelib chiqib tuzilishi kerak. Bunda ko‘zlangan maqsad va algoritmdan kelib chiqib inson tushunadigan til, insonning bilimi, hayotiy tajribasi, kasbiy malakasi, yoshi, qolaversa, jismoniy imkoniyatlari hisobga olinishi zarur. Agar ijrochi texnik vosita (masalan, kompyuter, elektron soat, dastgohlar) boMsa, u holda algoritm shu texnik vositaning imkoniyatlaridan kelib chiqib tuzilishi kerak. Inson hayoti davomida katta-kichik vazifalar yoki masalaiarni hal etishni o‘z oldiga maqsad qilib qo‘yadi. Odatda, u o‘z maqsadiga erishishi uchun bajarishi lozim bo'lgan amal yoki ishlarini hayotiy tajribasi yoki o'zlashtirgan bilimiga asoslanib ma'lum bir tartibga keltiradi. Bunga hayotimizdan xilmaxil misollar keltirish mumkin. 1 - misol Ko‘chadan o'tish maqsad qilib qo‘yilgan bo'lsin. IJ holda ko‘chadan o'tayotgan kishi hammamizga odatiy hol bo‘lib qolgan quyidagi harakatlarni bajarishi lozim bo'ladi: 1) chap tarafga qaralsin, agar transport vositasi yo‘q bo‘lsa, 2- bandga o'tilsin, aks holda 1-bandga o'tilsin; 2) o‘ng tarafga qaralsin, agar transport vositasi yo‘q bo‘lsa, 3- bandga o'tilsin, aks holda 1-bandga o'tilsin; 3) ko'chadan o'tilsin. Yuqoridagi misollarda keltirilgan amallar ketma-ketligi, boshqacha aytganda, ko'rsatmalar yoki buyruqlar ketma-ketligi biror kishi tomonidan bajarilgach, ko'zlangan maqsadga erishiladi. Bunday amallar ketma-ketligi yoki hayotimizda har kuni va har soatda uchrab turadigan turli qoidalar ichida biror zaruriy natijaga erishishga olib keladigan amallarni ketma-ket bajarishni talab etadigan qoidalar informatikaning asosiy tushunchalaridan biri algoritm so‘zi bilan ifodalanadi. Algoritm so‘zi IX asrda yashab (783-yilda tug‘ilgan) o‘z ilmiy ishlari xazinasi bilan dunyoga tanilgan vatandoshimiz buyuk astronom, matematik va geograf Abu Abdullo Muhammad ibn Muso al-Xorazmiy nomidan kelib chiqqan. Al-Xorazmiy arifmetikaga bag‘ishlangan «Hind hisobi haqida kitob» risolasida
to‘qqizta hind raqamining sonlarni ifodalashdagi afzalliklari va ular yordamida har qanday sonni ham qisqa va oson yozish mumkinligini aytadi va hozirgi kunda hamma o‘quvchilar biladigan sonlar ustida, yuqoridagi 3-misoldagi kabi ustun ko'rinishida amallar bajarish qoidalarini yoritadi. Ayniqsa, nol (0) qo‘llashning ahamiyati haqida tushuncha berib, nolni yozmaslik natijaning xato chiqishiga olib keladi, degan. Bu risola XII asrda Ispaniyada lotin tiliga tarjima qilingan va butun Yevropaga tarqatilgan. Bu tarjimaning XIV asrda ko'chirilgan qoLyozmasi ning yagona nusxasi Kembrij universitetining kutubxonasida saqlanmoqda. Risola «Dixit Alxhorithmi», ya’ni oDediki aiXorazmiy» iborasi bilan boshlanadi. Algoritm deganda, biror maqsadga erishishga qaratilgan ijrochi bajarishi uchun mo'ljallangan ko‘rsatma (buyruq)laming aniq, tushunarli va chekli ketma- ketligi tushuniladi. Bu algoritm tushunchasining matematik ta'rifi boMmasa ham intuitiv ma'noda algoritmning mazmunini ochib beruvchi tavsifidir. Algoritmni intuitiv ma’noda bir necha misollarda izohlaymiz. Biror-bir narsani taqiqlovchi qoidalar algoritm boMolmaydi, masalan: «Chekish mumkin emas», «Begonalarning kirishi taqiqlanadi», «Kirish», «Chekish uchun joy» kabi birorbir narsaga ruxsat etuvchi qoidalar ham algoritmga xos emas. Lekin «Svetoforni yashil rangida o‘ting» juda sodda bo'lsa ham algoritmdir. Demak, yuqorida keltirilgan misollardagi ko‘rsatmalar ketma-ketligi algoritm va bu algoritmlarni bajarayotgan inson — ijrochi boMar ekan. Algoritm ijrochisi faqat insonmi, degan savol berishingiz tabiiy. Bu savolga javob quyidagicha: Algoritm ijrochisi — algoritmda ko'rsatilgan buyruq yoki ko‘rsatmalarni bajara oladigan abstrakt yoki real (texnik yoki biologik) sistema. Ijrochi bajara olishi uchun algoritm unga tushunarli boMishi lozim. Algoritm ijrochi tushunadigan tilgagina emas, balki uning bilim va malakasiga ham mos boMishi kerak. Aks holda ijrochi birorta ham ko'rsatmani bajara olmasligi mumkin. Ijrochi bajara olishi mumkin boMgan ko‘rsatma yoki buyruqlar to‘plami ijrochining ko‘rsatmalar sistemasi deyiladi. Masalan, «16 sonidan kvadrat ildiz chiqarilsin» ko'rsatmasi 2-sinf o'quvchisining ko'rsatmalar sistemasiga tegishli boMmaydi, lekin 8-sinf o'quvchisining ko‘rsatmalar sistemasiga tegishli boMadi. 1. Ma’lumotlar tuzilmasi, tuzilmalar ustida bajariladigan amallar. Dasturlash texnalogiyalari Ma’lumotlar tuzilmasi — bu ma’lumotlarni samarali o’qish va o’zgartirish imkonini beruvchi, ma’lumotlarni saqlash va boshqarishning bir formatga solingan shaklidir.
Barcha dastur yoki dasturiy mahsulotning asosida ikkita birlik yotadi: ma’lumotlar va ular ustida qandaydir amallar bajaradigan algoritmlar. Algoritmlar ma’lumotlarni biz yoki dastur uchun foydali bo’lgan axborot ko’rinishiga keltirib beradi. Algoritmlar shu ma’lumotlar ustida amallarni (o’qish, yozish, yangilash, o’chirish) samarali va tez bajara olishi uchun biz shu ma’lumotlarni ma’lum bir strukturaga solgan holda saqlashimiz kerak bo’ladi. Demak shunday qilib, Quyida keltirilgan ma’lumotlar tuzilmalari dasturlashda eng ko’p qo’llaniladigan tuzilmalardir. Ularga: 1. Massiv (Array) 2. Bog’langan ro’yhat (Linked List) 3. Navbat (Queue) 4. Stek (Stack) 5. Hash jadvallar (Hash tables) 6. Daraxtlar (Trees) 7. Graflar (Graph) kiradi. Biz bu bo’limda boshidagi 5 ta tuzilma bilan yaqindan tanishib, ularning kuchli va kuchsiz tomonlari va ularni qanday holatlarda ishlatish ma’qulligi haqida gaplashib o’tamiz. Qolgan ikkita tuzilma murakkabroq bo’lib ular o’z ichida yana ko’plab turlarga bo’linib ketadi. Shuning uchun ularni keyinroqqa qoldiramiz. Bundan tashqari barcha tuzilmalarning hamma joyda ingliz tilidagi nomi
ishlatilgani va ularning nomi odatda tarjima qilinmaganligi sababli keyingi o’rinlarda men ularning asosan ingliz tilidagi nomlarini ishlataman. Turli xildagi ma’lumotlar tuzilmalari nima uchun kerak? Ma’lumotlar tuzilmalari nimaligi haqida qisman tasavvurga ega bo’ldingiz va ularning asosiy turlari bilan ham tanishib oldingiz. Lekin, shu joyga kelib agar sizda “Nima uchun ma’lumotlarning turli xil tuzilmalari kerak?” “Nima uchun bir turdagi universal ma’lumotlar tuzilmalaridan foydalanib qo’ya qolsa bo’lmaydi?” degan savol tug’ilmagan bo’lsa, bu yaxshi emas.) Keling endi shu savolga javob topishga harakat qilamiz. Undan oldin ma’lumotlar tuzilmalari ustida asosiy bajarilishi mumkin bo’lgan amallarni ko’rib chiqaylik. Bularga ma’lumotlarni : Ko’rib chiqish (Traversing) O’qib olish (Retrieving) Kiritish (Insertion) O’chirish (Deletion) Qidirish (Search) Saralash (Sorting) Birlashtirish (Merging) lar kiradi. Turli xildagi ma’lumotlar tuzilmalarida esa yuqoridagi amallar turlicha tezlikda amalga oshadi. Masalan oddiyroq misol olaylik, array uchun ma’lumotni o’qib olish uchun O(1) vaqt sarflansa, uni kiritish yoki o’chirish uchun O(n) vaqt sarflanadi. Linked listda esa bular aksincha. Shuning uchun, masalan, sizning dasturingizda ma’lumotlar ko’p kiritilib, o’chirilsayu lekin kam o’qilsa, bunda ma’lumotlarni saqlashda arraydan foydalangandan ko’ra linked list qulayroq hisoblanadi. Lekin, ko’pincha holatda bir necha ma’lumotlar tuzilmalarini o’zini birlashtirgan gibrid ma’lumotlar tuzilmalaridan ham foydalaniladi. 2. Algoritmlarni murakkablik darajalasining tahlili, murakkablik darajasini baholash usullari . Dasturni bajarish vaqti bajarilgan amallar soniga proportsionaldir. Albatta, vaqtning o'lchov birliklarida (sekundlar), u ham protsessorning tezligiga (soat chastotasiga) bog'liq. Algoritmning vaqt murakkabligi ko'rsatkichi nisbatan o'zgarmas bo'lishi uchun spetsifikatsiyalar kompyuter, u nisbiy birliklarda o'lchanadi. Odatda vaqt murakkabligi bajarilgan operatsiyalar soniga qarab baholanadi. An'anaga ko'ra, algoritmning murakkablik darajasini u foydalanadigan asosiy kompyuter resurslari miqdori bo'yicha baholash odatiy holdir: protsessor vaqti