我正在计算 x 和 y 的可能组合的值。它有效,但是当我输入大数字时,它花费的时间太长了。你对更好的算法有什么想法吗?
ax + by = c
程序的输入是a、b、c,应该是非负数。我的代码如下所示:
int combs=0;
for(int x=0; x < c; x++) {
for(int y=0; y < c; y++) {
if( (a*x) + (b*y) == c) {
combs++;
}
}
}
一个更快的方法是先做一些数学运算。ax+by=c
=>y=(c-ax)/b
int combs=0;
for(int x=0; x < c; x++) {
int y = (c-a*x)/b;
if( (a*x) + (b*y) == c)
combs++;
}
摆脱嵌套循环是提高性能的最重要的细节。您可以做的另一件事是按照 Antti Haapala 在下面的评论中建议的那样做,并使用 ax 而不是 x。
int combs=0;
for(int ax=0; ax < c; ax+=a) {
int y = (c-ax)/b;
if( (ax) + (b*y) == c)
combs++;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句