Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра електронних обчислювальних машин Звіт про виконання лабораторної роботи № 3 з курсу „ Паралельні та розподілені обчислення ” Тема: Можливості використання паралельних алгоритмів Львів – 2005 Мета: дослідити можливості розв'язання різноманітних задач за допомогою паралельних алгоритмів. Навчитись виділяти паралельні гілки обчислень та виконувати їх паралельно. Завдання Варіант 11. Лабіринт задається матрицею з'єднань в якій для кожної пари кімнат вказано чи з'єднані вони коридором. Задати (ввести з клавіатури, або генерувати випадковим чином): кількість кімнат лабіринту(n), матрицю з'єднань для них, номери кімнат i та j (1<= i,j <=n). Побудувати шлях з кімнати з номером і в кімнату з номером j. Текст програмної реалізації #include <cstdio> #include <string.h> #include <stdlib.h> #include <time.h> #include <iomanip.h> int **A; int n; //***************************************** int**ManualInput(int n) { int **a, i, j; a = new int*[n]; for(i=0; i<n; i++) { a[i]= new int[n]; a[i][i]=1; } cout << endl << "Input matrix of connections (0=no; 1=yes)" << endl; for(i=0;i<n;i++) for(j=0;j<i;j++) { cout << "Is there a corridor between rooms " << (j+1) << " and " << (i+1) << ": "; cin >> a[i][j]; while (a[i][j]!=0 && a[i][j]!=1) { scanf("%d",&a[i][j]); } } for(i=0;i<n;i++) for(j=0;j<i;j++) a[j][i]=a[i][j]; return a; }//***************************************** int** AutoGen(int n) { int **a, **b, **c, i ,j; a = new int*[n]; for(i=0; i<n; i++) a[i]= new int[n]; b = new int*[n]; for(i=0; i<n; i++) b[i]= new int[n]; c = new int*[n]; for(i=0; i<n; i++) c[i]= new int[n]; for(i=0; i<n; i++) { for(j=0; j<n; j++) { if(j < i) a[i][j] = 0; else if(i == j) a[i][j] = 1; else a[i][j] = rand()%2; } } for(i=0; i<n; i++) for(j=0; j<n; j++) b[i][j] = a[j][i]; for(i=0; i<n; i++) { for(j=0; j<n; j++) { if(i == j) c[i][j] = 1; else c[i][j] = b[i][j] + a[i][j]; } } return c; } //***************************************** void Out(int **a, int n) { int i, j; for(i=0; i<n; i++) { for(j=0; j<n; j++) cout << setw(2) << a[i][j] << " "; cout << "\n"; } cout << "\n"; } //***************************************** void FindTheWay(int r1, int r2) { if(A[r1-1][r2-1] == 1) cout << r1 << " " << r2; else { int i, j, k = 0, k1 = 0, *mas1, *mas2, count1 = 0, count2 = 0; mas1 = new int[n]; mas2 = new int[n]; for(i = 0; i < n; i++) mas1[i] = 0; for(i = 0; i < n; i++) mas2[i] = 0; for(i = 0; i < n; i++) { if(A[r1-1][i] == 1) { k = i + 1; mas1[count1] = k; count1++; } } for(i = 0; i < n; i++) { if(A[i][r2-1] == 1) { k1 = i + 1; mas2[count2] = k1; count2++; } } cout << r1 << " "; for(i = 0; i < count1; i++) { for(j = 0; j < count2; j++) { if(mas1[i] == mas2[j] && mas1[i] != 0 && mas2[j] != 0) cout << mas1[i] << " "; } } cout << r2 << " "; } } void main() { srand(time(NULL)); cout << "Please enter number of rooms:" << endl; cin >> n; cout << " * MENU *\n"; cout << "1. Input matrix from keyboard\n"; cout << "2. Generate matrix of connections\n"; char menu; cin >> menu; switch (menu){ case '1': A = ManualInput(n); break; case '2': A = AutoGen(n); break; default: cout << "Wrong choice. Enter 1 or 2.\n"; } Out(A,n); int i, r1, r2; for(i = 0; i < n; i++) { cout << endl << "First room: "; do cin >> r1; while ( (r1<=0) || (r1>n) ); cout << "Second room: "; cin >> r2; if(r1 == r2) cout << " First & second rooms are the same" << endl; else FindTheWay(r1, r2); } cout << " * END *\n"; getchar(); } Приклад виконання програми Please enter number of rooms: 5 * MENU * 1. Input matrix from keyboard 2. Generate matrix of connections 2 1 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 First room: 1 Second room: 3 1 3 First room: 5 Second room: 3 5 4 3 Висновок: на даній лабораторній роботі я дослідив можливості розв'язання різноманітних задач за допомогою паралельних алгоритмів. Здобуті навики я закріпив на прикладі реалізації поставленої мені задачі про лабіринт.