Guruh talabasi Xushvaqtov Fazliddinning Ma’lumotlar tuzulmasi va algoritmlar fanidan labaratoriya ishi laboratoriya ishi 1 Mavzu: Dasturlash tillarida ma’lumotlarning standart turlari

610-21-guruh talabasi Xushvaqtov Fazliddinning Ma’lumotlar tuzulmasi va algoritmlar fanidan labaratoriya ishi


LABORATORIYA ISHI - 1
Mavzu: Dasturlash tillarida ma’lumotlarning standart turlari.


Ishdan maqsad: Daturlash tillarida ma’lumotlarning standart turlari. Ma’lumot tiplari va ularni ishlatish.
Qo’yilgan masala: C++ tilida ma’lumotlarning standart turlari va ularga doir misollarning dasturini ishlab chiqish.

Nazariy qism
C++ dasturlash tilida har bir o'zgaruvchi yoki o'zgarmasni tipi ya'ni ma'lumot tipi bilan yoziladi.

Ma'lumotlar turi o'zgaruvchini saqlaydigan ma'lumot hajmi va turini belgilaydi:

Type	Typical Bit Width	Typical Range
char	1byte	-127 dan 127 yoki 0 dan 255
unsigned char	1byte	0 dan 255
signed char	1byte	-127 dan 127
int	4bytes	-2147483648 dan 2147483647
unsigned int	4bytes	0 dan 4294967295
signed int	4bytes	-2147483648 dan 2147483647
short int	2bytes	-32768 dan 32767
unsigned short int	2bytes	0 dan 65,535
signed short int	2bytes	-32768 dan 32767
long int	8bytes	-2,147,483,648 dan 2,147,483,647
signed long int	8bytes	same as long int
unsigned long int	8bytes	0 dan 4,294,967,295
long long int	8bytes	-(2^63) dan (2^63)-1
unsigned long long int	8bytes	0 dan 18,446,744,073,709,551,615
float	4bytes
double	8bytes
long double	12bytes

Boolean ma'lumotlar turi bilan e'lon qilinadi bool kalit so'z va faqat qiymatlarni qabul qilishi mumkin true, yoki false. Qiymat qaytarilganda true = 1 va  false = 0.

Char Ma'lumotlar turi saqlash uchun foydalaniladigan yagona belgi. Belgilar 'A' yoki 'c' kabi bir tirnoq bilan o'ralgan bo'lishi kerak.
String - Turi belgi (matn) bir ketma-ketlikni saqlash uchun ishlatiladi. satrda yozilganidek qo'sh tirnoqda yozilishni unutmang. Misol uchun string ism = "MasterSherkulov"; Satrlardan foydalanish uchun siz qo'shimcha kutubxonadan foydalanishingizga to'g'ri keladi  kutubxonaga kiritishingiz kerak:

1. 
   Berilgan masala: 3 ta istalgan ma’lumot turidan foydalangan holda 3 ta raqam yig'indisini hisoblang.
   

Dastur kodi:
#include

using namespace std;

int main()
{
int a;
short int b;
long int c;
cin >> a >> b >> c;
cout << a+b+c;

return 0;

}


Xulosa: Men ushbu labaratoriy ishida ma’lumot turlaridan to’g’ri foydalanishni va to’g’ri algoritm tuzishni yaxshi o’rgandim. Algoritmni to’g’ri tuzib qiymatlarning to’g’ri joy egalash zarurligini tushundim.

LABORATORIYA ISHI - 2
Mavzu: Qidiruv algoritmlari: chiziqli va binary qidiruv.


Ishdan maqsad:Ushbu laboratoriya ishining maqsadi talabalar qanday qidirish usullari va algoritmlari mavjudligini va ularning samaradorliklarini baholashni o’rganishlari kerak. Shu asosda qidirish usullarini qiyosiy tahlil qilishlari, C++ dasturlash tilida qidirish bilan islashni va ularga oid dasturlar tuzishni o’zlashtirishlari kerak.
Qo’yilgan masala: Talabalar topshiriq variantiga mos qidirish usuli yordamida masalani yechish dasturini yaratish ko’nikmasiga ega bo’lishlari kerak.

Nazariy qisim:

Aytaylik bizga massiv berilgan:
a[]={15, 23, 7, 45, 87, 16};
Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan dastur tuzish sharti qo'yilgan. Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:
#include
usingnamespace std;
int linearSearch(int array[], int size, int searchValue)
{
for(int i =0; i < size; i++)
{
if(searchValue == array[i])
{
return i;
}
}
return-1;
}
int main()
{
int a[]={15, 23, 7, 45, 87, 16};
int userValue;
cout<<"Enter an integer: "<< endl;
cin>> userValue;
int result = linearSearch(a, 6, userValue);
if(result >=0)
{
cout<<"The number "<< a[result]<<" was found at the"
" element with index "<< result << endl;
}
else
{
cout<<"The number "<< userValue <<" was not found. "<< endl;
}
}

Ko'rib turganingizdek, funksiyamiz 2 ta parametr qabul qiladi, birinchisi massivni o'zi, ikkinchisi esa biz qidirayotgan element. Agar uni topa olmasak, "-1" qiymatni qaytaramiz.

Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak. Bu usulda ham funksiyaga 2 ta parametr, birinchisi massiv o'zi keyin esa biz qidirayotgan elementni parametr sifatida beriladi. Qidiruv esa quyidagicha: Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening kodimda bu left va right o'zgaruvchilaridir:
left := 0 right := len(a)
so'ngra quyidagi shart bajarilgan holda
left< right
quyidagi ketma-ket operatsiyalarni amalga oshiramiz

1. 
   left va right index lari markazidagi elementni topamiz (left + right) / 2
   
2. 
   topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
   
3. 
   agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
   
4. 
   agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.
   

Shu zaylda qidiruv left < right shart bajarilmagunicha davom etadi, agar bu jarayonda biz qidirgan element topilmasa u xolda -1 javob qaytariladi, quyida dastur kodi keltirilgan:
#include
Using namespace std;
int binarySearch(int array[], int size, int searchValue)
{
int low =0;
int high = size -1;
int mid;
while(low <= high)
{
mid =(low + high)/2;
if(searchValue == array[mid])
{
return mid;
}
elseif(searchValue > array[mid])
{
low = mid +1;
}
else
{
high = mid -1;
}
}
return-1;
}
int main()
{
int a[]={12, 22, 34, 47, 55, 67, 82, 98};
int userValue;
cout<<"Enter an integer: "<< endl;
cin>> userValue;
int result = binarySearch(a, 8, userValue);
if(result >=0)
{
cout<<"The number "<< a[result]<<" was found at the"
" element with index "<< result << endl;
}
else
{
cout<<"The number "<< userValue <<" was not found. "<< endl;
}
}

Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni rekursiya usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib ko'ring. Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri yoza olishmaydi va bu normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi.

Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:

5. 
   funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q
   
6. 
   chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n)
   

Bundan tashqari massivda qidirishning boshqa usullari ham mavjud bu haqida bu yerda batafsil bilib olishingiz mumkin.
Berilgan topshiriq: 500 dan 1000 gacha bo’lgan sonlar ichida 700 sonini toping.

Dastur kodi:

#include

using namespace std;

int main()

{
for(int i=500; i<=1000;i++){
if(i==700)
cout << "Qidirilgan son: " << i;
}
return 0;
}

Xulosa:
Men ushbu labaratoriya ishida ma’lumotlari qidirish va uning qanday ishlashi haqida bilib oldim. Qidirish tizimlaridan to’g’ri foydalansak ancha ishimiz osonlanishini tushundim.