我正在创建一个程序,该程序只使用1、2、6和13返回求数(n)所需的最小和数。它非常适用于n的小值,但一旦n达到200这样的值,程序就会花费太多时间来计算结果。
因此,我有两个问题:
1.有什么方法可以加快递归速度吗?
2.我应该避免使用递归,而是使用循环吗?
以下是评论代码:
#include <iostream>
#define MAX 500000
using namespace std;
void cal(int inp, int &mini, int counter = 0);
int main (void)
{
//Gets input
int n;
cin >> n;
//Defines mini as the MAX result we can get
int mini = MAX;
//Calls the function
cal(n, mini);
//Prints the best result
cout << mini << endl;
return 0;
}
void cal(int inp, int &mini, int counter)
{
//Breaks recursion if it finds an answer
if(!inp)
{
if(counter<mini) mini = counter;
return;
}
//Breaks recursion if the input is negative
//or the counter is more than the best result
else if((inp<0) || (counter>mini)) return;
//Counts amount of recursions
counter++;
//Tries every combination
cal(inp-13, mini, counter);
cal(inp-6, mini, counter);
cal(inp-2, mini, counter);
cal(inp-1, mini, counter);
return;
}
感谢
问题在于你的暴力。让我提出一个更好的建议:
预备赛:如果你有两个1,最好用一个2。如果你有三个2,最好用一个6。如果你有十三个6,最好用三分之六。
因此,任何可容许和看起来总是像n = 13m+k
,其中k
被写成1、2和6的和。通过这些预备条件,我们知道对于最优和,k
永远不会超过1+2*2+12*6 = 77
。(反之亦然。当然,78以下的数字最好没有13。)所以强行使用这些就足够了。然后可以使用查找表。
这仍然可以进一步优化,但它不应该在200时崩溃。
假设你已经找到了你的前77个条目(也可以优化),你可以这样做(仍然没有优化;-):
int num_13 = ((n-78) / 13) + 1;
int sum_length = MAX;
for (i = num_13; i*13 < n; i++) {
int tmp = entries_77[n-i*13]+i;
if (tmp < sum_length) {
num_13 = i;
sum_length = tmp;
}
}
我会更快地为模13的等价类编译一个数组,因为对于任何给定的等价类,任何超过78的数字都将具有相同的k
。
您可以使用DP(动态编程)方法来解决您的问题。众所周知的硬币问题
您的递归需要记忆以避免重复计算。并且不需要递归的第二个和第三个参数。我已经更新并对您的代码进行了解释。如果你有任何困惑,请告诉我。
#include <iostream>
#include <string.h>
#define INF 999999
using namespace std;
int cal(int inp);
int mem[502];
int main (void)
{
//Gets input
int n;
cin >> n;
//initialzing the array for using with memoization
memset(mem,-1,sizeof(mem));
//Calls the function
//Prints the best result
cout << cal(n) << endl;
return 0;
}
//returns the minimum quantity of sum operations to get inp.
int cal(int inp)
{
//Breaks recursion if it finds an answer.
//Return cost 0. As in this stage no processing was done.
if(!inp)
return 0;
// Returning infinite cost for invalid case.
if(inp < 0)
return INF;
int _ret = mem[inp];
// If already visited here before then no need to calcuate again.
// Just return previous calculation. This is called memoisation.
// If not visited then _ret would have equal to -1.
if(_ret >=0 )
return _ret;
_ret = INF;
//Tries every combination and takes the minimum cost.
_ret = min(_ret, cal(inp-13)+1);
_ret = min(_ret,cal(inp-6)+1);
_ret = min(_ret,cal(inp-2)+1);
_ret = min(_ret,cal(inp-1)+1);
// Updating the value so that can be used for memoization.
mem[inp] = _ret;
return _ret;
}
这也适用于更大的数字。复杂性是4*n。