用布爾類型遞歸

我試圖自己學習遞歸。我已經完成了下面的練習，它應該返回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; 
}

在此先感謝您。

來源

2011-10-21 user971191

這是很多代碼，只是爲了學習遞歸。也許從小開始學習會更容易。 – quasiverse

你可能是對的，但我已經熟悉最基本的遞歸算法（用於教學目的）。我現在正在學習這個免費的在線課程：http://see.stanford.edu/see/courseinfo.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e CS106B編程抽象，我被要求做這個作爲部分自我評估練習。可悲的是，我找不到任何發佈答案的博客。 – user971191

我沒有運行代碼，但它看起來像sumPermute（在某些遞歸級別）的true結果將不會被「高於」級別傳播回源代碼。

要解決這個問題，您需要測試sumPermute的返回值，如果true確保它立即傳播回來。

嘗試修改此：

sumPermute(newPrefix, newRest, target);

這樣：

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

更新：我tested this hypothesis on IDEone，實際上這就是問題所在。

來源

2011-10-21 00:25:22 Jon

這樣做，謝謝！ :) – user971191

您不需要使用if語句。只需返回遞歸調用：

return sumPermute(newPrefix, newRest, tartget);

問題是你沒有返回通過堆棧返回的布爾值。

來源

2011-10-21 00:42:32

用布爾類型遞歸

回答

相關問題