Oqim guruhlarini yaratish qanday amalga oshiriladi?

Tarmoqlar va chegaralar usuli
Аgar, biz shaharlarni bir marta aylanib chiqishni marshrut deb atasak, aniqki, bunday marshrutlar soni koʼpi bilan (h-1)!ta boʼladi.

Biz tarmoqlar va chegaralar usulini kommivoyajer masalasini yechish uchun qoʼllanishini koʼramiz. Faraz etaylik cij sonlari ishahardan j-shaharga oʼtish uchun ketadigan xarajatni bildirsin. Аgar i shahardan j shaharga oʼtishning iloji boʼlmasa, cij ni yetarlicha katta son deb olamiz (buni cij =∞ deb belgilaymiz), i-shahardan yana i-shaharga oʼtildi, deyish maʼnosiz boʼlganligi sababli cij =∞ deb olinadi. Shundan soʼng nxn oʼlchamli (cij) jadval (matritsa) hosil boʼladi, u xarajat jadvali deb ataladi. Yana bir bor taʼkidlab oʼtamizki, jadvalning i satri j ustuni kesishgan joydagi cijelement i-shahardan j-shaharga oʼtish uchun ketgan sarf-xarajatni bildiradi. Endi jadvalni keltirish tushunchasini kiritamiz. Buning uchun, avval jadval satrlari keltiriladi, yaʼni jadvalning har bir satr elementlaridan shu satrning kichigi mos ravishda ayirib tashlanadi. Barcha satrlari va ustunlari keltirilgan jadval keltirilgan deb ataladi. Demak, keltirilgan jadvalning har bir satri va ustunida kamida bitta nol element ishtirok etgan boʼladi. Jadval satr va ustunlari eng kichik elementlarining yigʼindisi h bilan belgilanib, u jadvalning keltirish koeffitsienti deyiladi. Misol sifatida quyidagi harajat jadvalini ko’ramiz:

Jadval satrlarini keltirish uchun, uning oʼng tarafiga mos satrning eng kichik elementini yozib chiqamiz va satr elementlaridan uni ayirib quyidagi jadvalga ega boʼlamiz.

Hosil boʼlgan C* jadvalning ustunlarini keltirish maqsadida jadval ostiga mos ustunning eng kichik elementi yoziladi va u ustun elementlaridan ayirib chiqiladi, natijada quyidagi jadval hosil boʼladi. C ** jadval keltirilgan boʼlib, uning har bir satr va ustunida kamida bittadan nol element bor. Koʼrilayotgan jadvalning keltirish koeffitsienti h quyidagi songa teng

h=3+1+2+1+4+4+0+3+0+0+0+0=18.

Keltirish koeffitsienti h eng kam xarajatli oʼtishlarning umumiy harajatini bildirib, bu xarajatni beruvchi marshrutni xar vaqt ham aniqlab boʼlmaydi. Yuqorida koʼrilgan misolda eng kam harajatli (h=18) marshrutni aniqlasak, u ikkita bir biriga bogʼlanmagan oʼtishlardan (tsikllardan) iborat boʼlib qoladi, yaʼni 1→5→3→2→1 va 4→6→4. Bu esa qoʼyilgan masalaning yechimini bermaydi. Demak, jadvalni keltirish bilan har vaqt ham qoʼyilgan masalaning yechimini olib boʼlmas ekan. Umuman, tarmoqlar va chegaralar usuli ikkita muhim bosqichdan iboratdir. 1) tarmoqlash; 2) chegaralarni aniqlash. Bu graf oʼzaro birlashtirilgan doirachalardan iborat boʼlib, ularning har biri maʼlum bir xossali marshrutlar toʼplamini aniqlaydi.

Yuqorida koʼrgan misolda h=18 edi, demak, xarajati 18 dan kichik boʼlgan marshrut yoʼq ekan. Barcha marshrutlar toʼplamini tarmoqlash uchun keltirilgan S** jadvalning nol elementlari darajalari aniqlanadi. Masalan, c15 **=0 ning darajasini topish uchun, birinchi satrdagi eng kichik element-1ga, beshinchi ustundagi eng kichik element-1 qoʼshiladi va hosil boʼlgan 2 soni shu nolning darajasi sifatida yozib qoʼyiladi. Xuddi shunday c32 **=0 ning darajasini topish uchun uchinchi satrdagi eng kichik-0 ga ikkinchi ustundagi eng kichik element-4 qoʼshiladi va hosil boʼlgan 4 soni c32 **ning darajasi sifatida yozib qoʼyiladi. Darajasi eng katta boʼlgan nol element s53 **=0 dir, demak, tarmoqlanish grafi koʼrinishda boʼladi. Jadvalning oʼlchami bittaga kamayadi. Bunda, shuni alohida taʼkidlash lozimki, shaharlarning tartib raqamlari albatta saqlanib (yozilib) qolishi shart, aks holda chalkashliklar kelib chiqadi. Shundan soʼng, toʼla boʼlmagan marshrut i→j, j→i (i→j) belgi i-shahardan j-shaharga oʼtishni bildiradi) yoʼqotiladi, buning uchun Cij**element belgisiga almashtirilib yozib qoʼyiladi. Bizning misolda bu jadval quyidagi koʼrinishga ega boʼladi.

