在C/C++中,是否有一种方法可以停止回溯算法,在找到第一个解之后而不退出程序。
我希望我的函数能够立即退出函数,而不是逐层递归地声明返回语句。
在C/C++中,是否有一种方法可以停止回溯算法,在找到第一个解之后而不退出程序。
我希望我的函数能够立即退出函数,而不是逐层递归地声明返回语句。
如果你有一个标志,在完成时设置,然后在函数中进行检查,你可以解决这个问题。例如:
void foo(..)
{
if (g_done) return;
...
}
如果您不确定需要什么,我建议您实现自己的堆栈,并完全避免使用递归。这样退出回溯树变得非常简单(只需一个“return”),并且还可以通过再次调用函数来恢复搜索以查找下一个解决方案,假设用户定义的堆栈状态被保留(在静态变量中)。当然,将简单的递归程序转换为循环需要一些编程开销,但这很容易做到。
实际上这取决于你的实现方式,但你可以设置一些特殊参数并将其用作标志,例如“我们是否已经得到了解决方案?如果是,则中止当前例程并仅将该解决方案输出”。
return
退出每个递归级别。这将被编译器优化,性能甚至比exception
方法更好(异常处理会调用堆栈展开,因此在非异常处理方面不应使用,因为它很慢)。 - M. Williamsint SumNum(int nMax)
{
if (0 == nMax)
return 0;
else
return nMax + SumNum(nMax-1);
}
实际值是在回溯过程中计算的。
但是,您可以按照以下方式重写代码:
int SumNum(int nMax, int nSum)
{
if (0 == nMax)
return nSum;
else
return SumNum(nMax-1, nSum+nMax);
}
现在,你可以做以下的技巧:
int SumNum(int nMax, int nSum)
{
if (0 == nMax)
throw nSum;
else
return SumNum(nMax-1, nSum+nMax);
}
f()
{
int nSum;
try
{
SumNum(100, 0);
}
catch (int _nSum)
{
nSum= _nSum;
}
}
你可以在C和C++中使用setjmp()/longjmp(),以一种简单但有效的方式绕过需要将标志传递回去的需求。
setjmp
和longjmp
。 - M. Williams