Muhmmad al-xorazimiy nomidagi toshkent axborot texnalogiyalar unversiteti farg’ona filiali

MUHMMAD AL-XORAZIMIY NOMIDAGI TOSHKENT AXBOROT TEXNALOGIYALAR UNVERSITETI FARG’ONA FILIALI
KOMPUTER INJINERING FAKULTETI KOMPUTER INJINERINGI YONALISHI 612-20 GURUH TALABASI OSTANAQULOV MUXAMMADMIRZONING Algaritmlarni loyihalash fanidan tayyorlagan
MUSTAQIL ISHI

Topshirdi: Ostanaqulov Muxammadmirzo

Qabul qildi: Abdumalik Xayitqulov
Mavzu: Tasodifiy algoritmlar
Reja:

1. 
   Tasodifiy butun sonni hosil qilish funksiyasi
   
2. 
   Tartiblangan elementlarni tasodifiy algoritm yordamida o’zgartirish
   
3. 
   Massiv elementlaridan tasodifiy algoritm yordamida qidirish
   
4. 
   N ta elementli massivdan k ta elementni tasodifiy ajratib olish
   

Tasodifiy algoritmlarni ko’rib chiqishdan oldin tasodifiy butun sonni hosil qilish funksiyasi rand() haqida ozroq eslatib o’tamiz.

rand() funksiyasi orqali tasodifiy butun son hosil qilish mumkin.
Tasodifiy sonlarni hosil qilish uchun rand() funksiyasidan foydalaniladi, buning uchun cstdlib header fayli chaqirilishi lozim. Bu funksiya 0 va RAND_MAX oralig’idagi butun tasodifiy sonlarni qaytaradi. RAND_MAX konstantasining qiymati platformaga bog’liq bo’ladi. Qt Creator muhitida RAND_MAX ning qiymati 32767 ga teng.
rand() psevdorandom sonlarni hosil qiladi. Bu degani bir necha bora rand() funksiyasini ishlatsangiz ham birinchi marta paydo bo’lgan sonlar takror chiqaveradi:
cout<Nima uchun? Chunki rand() funksiyasining algoritmi sonlarni qanday generatsiya qilishni nazorat qiluvchi seed nomli qiymatdan foydalanadi.Dastlabki holatda, seed ning qiymati 1 ga teng. Agar seed ning qiymatini turli sonlarga o’zgartirsak, u holda tasodifiy sonlar ham turlicha bo’lib chiqadi. seed ni o’zgartirish uchun cstdlib kutubxonasi tarkibidagi srand(seed) funksiyasidan foydalaniladi. seed ning qiymati har safar har xil bo’lishini ta’minlash uchun time(0) funksiyasidan foydalanish lozim. “Joriy vaqtni aniqlash” masalasidan time(0) funksiyasining vazifasini bilasiz. U GMT bo’yicha 1970 y., 1-yanvar 00:00 dan boshlab hozirgacha o’tgan vaqtni sekundlarda hisoblaydi
srand(time(0));
cout<Tasodifiy sonlarni 0 va 9 sonlari orasidan hosil qilishni istasak, u holda quyidagicha yoziladi:
rand()%10;

Tartiblangan elementlarni tasodifiy algoritm yordamida o’zgartirish
Fisher-Yates Shuffle (Ronald Fisher va Frenk Yates sharafiga nomlangan) - bu cheklangan to'plamning tasodifiy aralashmasini yaratish algoritmi. Fischer-Yates aralashtirishning asosiy g’oyasi xaltaga solib yashiringan raqamlangan toshchalarni xaltaga toshchalar qolmaguncha bitta-bitta chiqarish kabidir. Algoritm bunday jarayon uchun samarali va qat'iy usulni ta'minlaydi. Algoritmni bajarish vaqti O(n)
Int a[]={2,3,5,7,8,9};
for(int i=n; i>0; i--)
{
j=1+rand()%i;
swap(a[i], a[j]);
}
Massiv elementlaridan tasodifiy algoritm yordamida qidirish
Tasodifiy algoritm yordamida qidiruvni amalga oshirish ikkilik qidirish yoki boshqa algoritmlar kabi har doim ham samarali bo’lmasligi mumkin. Lekin, tasodifiy algoritm yodamida qidiruvni amalga oshirsa bo’ladi va bu yo’l amaliyotda yetarlicha masalalar yechilgan. Tasodifiy algoritm yordamida qidirishning ikkita yo’lini keltirib o’tamiz.

int a[11]={2,4,5,8,23,4,54,65,3,14,20};

do
{
b=rand()%11;
} while (c!=a[b]); //c - izlanayotgan son
cout<Bu usul qidirishning Las-Vegas usuli bo’lib, unda takrorlanishlar soni massiv elementlar soni n dan oshib ketishi mumkin. yoki agar izlanayotgan son massiv elementlari orasida bo’lmasa, takrorlanish cheksiz davom etadi. Buni takomillashtirilgan yana bir usuli bor. Uni quyida ko’ramiz.

int a[11]={2,4,5,8,23,4,54,65,3,14,20};
do
{
i++;
b=rand()%11;
if(i>k) break;
cout<} while (c!=a[b]);
if(i>k) cout<<"\nIzlanayotgan son topilmadi ";
else{
cout<Bu usul Monte-Karlo usuli bo’lib, u yuqoridagi algoritmdan yaxshiroqdir.
N ta elementli massivdan k ta elementni tasodifiy ajratib olish
Bu masala amaliyotda juda ko’p joylarda qo’llaniladi. Masalan, yutuqli o’yinlarda, sport musobaqasida qur’a tashlashda vs boshqa masalalarda. Algoritmning to’liq tavsifini va amaliy masalalarni 14.2-laboratoriya mashg’ulotida keltirib o’tganmiz.
Algoritmning qisqacha tavsifi quyidagicha. Massivdan tasodifiy bitta element raqami tanlanadi. Chunki element turi har xil bo’lishi mumkin. shuning uchun uning tartib raqami tanlab elementga murajaat qilinadi. Shu element yana qayta tanlanmasligi uchun buni massivdan “o’chirib” tashlash kerak. Buning uchun eng oxirgi element shu element o’rniga keltiriladi va massiv elementlar soni bittaga qisqartiriladi.
int a[11]={2,4,5,8,23,13,54,65,3,14,20};
do
{
b=rand()%n;
cout<<"\nTasodifiy tanlangan son "< if(b==(n-1))
{
n--;

}
else
{
a[b]=a[n-1];
n--;

}
} while (n!=k);

Bu masalani yechishning soddaroq algoritmi ham bor. Lekin uni bir necha marta ishlatsangiz ham bir xil natija chiqadi. Bu srand(seed) funksiyasiga seedning qiymatiga joriy vaqt time(0) ni emas, balki takrorlanish tartib raqami qo’yiladi. Natijada bitta massiv uchun har doim bir elementlar tasodifiy tanlanadi.

do
{
srand(i);
b=rand()%(n+1);
cout<<"\nTasodifiy tanlangan son "< i++;
} while (i!=k);