C++：如何解決這個遞歸拼圖（subset-sum style）

請給我一些關於爲什麼我的代碼不適合這個任務的指針。我的想法是有一個index（param），它是Vector中的當前位置，以及target（param），它是數組中給定索引的值。然後，我可以上下移動，直到到達其中一個基本情況。但它不工作。C++：如何解決這個遞歸拼圖（subset-sum style）

主要的問題是，它迄今只輸出錯誤的結果。

enter image description here

bool RecursivePuzzle :: SolvableReal(Vector<int> & squares, int index, int target) 
{ 
if (target == 0 && index == squares.size()) return true; 
if (index >= squares.size()) return false; 
if (index < 0) return false; 

int goUp = squares[index] + index; 
int goDown = squares[index] - index; 

return SolvableReal(squares, goUp, squares[index]) || 
     SolvableReal(squares, goDown, squares[index]);

來源

2012-12-15 Tom Lilletveit

你說的「它不工作」是什麼意思？它是否陷入無限循環？ –

一個錯誤是您沒有考慮潛在的無限循環。它仍然可以通過一些配置完成，所以當你說「它不起作用」時，你的意思是什麼？它會永遠運行嗎？它是段故障嗎？ –

除非我擁有[3,0,0,3]的配置（因爲它會在這兩個數字之間轉換），否則它不會陷入無限循環。但我知道這一點，這不是主要問題。這是它輸出錯誤的結果，只是錯誤的。 –

可能不是全部答案，但是這部分看起來錯誤：

int goUp = squares[index] + index; 
int goDown = squares[index] - index;

我覺得應該是

int goUp = index + squares[index]; 
int goDown = index - squares[index];

來源

2012-12-15 23:40:18 Neil

喔！似乎這是問題所在，需要進一步測試，但我認爲是這樣。至少我在其中一項測試中得到了正確的結果。 –

@TomLilletveit底部的「||」條件也是IMO的問題。查看關於您的問題的最新評論。只有goUp失敗時才考慮goDown。 –

應該不是你最後溶液狀態相比，尺寸 - 1？

if (target == 0 && index == squares.size() - 1) return true;

來源

2012-12-15 23:36:16

是的，但它仍然輸出錯誤的結果。 –

@Tom當描述一個問題時，諸如「它給出了錯誤的結果」，「它不起作用」以及其他任何組合都是毫無用處的。總是給出一個具體的例子，包括預期的和實際的輸出（你已經介紹了前兩部分，但不包括你的實際輸出），或者描述了確切的錯誤信息（比如說：「我用這個堆棧跟蹤獲得了下面輸入的一個堆棧溢出「）。 – Voo

C++：如何解決這個遞歸拼圖（subset-sum style）

回答

相關問題