假设初始位置为(1, 1)，在每一步中，通过以下给定的规则，找出是否可以到达(x, y)

Question

You are given the coordinates (x,y). Initially, you are at (1,1) and are required to go to (x,y) using the following rule: If the current position is (a,b) then in the next move, you can move only to (a+b,b) or (a,a+b). Write a program to check if you can reach (x,y) using only the described moves.

我已经尝试通过递归来解决上面Java中提到的这个问题。但是该程序不适用于某些测试用例。我找不到问题所在。但我知道这是一种蛮力方法。

import java.util.*;
class Solution{
    static boolean sol(int a, int b, int x, int y){
        if( a == x && b == y)
            return true;
        else if(a > x || b > y)
            return false;
        else{
            if(sol(a+b, b, x, y)) return true;
            if(sol(a, a+b, x, y)) return true;
        }
        return false;
    }
    static String ans(int x, int y){
        if(sol(1, 1, x, y)) return "Yes";
        return "No";
    }
    public static void main(String[] args) {
        int x, int y;
        Scanner sc = new Scanner(System.in);
            x = sc.nextInt();
            y = sc.nextInt();
            System.out.println(ans(x, y));
        
    }
    
}

这是我写的代码。有人能告诉我解决这个问题的有效方法并告诉我我的代码有什么问题吗？

Answer 1

看看：

if(sol(a, a+b, x, y)) return false;

该条件应 return 为真，如问题“您只能移动到 (a+b,b) 或 (a,a+b)”。

import java.util.*;
class Solution{
    static boolean sol(int a, int b, int x, int y){
        if( a == x && b == y)
            return true;
        else if(a > x || b > y)
            return false;
        else{
            if(sol(a+b, a, x, y)) return true;
            if(sol(a, a+b, x, y)) return true;
        }
        return false;
    }
    static String ans(int x, int y){
        if(sol(1, 1, x, y)) return "Yes";
        return "No";
    }
    public static void main(String[] args) {
        int x,y;
        Scanner sc = new Scanner(System.in);
            x = sc.nextInt();
            y = sc.nextInt();
            System.out.println(ans(x, y));
        
    }
    
}

最优方法：

使用 two-dimensional 矩阵 (x * y) 来了解该单元格是否被访问，如果被访问则存储结果。

未访问过 -> -1

已访问并可能从该位置到达 (x,y) -> 1

已访问并可能从该位置到达 (x,y) -> 0

import java.util.*;
class Solution{
    
    static boolean sol(int a, int b, int x, int y, int[][] dp){
        if( a == x && b == y)
            return true;
        else if(a > x || b > y)
            return false;
        else if(dp[a][b] == 1)
            return true;
        else if(dp[a][b] == 0)
            return false;
        else if(sol(a+b, a, x, y, dp) || sol(a, a+b, x, y, dp)){
                dp[a][b] = 1;
                return true;
        }
        dp[a][b] = 0;
        return false;
    }
    
    static String ans(int x, int y, int[][] dp){
        if(sol(1, 1, x, y, dp)) return "Yes";
        return "No";
    }
    
    public static void main(String[] args) {
        int x,y;
        int[][] dp;
        
        Scanner sc = new Scanner(System.in);
        x = sc.nextInt();
        y = sc.nextInt();
        
        dp = new int[x+1][y+1];
        for(int[] row : dp)
            Arrays.fill(row,-1);
        
        System.out.println(ans(x, y, dp));
        
    }
    
}

Answer 2

您的问题是：

If the current position is (a,b) then in the next move, you can move only to (a+b,b) or (a,a+b).

你的错误是（在粗体中突出显示）：

1. if(sol(a+b, <strong>a</strong>, x, y)) return 真； // a 应该是 b
2. if(sol(a, a+b, x, y)) return <strong>false</strong>; // false 应该是 true

更正两个点（在粗体中突出显示内联）：

1. if(sol(a+b, <strong>b</strong>, x, y)) return true;
2. if(sol(a, a+b, x, y)) return <strong>true</strong>;

或通过组合它们来简化： if(sol(a+b, <strong>b</strong>, x, y) || sol(a, a+b, x, y)) return 真;

根据上述建议，完整代码为：

import java.util.*;
class Solution {
    static boolean sol(int a, int b, int x, int y) {
        if(a == x && b == y)
            return true;
        else if(a > x || b > y)
            return false;
        else if(sol(a+b, b, x, y) || sol(a, a+b, x, y)) // fix applied here
            return true;
        return false;
    }
    static String ans(int x, int y) {
        if(sol(1, 1, x, y)) return "Yes";
        return "No";
    }
    public static void main(String[] args) {
        int x, int y;
        Scanner sc = new Scanner(System.in);
        x = sc.nextInt();
        y = sc.nextInt();
        System.out.println(ans(x, y));
    }
}

---

编辑比暴力优化的解决方案

我们从 (1, 1) 开始，(a, b) 的任何下一步都是 (a+b, b) or (a, a+b)，因此 x > 0 and y > 0 是任何步骤 (x, y) 的必要条件。

现在，让我们说，

