დეიქსტრას ალგორითმი (Dijkstra's Algorithm) C++

ეს ალგორითმი გამოთვლის რომელი მაშრუტებით მივალთ ყველაზე იაფად თბილისიდან სანდიეგომდე მოცემული ნახაზის მიხედვით:

// ConsoleApplication4.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

using namespace std;

#define  N 10

int _tmain(int argc, _TCHAR* argv[])

{

int a[N][N] =

{

{ 0, 500, 400, 450, 700, 0, 0, 0, 0, 0 },  //tbilisi

{ 500, 0, 0, 0, 0, 700, 800, 750, 0, 0 },  //munich

{ 400, 0, 0, 0, 250, 550, 550, 600, 0, 0 },  //Amsterdam

{ 450, 0, 0, 0, 0, 800, 0, 850, 850, 0 },  //istambul

{ 700, 0, 250, 0, 0, 500, 0, 0, 0, 0 },  //Rome

{ 0, 700, 0, 550, 500, 0, 0, 0, 0, 550 },  // New Yourk

{ 0, 800, 550, 0, 0, 0, 0, 0, 0, 350 },  //Huston

{ 0, 750, 600, 0, 0, 0, 0, 0, 350, 450 }, //Chikago

{ 0, 0, 0, 850, 0, 0, 0, 350, 0, 250 },  //Los Angeles

{ 0, 0, 0, 0, 0, 550, 350, 450, 250, 0 }  //San Diego

};

int d[N] = { 0, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000 }; //2000000000 eseni aviget usasrulobis magivrad

int b[N] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; //chartulia tuara qalaqi; roca metia xo irtveba; tavidan yvela chartulia

for (int p = 0; p < N - 1; p++)

{

int i;

int k = -1;

int min = 2000000001;

for (i = 0; i<N; i++)

if (b[i] != 0 && d[i] < min)//chartuli iyos da naklebi minimumze

{

k = i; min = d[i]; // es iqneba minimumi

}

for ( i = 0; i < N; i++)

if (b[i] != 0 && a[k][i]>0) //tu metia 0ze eseigi aris mimosvla, tan chartuliq// a[k][i] es aris dashoreba //minimumshi sadac vart imas davumatet dashorebebi

{

int h = d[k] + a[k][i];

if (h < d[i])

d[i]=h; //tu naklebi gamovid mashin gadavawerot

}

b[k] = 0; // gatishva is romlebtanac shevamowmet yvelaperi// gadavalt imaze romlebdic chartulebia da iq vezebt minimums

}

cout << d[N - 1] << endl;

system("pause");

return 0;

}

merge sort C++

//ConsoleApplication2.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

using namespace std;

#define N 8

void Merge(int a[], int low, int m, int high)

{

static int b[N];

int i, j, k;

i = low;

j = m + 1;

k = i;

while (i <= m && j <= high)

{

if (a[i] < a[j]){

b[k] = a[i];

i++;

}

else

{

b[k] = a[j];

j++;

}                                                                                                                                       

k++;

}

while (i <= m)

{

b[k] = a[i];

i++;

k++;

}

while (j <= high)

{

b[k] = a[j];

j++;

k++;

}

for (k = low; k = high; k++)

{

a[k] = b[k];

}

}

void MySort(int a[], int low, int high)

{

if (low < high)

{

int m = (low + high) / 2;

MySort(a, low, m);

MySort(a, m + 1, high);

Merge(a, low, m, high);

}

}

int _tmain()

{

int a[N] = { 3, 8, 9, 7, 5, 2, 4, 1 };

MySort(a, 0, N - 1);

for (int k = 0; k < N; k++)

cout << a[k]<<endl;

system("pause");

return 0;

}

რეკურსიის მაგალითი. ფაქტორიალი. C++

#include <iostream>

using namespace std;

int factorial (int n)

{

    int r;

    if (n==1)

    r=1;

    else

    r=n*factorial(n-1);

    return r;

}

int _tmain(int argc, _TCHAR* argv[])

{

    int h;

    h=factorial(4);

    cout << h <<emdl;

    return 0;

}

კონებით დალაგება (heap sort) C++

#include "stdafx.h"

#include <iostream>

using namespace std;

#define N 8

int _tmain(int argc, _TCHAR* argv[])

{

int i, j, k;

int a[N + 1] = { 0, 5, 2, 3, 9, 8, 7, 1, 4 };

int b;

for (i = 2; i <= N; i++)

{

j = i >> 1; 

k = 1;

while (j > 0 && a[k] > a[j])

{

b = a[k];

a[k] = a[j];

a[j] = b;

k = j;

j = j >> 1;

}

}

for (int i = 1; i < N; i++)

cout << a[i] << endl;

for (i = N; i>1; i--)

{

b = a[i];

a[i] = a[1];

a[1] = b;

j = 1;

k = j << 1;

while (k < i)

{

if (k=1 < 1 && a[k + 1] > a[k])

k = k + 1;

if (a[k] > a[j])

{

b = a[k];

a[k] = a[j];

a[j] = b;

j = k;

k = k << 1;

}

else 

break;

}

}

for (int i = 1; i < N; i++)

cout << a[i] << endl;

system("pause");

return 0;

}

პოსტის მანქანა

პოსტის მანქანა არის ჰიპოტეტური მანქანა. ის შესდგება უსასრულო ლენტისაგან, რომელიც გაყოფილია სექციებად. ყოველ მომენტში სექცია შეიძლება იყოს ცარიელი __ან შევსებული _¹_. ლენტის შევსებული და ცარიელი სექციების ერთობლიობას უწოდებენ ლენტის მდგომარეობას. მანქანას გააჩნია თავაკი, რომელიც აღინიშნება M ასოთი, ის ყოველთვის იმყოფება ზუსტად რომელიმე სექციის ქვეშ.

მანქანას შეუძლია შეასრულოს შემდეგი მოქმედებები:

1.      თავაკი გადაადგილდეს ერთი სექციით მარჯვნივ ან მარცხნივ;

2.      ჩაწეროს ცარიელ სექციაში ერთიანი, ან წაშალოს შევსებული სექციიდან ერთიანი;

3.      "გაარკვიოს" სექციაში, რომლის ქვეშაც თავაკი დგას, შევსებულია თუ არა (წერია თუ არა 1);

4.      დაამთავროს მუშაობა - გაჩერდეს;

პოსტის მანქანის ბრძანებები:

1.    თავაკის მარცხნივ გადაადგილება: ბრძანების სახელია L(Left)

მაგ,: 02: L-03

ეს ნიშნავს თავაკის ერთი სექციით მარცხნივ გადაადგილებას, შემდეგი შესასრულებელი ბრძანება კი იქნება ბრძანება ნომრით 03.

2.    თავაკის მარჯვნივ გადაადგილება: ბრძანების სახელია R(Right)

მაგ,: 04: L-06

ეს ნიშნავს თავაკის ერთი სექციით მარჯვნივ გადაადგილებას, შემდეგი შესასრულებელი ბრძანება კი იქნება ბრძანება ნომრით 06.

3.    სექციის შევსება, ბრძანების სახელია 1

მაგ.: 05: 1-06

ამ ბრძანების შესრულებისას თუ სექცია ცარიელია, ჩაიწერება 1, შემდეგი შესასრულებელი ბრძანებაა 06. თუ სექცია შევსებულია მოხდება ავარიული გაჩერება. ბრძანების შესრულების შემდეგ თავაკი მდებარეობას არ იცვლის.

4.    სექციის გასუფთავება, ბრძანების სახელია 0

მაგ.: 05: 0-06

ამ ბრძანების შესრულებისას თუ სექცია შევსებულია ჩაიწერება 0, შემდეგი შესასრულებელი ბრძანებაა 06. თუ სექცია ცარიელია, მოხდება ავარიული გაჩერება. ბრძანების შესრულების შემდეგ თავაკი მდებარეობას არ იცვლის.

5.    გაჩერება, ბრძანების სახელია Q(Quit).

09: Q

ამ ბრძანების შესრულების შემდეგ პროგრამა ამთავრებს მუშაობას, თავაკი ინარჩუნებს საბოლოო მდებარეობას, ამ შემთხვევაში ამბობენ რომ ადგილი აქვს შედეგიან გაჩერებას.

6.      განშტოების ბრძანება, ბრძანების სახელია I (if)

მაგ.:  03: I-04-05

ეს ნიშნავს თუ სექცია , რომლის ქვეშაც დგას თავაკი, ცარიელია- მართვა გადაეცემა 04 ბრძანებას(ანუ შემდეგი შესასრულებელი ბრძანებაა 04 ნომრიანი ბრძანება), ხოლო თუ სექცია შევსებულია-მართვა გადაეცემა 05 ბრძანებას

˜ პროგრამაში ბრძანებები ინომრება მიმდევრობით 01 - დან დაწყებული( 01, 02, 03, ...). პროგრამა იწყება 01 ნომრიანი ბრძანებით. არ შეიძლება გადასვლა ისეთ ნომრიან ბრძანებაზე რომელიც პროგრამაში არ გვაქვს.

მაგალითი:

პოსტის მანქანის საწყისი მდებარეობაა:

1

1

1

               M

შევადგინოთ პროგრამა, რომელიც მარჯვნივ პირველ ერთიანამდე ცარიელ სექციებს შეავსებს(ჩაწერს 1-იანებს).

01: R-02

02: 1-03

03: R-04

04: 1-05

05: R-06

06: 1-07

07: Q

ან ზოგადად (როცა ცარიელი სექციების რაოდენობა უცნობია)

01: R-02

02: I-03-04

03: 1-01

     04: Q

1

1

1

1

1

1

                                                  M

 

 პრეზენტაციის ლინკი: https://www.dropbox.com/s/tnt78yet25zcn5x/99772%20%281%29.pptx?dl=0