递归的运行内存分支 [英] Recursion that branches running out of memory
问题描述
我有一个编程任务是这样的：
I have a programming assignment that goes like this:
您给出三个数字A，B和C。 （1≤а，B，C≤10 ^ 18）
每次有两个，选项，可以将B加入A（A + = B），或添加到B（B + = A）。编写一个程序，将通过增加a和b彼此打印出来YES或NO取决于你是否能得到到c。
You are given three numbers a, b, and c. (1 ≤ а, b, c ≤ 10^18) Each time you have two choises, either add b to a (a+=b), or add a to b (b+=a). Write a program that will print out YES or NO depending on whether you can get to c by adding a and b to each other.
我试图解决使用递归这个问题，每次跳转到两个分支，其中一个分店A + B，b和其他分店A，B + A。在每一个递归调用的函数检查a和b的值，如果他们是等于C就立即停止搜索功能打印YES。当A或B有一个值大于c递归停止。
I've tried solving this problem using recursion that branches to two branches every time where one branch stores a+b, b and the other branch stores a, b+a. In every recursive call, the function checks the values of a and b, and if they are equal to c the search stops and the function prints YES. The recursion stops when either a or b have a value greater than c.
下面的分支是如何工作的：
Here's how the branching works:
和这里的code在C：
And here's the code in 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;
}
现在，这一计划适用于小数目，但是由于B和C可以是任意的64位数字，可以将树分支本身就是一个数十亿次，程序运行的内存和崩溃。
Now, this program works for small numbers, but since a b and c can be any 64-bit number, the tree can branch itself a few billion times, and the program runs out of memory and crashes.
我的问题是：有没有什么办法可以改善我的code，或使用任何其他方式（其他然后递归）来解决这个
My question is: Is there any way i can improve my code, or use any other way (other then recursion) to solve this?
推荐答案
好吧，我得承认，这竟然是一个有趣的问题。我真的以为，应该有找出答案的快捷方式，但更多的我看了看问题，更复杂，它成了。例如，如果您曲折下来的树，交替 A + = B 与 B + = A ，你基本上是创建斐波纳契数列（想象一个= 2和b = 3下手）。这意味着，如果你能很快找到答案，你可以以某种方式使用类似的程序来回答是 C 斐波纳契数？
OK I'll have to admit that this turned out to be a fascinating question. I really thought that there should be a quick way of finding out the answer but the more I looked at the problem, the more complex it became. For example, if you zigzag down the tree, alternating a+=b with b+=a, you are essentially creating the fibonacci sequence (imagine a=2 and b=3 to start with). Which means that if you could find the answer quickly, you could somehow use a similar program to answer "is c a fibonacci number"?
所以，我从来没有什么比搜索二叉树更好地走了过来。但我没有想出一个方法来搜索二叉树不会耗尽内存。在我的算法的关键诀窍是，在每一个节点，你需要搜索两个子节点。但你并不需要递归下来两个路径。你只需要向下递归一个路径，如果失败，您可以遍历其他孩子。递归时，你应该总是选择其中较小数量变化的路径。这保证了你加倍每个递归级别最小元素，它可以保证你将只最大递归64次在你的最小元素将超过2 ^ 64。
So I never came up with anything better than searching the binary tree. But I did come up with a way to search the binary tree without running out of memory. The key trick in my algorithm is that at every node you need to search two child nodes. But you don't need to recurse down both paths. You only need to recurse down one path, and if that fails, you can iterate to the other child. When recursing, you should always pick the path where the smaller number changes. This guarantees that you are doubling the minimum element on each recursion level, which guarantees that you will only recurse 64 times max before your minimum element will exceed 2^64.
所以我写程序，运行它，和它的工作就好了。也就是说，直到我进入了 C 一个非常大的数字。在这一点上，它并没有结束。我从测试的算法似乎有一个O（N ^ 2）运行时间，其中N = C找到。下面是一些样品的运行时间（所有在桌面上运行64位Windows）。
So I wrote the program and ran it, and it worked just fine. That is until I entered a very large number for c. At that point, it didn't finish. I found from testing that the algorithm appears to have an O(N^2) running time, where N = c. Here are some sample running times (all on a desktop running 64-bit 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)
下面是我的code：
// 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％左右。你可以找到优化程序这里。
I optimized the above program by removing recursion, reordering the arguments so that a is always less than b at every step, and some more tricks. It runs about 50% faster than before. You can find the optimized program here.
这篇关于递归的运行内存分支的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