Step k:   (a, b)  
Step k+1: (a2, b2) = (a+b, b) OR (a, a+b)

所以如果我们想从 step#k+1 推导出 step#k 那么我们可以说 (a, b) 可以是这两个之一：(a2 - b2, b2) OR (a2, b2 - a2)。我们可以 轻松删除一个选项 因为我们知道 a > 0 and b > 0.

• 如果 (a2 - b2) > 0 则 (a, b) 必须是 (a2 - b2, b2)。
• 同样，如果 (b2 - a2) > 0 那么 (a, b) 必须是 (a2, b2 - a2)。
• 如果 a2 == b2（而不是 1），则 a2 - b2 和 b2 - a2 将是 0，这是不可能的，因为需要 a > 0 and b > 0条件。

所以，我们将从目的地(x, y)出发，并尝试在线性时间内通过上述观察到达(1, 1)。要点是：

static boolean solve(int x, int y) {
    if (x == 1 && y == 1) {
        return true;
    }
    if (x == y || x < 1 || y < 1) {
        return false;
    }
    if (x > y) {
        return solve(x - y, y);
    } else {
        return solve(x, y - x);
    }
}

以上解决方案是递归和 Ole V.V。如果输入数字很大并且堆栈内存分配相对较少，则 关于可能 WhosebugError 有一个很好的观点。根据他关于需要迭代解决方案的建议，我提供以下迭代方法的要点：

static boolean solve(int x, int y) {
    while (x > 0 && y > 0) {
        if (x == y) {
            return (x == 1); // x and y can be same if they are 1, otherwise impossible
        }
        if (x > y) {
            x = x - y;
        } else {
            y = y - x;
        }
    }
    return false;
}

Answer 3

已经指出了你逻辑上的问题，但是现在的做法很浪费内存。

说明：您正在使用递归，这是对 stack 的隐式使用，其中存储了您调用的方法及其状态。如果 x 和 y 是非常大的数字，那么您将遇到堆栈溢出问题（没有双关语！）。

解决方案

我们知道

• 最初你在点 (1, 1)
• 您的 (a, b) 位置是 (1, 1), (a' + b, b) 或 (a, a + b')
• 如果a > b，则a = a' + b，所以，前一个位置是(a - b, b)
• 如果a < b，则b = a + b'，所以，前一个位置是(a, b - a)
• 如果 a == b，那么你要么在 (1, 1) 的初始位置，要么，你无法通过纯粹的值来确定之前的状态是什么

这允许您节省大量内存，假设您以迭代方式实现它。您需要遵守的理念如下：

• 如果到达(x,y)，则算法结束，不管发生什么，因为问题是它是否可解，所以不需要存储实际解
• 当你执行一个步骤时，你需要知道你是否将一个坐标添加到另一个坐标，或者你已经退后一步
• 如果这个点看起来像(a, a)，那么你需要把之前的值存储在一个栈中，还有你走的方向，这样你就可以回到它，(的位置a, a) 必须特殊对待
• 如果你不只是向后移动，那么先尝试增加左边的坐标
• 如果你刚好在向后移动之后和向后移动之前，要么 a > b 为真，要么 a == b 为真，条件是我之前提到的堆栈中的方向是左，然后增加第二个坐标而不是第一个坐标，如果存在则更改堆栈顶部条目的方向
• 如果您刚好在向后移动之后并且 a < b 为真，或者 a == b 为真且条件是堆栈中第一个坐标高于第二个，那么下一步将是也向后
• 如果你执行向后移动并且向后移动之前的位置是（a，a），那么你可以从你的堆栈中删除相应的条目
• 如果在向后移动后到达 (1, 1)，则无论方向如何，都可以结束算法，因为 (2, 1) 的步长与 (2, 1) 的步长相同(1, 2)，包括子树，由于 adding
的可交换性

Answer 4

优化迭代解决方案

but still, the code isn't working. It's giving me memory limit exceeded error. Is there any other logic for this program?

在我的 Java 上，如果任一输入为 10 000 或更多，您的程序使用来自 Viral Lalakia 的答案的修复程序崩溃并出现堆栈溢出。可以通过调整 JVM 的内存分配来调整限制，但实际上您无法将内存增加到您想要的任何值。有效的解决方案是避免递归并编写迭代解决方案。

我的主要想法是从目标 (x, y) 向后迭代。 Viral Lalakia的优化方案也是从目的地往回走，节省了时间，但是只要递归，我怀疑不节省space ]，也就是递归程序是运行出来的。

所以在循环中从 x 和 y 中找到以前的坐标。

• 如果 x < y，则之前的坐标必须是 (x, y - x)。所以从 y 中减去 x。
• 如果相反 x > y 做相反的减法。
• 如果 x == y 则没有可能的先前坐标。如果我们在起点 (1, 1)，我们知道存在解决方案。 Return 是的。如果不是，return 错误。

每次循环检查你减少的数字是否小于1，如果小于1，则无解。 Return 错误。

顺便说一句，该算法与寻找x和y的最大公约数的算法相同。因此，非常简单的解决方案是 BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)) 并将结果与​​ BigInteger.ONE 进行比较以确定路径是否存在。

Link: