Recursion in which memory ends

Question

I have a programming assignment that looks like this:

You are given three numbers a, b and c. (1 ≤ a, b, c ≤ 10 ^ 18) Each time you have two choices, either add b to (a + = b) or add a to b (b + = a). Write a program that will print YES or NO depending on whether you can go to c by adding a and b to each other.

I tried to solve this problem using recursion, which branches up to two branches each time when one branch stores + b, b and the other branch stores a, b + a. In each recursive call, the function checks the values ​​of a and b, and if they are equal to c, the search stops and the function displays YES. Recursion stops when either a or b have a value greater than c.

Here's how 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;
}

, b c 64- , , .

: - ( ), ?

Answer 1

, . , , , . , , a+=b b+=a, , , ( a = 2 b = 3 ). , , - , "is c "?

, , . . , node . . , , . , . , , , 64 , 2 ^ 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% , . .

Answer 2

@Oliver Charlesworth, , . , b, , a ( OP), .

#include <stdio.h>

int main(){
    unsigned long long int a, b, c, bb;
    scanf("%I64u", &a);
    scanf("%I64u", &b);
    scanf("%I64u", &c);

    if (a >= 1 && a < b && b < c) {
        for (bb=b; bb<c; bb+=b) {
            if ((c - bb) % a == 0) {
                printf ("YES\n");
                return 0;
            }
        }
    }
    printf("NO\n");
    return 0;
}