java - 假设初始位置是(1, 1)，看看你是否可以在每一步通过以下给定的规则到达(x, y)

Question

关闭。这个问题需要debugging details .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

去年关闭。




Improve this 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 the current position is (a,b) then in the next move, you can move only to (a+b,b) or (a,a+b).

你的错误是(在 粗体 中突出显示):

if(sol(a+b, a, x, y)) return true; // a should be b

if(sol(a, a+b, x, y)) return false; // false should be true

用(在 粗体 中突出显示内联)更正两个点:

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

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

或通过组合它们来简化:if(sol(a+b, b, x, y) || sol(a, a+b, x, y)) return true;根据上述建议，完整代码将是:

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来自 step#k+1那么我们可以说 (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.在 this answer 中有一个好点子关于可能 StackOverflowError如果输入数字很大并且堆栈内存分配相对较少。根据他对迭代解决方案需求的建议，我提供了以下迭代方法的要点:

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;
}