Міністерство освіти і науки України Національний університет «Львівська політехніка» Лабораторна робота №4 з дисципліни: «Технології розподілених систем та паралельних обчислень» Варіант - 6 Тема роботи: Розподілене програмування на основі технології Cilk. Завдання: Знаходження шляху на графі з допомогою алгоритму Лі. Виконання. Код програми: #include <iostream> #include <string> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <time.h> #include <dos.h> #include <windows.h> #include <cilk.h> #include <cilk_stub.h> #include <reducer_opadd.h> #include <stdio.h> using namespace std; using namespace cilk; #define FALSE 0 #define TRUE 1 #define NROWS 6 #define MCOLS 6 // Symbols: // '.' = open // '#' = blocked // 'S' = start // 'G' = goal // '+' = path // 'x' = bad path char maze[NROWS][MCOLS] = { { 'S', '.', '.', '.', '#', '#' }, { '#', '.', '#', '.', '.', '.' }, { '#', '.', '#', '#', '.', '#' }, { '.', '.', '#', '.', '#', '#' }, { '#', '.', '.', '.', '#', 'G' }, { '#', '.', '#', '.', '.', '.' } }; void display_maze(void); int find_path(int x, int y); int main(void) { clock_t t = clock(); display_maze(); if (find_path(0, 0) == TRUE) printf("Success!\n"); else printf("Failed\n"); display_maze(); int i; cin >> i; clock_t t1 = clock(); cout << "TIME: " << (t1 - t) / 1000 << "ms" << endl; system("pause"); return 0; } // main() void display_maze(void) { int i; printf("MAZE:\n"); cilk_for (i = 0; i < NROWS; i++) printf("%.*s\n", MCOLS, maze[i]); printf("\n"); return; } int find_path(int x, int y) { if (x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1) return FALSE; if (maze[y][x] == 'G') return TRUE; if (maze[y][x] != '.' && maze[y][x] != 'S') return FALSE; maze[y][x] = '+'; if (find_path(x, y - 1) == TRUE) return TRUE; if (find_path(x + 1, y) == TRUE) return TRUE; if (find_path(x, y + 1) == TRUE) return TRUE; if (find_path(x - 1, y) == TRUE) return TRUE; maze[y][x] = 'x'; return FALSE; }// find_path() Програма в роботі: Без використання Cilk: / З використанням Cilk: / cilk працює швидше. Хоча опрацьовувались не велика кількість даних, але отримано результат.