c++ - 使用并行线程查找加到给定数字的所有组合

问题描述

问题是找到一种方法来达到与下面代码中已经达到的结果相同的结果，但要使用自定义数量的线程，使用临界区和信号量，以便并行化下面的代码

我试图并行化代码的递归部分，但我没有想出任何合理的解决方案

代码可以在这里以某种方式并行化，信号量可用于并行化代码，但尚不清楚哪些部分可以并行运行

已经运行的解决方案：

C ++程序找出加到给定数字的所有正数组合

#include <iostream> 
using namespace std; 

//    arr - array to store the combination 
//    index - next location in array 
//    num - given number 
//    reducedNum - reduced number 

void findCombinationsUtil(int arr[], int index, 
                       int num, int reducedNum) 
{ 
    // Base condition 
    if (reducedNum < 0) 
        return; 

    // If combination is found, print it 
    if (reducedNum == 0) 
    { 
        for (int i = 0; i < index; i++) 
            cout << arr[i] << " "; 
        cout << endl; 
        return; 
    } 

    // Find the previous number stored in arr[] 
    // It helps in maintaining increasing order 
    int prev = (index == 0)? 1 : arr[index-1]; 

    // note loop starts from previous number 
    // i.e. at array location index - 1 
    for (int k = prev; k <= num ; k++) 
    { 
        // next element of array is k 
        arr[index] = k; 

        // call recursively with reduced number 
        findCombinationsUtil(arr, index + 1, num, 
                                 reducedNum - k); 
    } 
}

找出加到给定数字的所有正数组合的功能。它使用 findCombinationsUtil()

void findCombinations(int n) 
{ 
    // array to store the combinations 
    // It can contain max n elements 
    int arr[n]; 

    //find all combinations 
    findCombinationsUtil(arr, 0, n, n); 
}

驱动程序代码

int main() 
{ 
    int n = 5; 
    findCombinations(n); 
    return 0; 
}

来源：https ://www.geeksforgeeks.org/find-all-combinations-that-adds-upto-given-number-2/

标签： c++windowsmultithreadingwinapivisual-c++

我将引用另一个答案中的一句话：

我会走建议路线。在尝试使用线程使您的程序更快之前，您首先要使其在单线程情况下更快。

在你的具体问题中，我认为并行化函数有点困难。例如，您可以让每个线程在原始数组的子数组中找到数字的组合，但是不同子数组中的组合呢？显然，并行化这个问题是有限制的，因为每个数字都依赖于其他数字。您可以在进行并行计算之前预先缓存总和，但如果您想要形成组合的数字，它不会有太大帮助。

在 C++ 中使用 OpenMP 并行化递归函数

c++ - 使用并行线程查找加到给定数字的所有组合

问题描述

解决方案

推荐阅读