Shundan soʼng, hosil boʼlgan yangi jadval keltirilib, uning keltirish koeffitsienti, oldingi keltirish, koeffitsienti boʼlgan h ga qoʼshib yoziladi (h2*). Oxirgi jadvaldan koʼrinib turibdiki, u keltirilgan jadval ekan, demak, uning keltirish koeffitsienti nolga teng. Bunda (k,l) ̅ belgini olgan chap doirachaga mos chegara (h4), h1ga nolning eng katta darajasi qoʼshib aniqlanadi.(k,l) belgili oʼng doirachaga mos kelgan chegarani (h*3) topish uchun oxirgi jadvaldan k-satr va l-ustun chiqarib (oʼchirib tashlanadi) va toʼla boʼlmagan marshrutlar ∞ belgisi yordamida taqiqlanadi. Shundan soʼng, hosil boʼlgan jadvalning keltirish koeffitsienti h ga h*1 qoʼshilib oʼng doiracha yoniga yozib qoʼyiladi.

k,l juftlik sifatida 3→2ni, yoki 6→4ni olish mumkin. Masalan, 3→2ni olaylik. U holda quyidagi grafga ega boʼlamiz. (2,1) belgili doirachada 5→3→2→1 oʼtishlarni oʼz ichiga olgan marshrutlar toʼplami boʼlib, toʼla boʼlmagan 5→3→2→1→5 marshrutni yoʼqotish maqsadida birinchi satr, beshinchi ustun kesishgan elementni ∞ belgiga almashtiramiz va ikkinchi satr birinchi ustunni oʼchirib tashlaymiz, natijada, quyidagi jadval hosil boʼladi:

3. 
   Statik ma`lumotlar tuzilmalari deganda nimani tushinasiz?
   

Statik ma’lumotlar tuzilmasi: to‘plam, massiv, yozuv va jadval.

Statik ma‟lumotlar tuzilmasi vaqt o„tishi bilan o„z o„lchamini o„zgartirmaydi. Biz har doim dastur kodidagi statik ma‟lumotlar tuzilmasiga qarab ularning o„lchamini bilishimiz mumkin.

Toʼplam bu bir turga tegishli boʼlib, takrorlanmaydigan elementlar majmuasidir.

Toʼplam bazaviy turga tegishli boʼlgan barcha qiymatlarni qabul qilishi mumkin. Shuni eslatib oʼtish lozimki, bazaviy 256 tadan ortiq qiymatni qabul qilmasligi lozim. Shu sababli toʼplamning bazaviy turi byte, char va ular orqali hosil qilingan turlar boʼlishi mumkin.

Toʼplam maʼlumotlari uchun ajratilgan baytlar soni:

ByteSize = (max div 8)-(min div 8) + 1,

bu yerda max va min – toʼplam bazaviy turining yuqori va quyi chegarasi.

Аniq bir Ye elementning bayt raqami quyidagicha aniqlanadi:

ByteNumber = (E div 8)-(min div 8).

set T; T.in(x); T.insert(x); T.empty(); …. include

Massiv tushunchasi

Аgar tuzilma elementlari ketma-ket joylashgan boʼlib, ular bir turga tegishli va umumiy nomga ega boʼlsa, u holda bunday maʼlumotlar tuzilmasiga massiv deb ataladi.

Massiv bir oʼlchamli yoki vektor deyiladi, agar u bir qator va N ta ustundan iborat boʼlsa.

Massiv m oʼlchamli deyiladi, agar u m qator va N ta ustundan iborat boʼlsa.

Dasturda massivni eʼlon qilish uchun uning nomini, elementlar sonini va ularning turini koʼrsatish lozim.

a=(a₁,a₂, … , a₁₀₀) - abstrakt bosqich;

fizik bosqich

Massiv xossalari

Massiv elementlari bir turga tegishli, shu sababli, ularning har biri xotirada bir hil xajmni egallaydi;

Massiv tashqi qurilmada emas, balki operativ xotirada joylashadi;

Massiv elementlari ketma-ket kelgan yacheykalarni egallaydi.

S++da massivni 2 hil usulda berish mumkin:

initsializatsiya qilinmagan (masalan, 4 ta elementdan iborat butun turli massiv: int a[4]);

initsializatsiya qilingan (int a[]={2, 3, 4, 5}).

Eslatma: Massivlar bilan ishlayotganda eʼlon qilingan chegaradan chiqib ketmaslik lozim, sababi bu haqida kompilyator ogohlantirmaydi.

Massivga doir misollar

Faraz qilaylik, bizga A={aij} va B={bij} matritsalar berilgan boʼlib, А matritsa eng katta elementini va ushbu matritsalar yigʼindisini topish talab qilingan boʼlsin.

# include

# include

int main()

{clrscr(); int n,m,i,j,p,t;

float a[40][50], b[50][60], c[40][50];

cout<<"A matrisa o'lchamini kirit"<

cin>>n>>m;

cout<<"B matrisa o'lchamini kirit"<

cin>>p>>t;

cout<<"A matrisa elementlarni kirit"<

for(i=0; i

for(j=0; j

cin>>a[i][j];

cout<<"B matrisa elementlarni kirit"<

for(i=0; i


for(j=0; j

cin>>b[i][j];

float x=a[0][0]; int k=0;int l=0;

for(i=0; i

for(j=0; j

if (x

k=i+1;l=j+1;}

cout <<"A matrisa max="<

else

{ for(i=0; ifor(j=0; j

c[i][j]=a[i][j]+b[i][j];

}

return 0;

}