Рекурсивный Фибоначчи в C, используя fork()

Наверху, я с готовностью признаю, что это домашнее задание. Но я ударился головой о стену на этом, и я просто не понимаю. Параметры присваивания следующие: «Рекурсивно вычислить указанный номер.Если печать верна, распечатайте ее, в противном случае предоставьте ее моему родительскому процессу.Рекурсивный Фибоначчи в C, используя fork()

ПРИМЕЧАНИЕ. Решение должно быть рекурсивным, и оно должно развить новый ребенок для каждого вызов. Каждый процесс должен вызывать doFib() ровно один раз ».

Это мой первый опыт использования fork(), и хотя я думаю, что понимаю, я просто не могу окутать голову, почему я не получаю правильный ответ. Вот мой код, который довольно зачаточном:

doFib(int n, int doPrint) 
{ 
    int status; 
    int print; 
    pid_t pid1; 
    pid_t pid2; 
    int sum1; 
    int sum2; 

    if (n < 2) 
     exit(n); 

    pid1 = fork(); 

    if (pid1 == 0) 
    { 
     doFib(n-1, doPrint); 
     exit(n-1); 
    } 

    pid2 = fork(); 

    if (pid2 == 0) 
    { 
     doFib(n-2, doPrint); 
     exit(n-2); 
    } 

    while ((pid1 = waitpid(-1,&status, 0)) >0) 
    { 
     if(WIFEXITED(status)) 
      sum1 += WEXITSTATUS(status); 
    } 

    while ((pid2 = waitpid(-1,&status, 0)) >0) 
    { 
     if(WIFEXITED(status)) 
      sum2 += WEXITSTATUS(status); 
    } 

    print = sum1 + sum2; 

    if(doPrint) 
     printf("%d\n", print); 
    else 
     exit(0); 
}

Фибоначчи является одним из первых примеров рекурсии я учил, и я его понимаю на базовом уровне. Тем не менее, когда я запускаю свою программу, с 10 в качестве заданного аргумента (хотя любой аргумент приводит к неправильным результатам), я получаю поток мусора, заканчивающийся на: -1861761537 (есть много этих отрицательных чисел), 17. Любые изменения, которые я делаю в результате в разных значениях нежелательной почты, но все равно в конечном итоге на 17.

Я считаю, что проблема в моем использовании waitpid, но я не знаю, что это будет. Правильно ли я полагаю, что это источник моей ошибки? Я просмотрел учебник, справочные страницы, Интернет и т. Д., И я не знаю, что я могу исправить. Любая помощь будет принята с благодарностью. Спасибо.

источник

2013-09-13 Anonymous

Можете ли вы правильно откомпоновать код. – hetepeperfan

Использование рекурсии препятствует производственному коду. См. Например, ориентиры NASA: http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf – matcheek

Рад, что они вычисляют числа fininccci ** рекурсивно **; потому что преподавание студентов, что ** код O (2^n) '** является приемлемым, определенно поставит их для успеха позже в жизни. –

я возьму удар в этом:

exit(n-1);

почему вы декремент входа в качестве значения выхода? если я правильно чтение намерения кода, значение выхода должен быть промежуточный результат

Добавление

:) Поскольку это домашнее задание, я не дам вам ответ. Также, поскольку я не знаю ответа, не использовал fork() в ... очень долгое время.

Вместо того, думать об ответе в качестве шаблона подстановки:

Первого шаблоном является нормальной рекурсивной функцией Fib, с синхронными вызовами
Второго шаблоном извлечением результата из асинхронных вилков вместо синхронного звонки

Напишите первый образец и протестируйте его, а затем преобразуйте его со вторым рисунком. Существует по крайней мере два правильных решения. Найдите оба.

источник

2013-09-13 21:59:04

Тогда текущее «n» процесса - это значение, на которое я хочу выйти? Тогда рекурсивные вызовы будут обрабатывать случаи «n-1» и «n-2». Быстрая проверка того, что оба оператора выхода читают «exit (n)», генерирует подобный поток мусора, который закончился на 20, что по крайней мере ближе к желаемому 55, хотя я могу неправильно истолковать ваш вопрос. –

@ user1478674: см. Правки –

Вы использовали += назначение вместо = присвоения при присвоении значения sum1 & sum2 от WEXITSTATUS(). Поскольку sum1 & sum2 не были инициализированы, это создало вектор вставки для данных мусора в вашу программу.

Кроме того, как отметил Zack в comments, код не будет работать на машинах Unix для значений n >= 15 из-за максимальное значение состояния выхода из 255.

источник

2013-09-13 22:33:29

Это имеет смысл логически, но в исполнении он дал мне вывод 375. Что-то слишком много работает FAR. –

@MartyEischeid да мой первоначальный тест ведет к тому, что кажется арифметическим переполнением ... Что-то еще не так ... –

Ну, я нашел одну проблему: второй цикл while вообще не вводится. В настоящее время я тестирую некоторые исправления, чтобы выяснить, почему это было бы. –

Что вам нужно сделать, так это отладить вашу программу.Я бы предложил начать, предоставив ему простой путь выполнения и посмотреть, что он делает. Например, начните с n = 1, затем n = 2, затем n = 3. Прокомментируйте второй код вилки и сконцентрируйтесь на том, чтобы первая часть работала. Используйте инструкции печати для проверки значений переменных в разных точках программы, что даст вам подсказку о том, как она работает, или нет.

источник

2013-09-14 15:21:11

Рекурсивный Фибоначчи в C, используя fork()

ответ

Смежные вопросы