Matematikaningkoʻpbosqichliengmaqbul (optimal) boshqarishgaoidmasalalarnazariyasivaularniyechishusullarinioʻrganuvchiboʻlimi

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

“DASTURIY INJINIRING” KAFEDRASI

“Algoritmlarni loyihalash” fani

4– mustaqil ta’lim ish hisoboti
Guruh: 20-02
Rahbar: Bobonazarov.A
Talaba : Allamurotov.F
2021-2022
Ma’ruzamashg’ulotlariuchunsavollar.
Quyidagisavollargajavobbering.

1. 
   Dinamik dasturlashni tushuntirib bering,
   

Dinamikdasturlash — matematikaningkoʻpbosqichliengmaqbul (optimal) boshqarishgaoidmasalalarnazariyasivaularniyechishusullarinioʻrganuvchiboʻlimi. Bu yerdadasturlash (programmalash) tushunchasi "rejalashtirish", "qarorqabulqilish", yaʼni "birqarorgakelish" maʼnolarida ham qoʻllaniladi. Bu prinsip D. d.ningasosiymasalasinioxiridanboshlabyechishgaimkonberadi. D. d. cheklibosqichlijarayonlardantashqari, uzluksizdavometadiganjarayonlaruchun ham ishlabchiqilgan. U texnika, kosmikparvozlar, xalqxoʻjaliginirejalashtirishningturlimasalalaridaengmaqbulyechimlartopishgaimkonberadi. D. d. usulielektronhisoblashmashinalari, kompyuterlaryordamidatatbiqqilinadi.

2. 
   Kommivoyajer masalasini qo’yilishini ayting.
   

• 
  Masalaning bir nechta variantlari mavjud :
  
• 
  Simmetrik kommivoyajer masalasi  (TSP = traveling salesman problem) D_ji = D_ij.
  
• 
  Assimmetrik kommivoyajer masalasi  (ATSP) D_ji ≠ D_ij.
  
• 
  Qisman tartiblash masalasi  (SOP = sequential ordering problem)
  
• 
  Гамильтон siklini izlash (HCP = нamiltonian cycle problem) -
  

3. 
   “Bo’lib tashla va hukmronlik qil “ prinsipini tushuntirib bering
   

Bo’libtashlavahukmronlikqilusuli
Dasturlashda, bo’libtashlavahukmronlikqil — bu algoritmikparadigma bo’lib, buparadigmaningasosiyg’oyasialgoritmikmasalalarni bosh masalagao’xshashkichikqismlargabo’libtashlab, ularni rekursiv halqilishdaniborat. Bu paradigmada masala qismlargabo’linganligisababli, qismmasalalar bosh masalagaqaragandakichikroqbo’lishivabubo’linishto’xtashiuchun asosholat bo’lishikerak.
Barchaturdagibo’libtashlavahukmronlikqilalgoritmlari 3 ta bosqichdaniboratbo’ladi:
Bo’libtashlashbosqichi. Bunda bosh masala huddishumasalagao’xshashkichikroqmasalalargabo’libchiqiladi.
Hukmronlikbosqichi. Asosholatimizgamoskelibqolganqismmasalalarhuddi u kabiyechiladi.
Birlashtirishbosqichi. Bubosqichdayechilgankichikqismmasalalarqaytibbirlashtiribchiqiladivabuboshmasalayechimibo’ladi.

2) Laboratoriyamashg’ulotlariuchunmasalalar. Quyidagimasalalaruchundasturtuzing.
1. Belgilardaniboratmassivberilgan. Massivni Quick sort algoritmibo’yichasaralang.
#include
using namespace std;

void swap(int* a, int* b)

{
int t=*a;
*a=*b;
*b=t;
}

int partition(int arr[],int low,int high)

{
int pivot=arr[high];
int i=(low-1);

for (int j=low;j<=high-1;j++)

{
if (arr[j]<=pivot)
{
i++;
swap(&arr[i],&arr[j]);
}
}
swap(&arr[i+1],&arr[high]);
return (i+1);
}
void quickSort(int arr[],int low,int high)
{
if (low{
int pi=partition(arr,low,high);
quickSort(arr,low,pi-1);
quickSort(arr,pi+1,high);
}
}

void printArray(int arr[],int size)

{
for (int i=0;icout<}

int main()

{
int arr[]={10,7,8,9,1,5};
int n=sizeof(arr)/sizeof(arr[0]);

quickSort(arr,0,n-1);

cout<<"Quicksortorqalisaralanganmassivlar:\n";
printArray(arr,n);
return0;
}

3. NxMo’lchamlito'rtburchakjadvalidao'yinchi chap yuqorikatakdajoylashgan. Bir vaqtningo'zidao’yinchiqo'shnikatakkao'nggayokipastga (chapgavayuqorigaqarab harakat qilishtaqiqlanadi) o'tishgaruxsatberiladi. O'yinchiningo'ngpastkikatakkakirishiningnechtausullariborliginihisoblang.

Kiruvchima'lumotlar:
N va M ikkitaraqamkiritiladi - jadvalningo'lchamlari (1< = N<=10, 1< = m< = 10).
Chiquvchima'lumotlar:
Kerakliyo'llarsoninichiqaring.
Misol. Kiruvchima’lumot:
2 3
Chiquvchima'lumot:
3
#include
using namespace std;

int numberOfPaths(int m,int n)

{
if (m==1||n==1)
return 1;
return numberOfPaths(m-1,n)+numberOfPaths(m,n-1);
}

int main()

{
int n,m;

cout<<"QandayNxMo'lchamlito'rtburchaknikiriting:\n";

cin>>n>>m;
cout<<"Bo'lishimumkinbo'lganusullarsoni:"<return0;
}