C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

動的計画法を使用して最適な並列化を実行するC++プログラム


これは、動的計画法を使用して最適な並列化を実行するためのC++プログラムです。

アルゴリズム

Begin
   Take the length n and dimension of matrix as input.
   MatrixChain() to find out minimum multiplications:
   Arguments:
      a[i][j]=Minimum number of scalar multiplications needed to
         compute the matrix A[i]A[i+1]...A[j] = A[i..j] where dimension of A[i] is p[i-1] x p[i].
         a[i][j] means cost is zero when multiplying one matrix.
      L is chain length.
      m = cost / scalar multiplications.
   Body of the function:
      for i = 1 to n-1
         Initialize a[i][i] = 0
      for L = 2 to n-1
         for i = 1 to n - L + 1
            j = i + L - 1
            a[i][j] = INT_MAX
            for k = i to j - 1
               m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j];
               if (m < a[i][j])
               a[i][j] = m
               b[i][j] = k
   return a[1][n - 1]
End

#include<limits.h>
#include<iostream>
using namespace std;
int MatrixChain(int p[], int n) {
   int a[n][n];
   int b[n][n];
   int i, j, k, L, m;
   for (i = 1; i < n; i++)
      a[i][i] = 0;
   for (L = 2; L < n; L++) {
      for (i = 1; i <= n - L + 1; i++) {
         j = i + L - 1;
         a[i][j] = INT_MAX;
         for (k = i; k <= j - 1; k++) {
            m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j];
            if (m < a[i][j]) {
               a[i][j] = m;
               b[i][j] = k;
            }
         }
      }
   }
   return a[1][n - 1];
}
int main() {
   cout << "Enter the length:";
   int n;
   cin >> n;
   int a[n];
   cout << "Enter the dimensions: ";
   for (int v = 0; v < n; ++v) {
      cin >> a[v];
   }
   cout << "Minimum number of multiplications is: " <<
   MatrixChain(a,n);
   return 0;
}

出力

Enter the length:5
Enter the dimensions: 2 3 7 6 4
Minimum number of multiplications is: 174

  1. 最適なページ置換アルゴリズムのためのC++プログラム

    与えられたページ番号とページサイズ。タスクは、最適なページ置換アルゴリズムを使用してメモリブロックをページに割り当てるときのように、ヒットとミスの数を見つけることです。 最適なページ置換アルゴリズムとは何ですか? 最適なページ置換アルゴリズムは、ページ置換アルゴリズムです。ページ置換アルゴリズムは、どのメモリページを置換するかを決定するアルゴリズムです。最適なページ置換では、実際には実装できませんが、近い将来に参照されないページを置換しますが、これは最適であり、ミスが最小限であり、最適です。 例を使って図式的に説明して理解しましょう。 ここで、1、2、3を割り当てた後、メモリが

  2. C ++プログラムを使用してプログラムを起動するにはどうすればよいですか?

    ここでは、メモ帳などのサードパーティアプリケーションやC++プログラムを使用したものを起動する方法を説明します。このプログラムは非常に単純で、コマンドプロンプトコマンドを使用してこのタスクを実行できます。 system()関数内でアプリケーション名を渡します。これにより、それに応じて開きます。 例 #include <iostream> using namespace std; int main() {    cout >> "Opening Nodepad.exe" >> endl;    sy