This server is intended for use for Academic Classwork related Git repositories only. Projects/repositories will generally be removed after 6 months following close of the semester. Inactive repositories from previous semester are now being archived when no activity for 365 days. They are renamed and marked as 'archived'. After 90 days in that state they will be removed from the system completely.

main.cpp 1.64 KB
Newer Older
1 2 3
#include <iostream>
#include <stdlib.h> 
#include<time.h> 
4
#include <chrono>
5 6
#include <omp.h>
using namespace std;
7
using namespace chrono;
8

9
const int MAX = 2147483647;
10
const int ARR_SIZE = 1000;
11 12


13 14 15 16 17 18 19
int main(int argc, char* argv[]) 
{
    srand(time(0));
    int arr[ARR_SIZE];
    for(int i = 0; i < ARR_SIZE; i++) {
        arr[i] = (rand() % 10 + 1) * 10;
    }
20
    int size = ARR_SIZE; 
21
    
22 23
    cout << "Starting execution." << endl;
    auto start = high_resolution_clock::now(); 
24
    int n = ARR_SIZE;
25

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
   // int result = MatrixChainOrder(arr, size);
    int m[n][n];
    // dummy row and column, can be ignored
    for (int i = 1; i < n; i++) 
        m[i][i] = 0; 
  
    // len is used to track length of the mult. chain 
    for (int len = 2; len < n; len++) 
    { 
    #pragma omp parallel for
        for (int i = 1; i < n - len + 1; i++) 
        { 
            int j = i + len - 1; 
            m[i][j] = MAX; 
            for (int k = i; k <= j - 1; k++) 
            { 
                // q = cost / scalar mult.
                int q = m[i][k] + m[k + 1][j] +  
                    arr[i - 1] * arr[k] * arr[j]; 
                if (q < m[i][j]) 
                    m[i][j] = q; 
            } 
        } 
    } 
    int result = m[1][n-1];
51 52
    cout << "Minimum number of multiplications is "
         << result 
53 54 55 56 57 58 59 60
         << endl;
    
    auto finish = high_resolution_clock::now();
    auto duration = duration_cast<seconds>(finish - start);
    //output time to console
    auto minutes = duration.count() / 60;
    auto seconds = duration.count() % 60;
    cout << "Execution time: " << minutes << "m" << seconds << "s." << endl;
61 62 63
 
    return 0; 
} 
64