c - 递归级别受限的斐波那契线程

Question

我正在尝试实现线程以如下所示的方式计算斐波那契数列:

                       fib(n)
                          /\
                         /  \
                 fib(n-1)   fib(n-2)
                   /\            /\
                  /  \          /  \
          fib(n-2) fib(n-3) fib(n-3) fib(n-4)

在这个级别之后，我可以使用 fib 函数来计算剩余的项。我已经编写了代码，但我在几个地方感到困惑。我在我感到困惑的地方提供了评论。非常感谢这方面的任何指导:

#include<stdio.h>
#include<time.h>
#include<pthread.h>
#include<stdlib.h>
#include<sys/types.h> /* need to calculate which I will implement later */

void *fibr(void *n);
void *fibr_1(void *k);
signed long long int fibonacci(signed long long int);

  int main(){
    clock_t begin, end;
    double time_spent;
    pthread_t tid,tid1;
    int result,result1;
    signed long long int n=6;
    signed long long int m=7;

     result=pthread_create(&tid,NULL,fibr,&n);
        if(result){
               perror("pthread_create");
                return 1;
            }
     result1=pthread_create(&tid1,NULL,fibr,&m);
        if(result1){
            perror("pthread_create");
             return 1;
            }
        if(pthread_join(tid,NULL)){
            perror("pthread_join");
            return 1;
            }
        if(pthread_join(tid1,NULL)){
            perror("pthread_join");
            return 1;
            }
       printf("Fib value=%lld\n",n+m);
        pthread_exit(NULL);
      }
 void *fibr(void *n){
   signed long long int *y=n;
   signed long long int x=*y;
   pthread_t tid2,tid3;
   signed long long int i,j;
   /* How do I assign values to i , j in order to 
     achieve the level viz fib(n-2)....fib(n-4) */
    if(pthread_create(&tid2,NULL,fibr_1,&i))
     {
        perror("pthread_create");
      }

     if(pthread_create(&tid3,NULL,fibr_1,&j))
      {
  perror("pthread_create");
      }
    if(pthread_join(tid2,NULL))
        {
          perror("pthread_join");
         }

    if(pthread_join(tid3,NULL))
        {
          perror("pthread_join");
         }
     /* How to return the values of i, j combined with *y . if I do *y+i+j, the result                        
      is not coming correctly */
     *y=fibonacci(x);
      return NULL;
       }

    void *fibr_1(void *k){
    long long int *a=k;
    long long int b=*a;
      *a=fibonacci(b);
       return NULL;
      }

      signed long long int fibonacci(signed long long int x){
          if((x==0)||(x==1))
           return x;
           return fibonacci(x-1)+fibonacci(x-2);
         }

疑问:在线评论。 (想不出主线程和子线程之间的传值方式，请指教)

Answer 1

我能想到的最简单的解决方案是使用一个简单的结构，该结构将保存要操作的值和结果并将其作为线程数据传递。代码可能如下所示:

#include<stdio.h>
#include<time.h>
#include<pthread.h>
#include<stdlib.h>
#include<sys/types.h>       /* need to calculate which I will implement later */

typedef signed long long int fibval; /*just to make everything less cluttered*/

void *fibr (void *n);
void *fibr_1 (void *k);
fibval fibonacci (fibval);

typedef struct _param_basket{
    fibval in_param; /* Will hold value to be operated in thread */
    fibval out_param; /* Will hold result of operation in thread */
}param_basket;

int main ()
{
/* Commented to remove warnings
  clock_t begin, end;
  double time_spent;
*/
  pthread_t tid, tid1;
  int result, result1;
  fibval n = 6;

  param_basket b1, b2;
  b1.in_param = n-1; /* This will contain fib(n-1) eventually*/
  b1.out_param = 0;

  b2.in_param = n-2;
  b2.out_param = 0; /* This will contain fib(n-2) eventually*/

  result = pthread_create (&tid, NULL, fibr, &b1);
  if (result)
    {
      perror ("pthread_create");
      return EXIT_FAILURE;
    }
  result1 = pthread_create (&tid1, NULL, fibr, &b2);
  if (result1)
    {
      perror ("pthread_create");
      return EXIT_FAILURE;
    }
  if (pthread_join (tid, NULL))
    {
      perror ("pthread_join");
      return EXIT_FAILURE;
    }
  if (pthread_join (tid1, NULL))
    {
      perror ("pthread_join");
      return EXIT_FAILURE;
    }

 /* fib(n) = fib(n-1) + fib(n-2)*/
  printf ("Fib value (%lld) =%lld\n",n, b1.out_param + b2.out_param);

  pthread_exit (NULL);

  return EXIT_SUCCESS;
}

void *
fibr (void *n) /* will receive n-1 & n-2 */
{
  param_basket * b = (param_basket *)n;

  pthread_t tid2, tid3;

  /* How do I assign values to i , j in order to
 achieve the level viz fib(n-2)....fib(n-4) */
  param_basket b3, b4;
  b3.in_param = b->in_param-1; /* n-2 when n-1 , n-3 when n-2 */
  b3.out_param = 0; /* This will contain fib(n-2) & fib(n-3) eventually in diff threads*/
  b4.in_param = b->in_param-2; /* n-3 when n, n-4 when n-2 */
  b4.out_param = 0; /* This will contain fib(n-3) & fib(n-4) eventually in diff threads*/

  if (pthread_create (&tid2, NULL, fibr_1, &b3))
    {
      perror ("pthread_create");
      return NULL;
    }

  if (pthread_create (&tid3, NULL, fibr_1, &b4))
    {
      perror ("pthread_create");
      return NULL;
    }
  if (pthread_join (tid2, NULL))
    {
      perror ("pthread_join");
      return NULL;
    }

  if (pthread_join (tid3, NULL))
    {
      perror ("pthread_join");
      return NULL;
    }
  /* How to return the values of i, j combined with *y . if I do *y+i+j, the result
     is not coming correctly */
  /* Just combine the outputs! */
  b->out_param = b3.out_param + b4.out_param;

  return NULL;
}

/* Second level thread ... no more wretched spawn! Direct calc*/
void *
fibr_1 (void *k)
{
  param_basket * b = (param_basket *)k;
  b->out_param = fibonacci(b->in_param);

  return NULL;
}

fibval
fibonacci (fibval x)
{
  if ((x == 0) || (x == 1))
    return x;
  return fibonacci (x - 1) + fibonacci (x - 2);
}

希望这对您有所帮助!