我有一个编程作业是这样的：
给定三个数字 a、b 和 c。 (1 ≤ a, b, c ≤ 10^18) 每次有两个选择时，要么将 b 添加到 a (a+=b)，要么将 a 添加到 b (b+=a)。编写一个程序，根据 a 和 b 相加能否得到 c 来打印 YES 或 NO。
我尝试使用递归来解决这个问题，每次分支到两个分支，其中一个分支存储 a+b、b，另一个分支存储 a、b+a。在每次递归调用中，函数都会检查 a 和 b 的值，如果它们等于 c，则搜索停止并且函数会打印 YES。当 a 或 b 的值大于 c 时，递归停止。
Here's how the branching works:
这是 C 语言中的代码：
#include <stdio.h>
#include <stdlib.h>
void tree(long long int a, long long int b, long long int c){
if(a==c || b==c){
printf("YES");
exit(0);
}
else if(a<c && b<c){
tree(a, b+a, c);
tree(a+b, b, c);
}
}
int main(){
long long int a, b, c;
scanf("%I64d", &a);
scanf("%I64d", &b);
scanf("%I64d", &c);
tree(a, b, c);
printf("NO");
return 0;
}
现在，该程序适用于小数字，但由于 a b 和 c 可以是任何 64 位数字，因此树可以自行分支数十亿次，并且程序会耗尽内存并崩溃。
我的问题是：有什么方法可以改进我的代码，或者使用任何其他方法（除了递归）来解决这个问题？
好吧，我不得不承认这是一个令人着迷的问题。我真的认为应该有一种快速的方法来找到答案，但我越看这个问题，它就变得越复杂。例如，如果你沿着树蜿蜒而下，交替a+=b with b+=a，您实际上是在创建斐波那契数列（想象一下 a=2 和 b=3）。这意味着如果您可以快速找到答案，您可以以某种方式使用类似的程序来回答“是”c斐波那契数列”？
所以我从来没有想出比搜索二叉树更好的方法。但我确实想出了一种在不耗尽内存的情况下搜索二叉树的方法。我的算法的关键技巧是，在每个节点，您需要搜索两个子节点。但您不需要沿着两条路径递归。您只需要沿着一条路径递归，如果失败，您可以迭代到另一个子路径。递归时，应始终选择数字变化较小的路径。这保证了您在每个递归级别上将最小元素加倍，从而保证在最小元素超过 2^64 之前最多只会递归 64 次。
所以我编写了程序并运行它，它运行得很好。直到我输入了一个非常大的数字c。到那时，事情还没有结束。我通过测试发现该算法的运行时间似乎是 O(N^2)，其中 N = c。以下是一些示例运行时间（全部在运行 64 位 Windows 的桌面上）。
Inputs Time in minutes
------ ---------------
a=2 b=3 c=10000000000 (10^10): 0:20
a=2 b=3 c=100000000000 (10^11): 13:42
a=2 b=3 c=100000000001 : 2:21 (randomly found the answer quickly)
a=2 b=3 c=100000000002 : 16:36
a=150 b=207 c=10000000 (10^7) : 0:08 (no solution)
a=150 b=207 c=20000000 : 0:31 (no solution)
a=150 b=207 c=40000000 : 2:05 (no solution)
a=150 b=207 c=100000000 (10^8) : 12:48 (no solution)
这是我的代码：
// Given three numbers: a, b, c.
//
// At each step, either do: a += b, or b += a.
// Can you make either a or b equal to c?
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
static int solve(uint64_t a, uint64_t b, uint64_t c);
int main(int argc, char *argv[])
{
uint64_t a = 0, b = 0, c = 0;
if (argc < 4) {
printf("Usage: %s a b c\n", argv[0]);
exit(0);
}
a = strtoull(argv[1], NULL, 0);
b = strtoull(argv[2], NULL, 0);
c = strtoull(argv[3], NULL, 0);
// Note, by checking to see if a or b are solutions here, solve() can
// be made simpler by only checking a + b == c. That speeds up solve().
if (a == c || b == c || solve(a, b, c))
printf("There is a solution\n");
else
printf("There is NO solution\n");
return 0;
}
int solve(uint64_t a, uint64_t b, uint64_t c)
{
do {
uint64_t sum = a + b;
// Check for past solution.
if (sum > c)
return 0;
// Check for solution.
if (sum == c)
return 1;
// The algorithm is to search both branches (a += b and b += a).
// But first we search the branch where add the higher number to the
// lower number, because that branch will be guaranteed to double the
// lower number, meaning we will not recurse more than 64 times. Then
// if that doesn't work out, we iterate to the other branch.
if (a < b) {
// Try a += b recursively.
if (solve(sum, b, c))
return 1;
// Failing that, try b += a.
b = sum;
} else {
// Try b += a recursively.
if (solve(a, sum, c))
return 1;
// Failing that, try a += b.
a = sum;
}
} while(1);
}
编辑：我通过删除递归、重新排序参数来优化上述程序，以便a总是小于b每一步，还有更多技巧。它的运行速度比以前快了大约 50%。你可以找到优化后的程序在这里 https://github.com/Jsdemonsim/Stackoverflow/blob/master/addnum.c.