Рекурсия с логическим типом - PullRequest
Новая
       14

Рекурсия с логическим типом

1 голос
/ 21 октября 2011

Я пытаюсь научиться рекурсии самостоятельно. Я выполнил следующее упражнение, которое должно возвращать true или false, но по какой-то причине оно всегда возвращает false.

Может кто-нибудь, пожалуйста, скажите мне, почему мой код всегда возвращает false и что мне нужно сделать, чтобы исправить эту ситуацию? 

/*The subset sum problem is an important and classic problem in     computer
theory. Given a set of integers and a target number, your goal is to 
find a subset of those numbers that sum to that target number. For 
example, given the numbers {3, 7, 1, 8, -3} and the target sum 4, the 
subset {3, 1} sums to 4. On the other hand, if the target sum were 2, 
the result is false since there is no subset that sums to 2.*/
#include <iostream>
#include "genlib.h"
#include "simpio.h"
#include "vector.h"

bool CanMakeSum(Vector<int> & nums, int targetSum);
bool sumPermute(Vector<int> &prefix, Vector<int> &rest, int target);

int main()
{
    int numbers[5] = {3, 7, 1, 8, -3};
    Vector<int> nums;
    for (int i=0; i<5; i++)
    {
        nums.add(numbers[i]);
    }
    cout << "Introduce target: ";
    int target = GetInteger();
    if (CanMakeSum(nums, target))
        cout << "True" << endl;
    else
        cout << "False" << endl;
    return 0;
}

bool CanMakeSum(Vector<int> & nums, int targetSum)
{
    Vector<int> prefix;
    return sumPermute(prefix, nums, targetSum);
}

bool sumPermute(Vector<int> &prefix, Vector<int> &rest, int target)
{
    for (int i=0; i<rest.size(); i++)
    {
        Vector<int> newPrefix;
        newPrefix = prefix;
        newPrefix.add(rest[i]);
        // Check for target value.
        int sum = 0;
        for (int n=0; n<newPrefix.size(); n++)
        {
            sum += newPrefix[n];
        }
        if (sum == target)
            return true;
        Vector<int> newRest;
        for (int j=0; j<i; j++)
        {
            newRest.add(rest[j]);
        }
        for (int k = i+1; k<rest.size(); k++)
        {
            newRest.add(rest[k]);
        }
        sumPermute(newPrefix, newRest, target);
    }
    return false;
}

Заранее спасибо.

Ответы [ 2 ]

1 голос
/ 21 октября 2011

Я не запускал код, но похоже, что может быть проблема с тем, что результат true из sumPermute (на некотором уровне рекурсии) не будет распространяться уровнем "выше" обратно в источник.

Чтобы исправить это, вам нужно проверить возвращаемое значение sumPermute, а если true, убедиться, что оно немедленно распространяется обратно.

Попробуйте изменить это: 

sumPermute(newPrefix, newRest, target);

к этому: 

if(sumPermute(newPrefix, newRest, target)) {
    return true;
}

Обновление : я проверил эту гипотезу на IDEone , и именно в этом и заключается проблема.

0 голосов
/ 21 октября 2011

Вам не нужно использовать оператор if. Просто верните рекурсивный вызов: 

return sumPermute(newPrefix, newRest, tartget);

Проблема в том, что вы не возвращали логическое значение обратно через стек.

...