确定是否可以生成答案

  static int ans = 0;
  public static void ablehelper(int a, int b, int c, int d){
      if(a != c && (b + a) > c){
          return;
      }
      if(b != d && (b + a) > d){
          return;
      }
      if(a == c && b == d){
          ans = 1;
          return;
      }
      ablehelper(a + b, b, c, d);
      ablehelper(a, b + a, c, d);

  }
  public static String able(int a, int  b, int c, int d){
      ablehelper(a, b, c, d);
      if(ans == 1){
          return "Able to generate";
      }else{
          return "Not table to generate";
      }
  }

As per one of the algorithms described below, I wrote this:


public static String betterSolution(int a, int b, int c, int d){
          while( c > a || d > b){
              if(c > d){
                  c = c-d;
              }else{
                  d = d-c;
              }
          }
          if( c == a &&  d == b){
              return "Able to generate";
          }else{
              return "Not able to generate";
          }
      }

#1 楼

这是一个有趣的问题！您让我们的聊天室长时间讨论了这个问题：)
您的方法很有趣，但是它有一个很大的缺陷：
您是从错误的方向开始的！
而不是从a和b开始，从c和d开始。问问自己这个问题：达到该数字的方法是什么？
请考虑以下问题：（我将使用符号a, b --> c, d）

4, 5 --> 15, 19

15, 19之前必须采取什么步骤？是哪个号码？
是15, x还是x, 19？ x, 19将是坚果，因为15小于19。因此，我们知道它是15, x。 x必须为4，因为15 + 4 =19。
通过继续减去具有最小数字的最大数字，我们可以找出所有可以产生这两个数字的可能输入。

15, 19
15, 4
11, 4
7, 4
3, 4
3, 1
2, 1
1, 1

因为a, b是4, 5，所以我们已经在15, 4上看到了，因为4 < targetB是不可能的。
以1, 2 --> 3, 8为例：

3, 8 <--- 8 is bigger, so decrease it by 3
3, 5 <--- 5 is bigger, so decrease it by 3
3, 2 <--- 3 is bigger, so decrease it by 2
1, 2 <--- 2 is bigger, so decrease it by 1
1, 1

等等，那是什么！？ 1, 2在列表中！这是我们的幸运日！我们找到了匹配的a, b！因此，它将返回true。
我将把实现代码的有趣部分留给您：)希望您理解这种方法。
关于时间复杂性：比当前的方法快得多。至于实时复杂性，请询问@rolfl。

#2 楼

复杂性讨论

您问复杂性是否为\ $ O（2 ^ n）\ $。

如果这确实是一个面试问题，则要求您讨论解决方案的复杂性，您应该给出的答案大致如下：


计算的复杂性旨在描述解决方案如何随着您的变化而扩展输入数据量。通常，
两种不同类型的复杂度是键，时间复杂度和空间
复杂度。对于时间复杂度，如果复杂度为\ $ O（n）\ $并且
输入数据加倍，则时间将加倍。如果复杂度是
\ $ O（n ^ 2）\ $，那么当输入翻倍时，时间将增加四倍。

因为在这个问题上，只有4个输入值，没有办法有意义地讨论时间或空间的复杂性。
没有意义。输入数据永远不会缩放。


通过暗示复杂度为\ $ O（n ^ 2）\ $，您在复杂性知识上显示出差距。首先，您的问题中没有定义n ...这是什么？

此外，如果时间复杂度确实很重要/适用，则复杂度为\ $ O（2 ^ n）\ $很大。每次添加输入值时，执行时间都会加倍。因此，例如，如果您当前有4个输入值，并且需要4秒，那么5个输入值将花费8秒，6个输入值将花费16秒，而20个输入值将花费... ..差不多一天了。和24个值将花费一个月，而30个值将需要8.5年....

#3 楼

编辑：这是基于对Simon的优化的线性时间算法！

算法

我们假定输入由非负整数组成。

Simon的算法是一项出色的改进，它可以很好地解决解决方案经常在两个选择之间“交替”出现的问题，但对于包含较长选择项的长“条纹”的解决方案，效果却很差。在解决方案a=1, b=1, c=n, d=1中可以观察到这一点。 Simon的算法将从\ $ n \ $倒数到\ $ 1 \ $，这是指数运行时间（根据表示输入所需的位）。

然后解决方案是“压缩这些路径。

和Simon的算法一样，我们从c和d开始，并找出最大的路径。假设它是c（如果不是，只需应用对称推理）。因此，任何解决方案的上一步都必须是将c增加d。但是，与Simon的算法不同，我们将确定情况是多少次。这很简单：c就是d或c/d（使用整数除法）的整数倍。因此，我们不再对c-d, d进行递归，而是对c - d*(c/d), d进行递归。

但是现在我们可能可以“跳过”我们要寻找的起始位置（a,b）。不过，这很容易检测。最后，返回b==d and (c - a)%d == 0。最后，Simon没有提到的拐角处，当允许\ $ 0 \ $作为有效输入时，有必要考虑一下（Simon没有，所以他的算法很好） ：c == d。如果是这种情况，那么实际上有两个有效的先前步骤：0, d和c, 0。我们必须检查我们的解决方案是否为上述任何一种，然后简单地终止。

分析

在每一步中，我们两个数字之一至少缩小一半（最坏的情况是\ $ c = 2d-1 \ $）。当两个数字均为0时，我们的算法将在最坏的情况下终止。因此，在\ $ O（\ log c + \ log d）\ $时间之后，该算法必须终止。输入的大小是线性的。

可以使用循环或尾部递归在\ $ O（1）\ $空间中完成。

代码

最后，这是我在Java中的实现（经过编译并测试了一些输入）

public static boolean hasSolution(int a, int b, int c, int d){
    if(a < 0 || b < 0 || c < 0 || d < 0){
        throw new IllegalArgumentException("Negative inputs are not allowed");
    }

    if(c == 0 || d == 0){
        //This is a fixed point, an inescapable blackhole!
        return a == c && b == d;
    }

    while(true){
        if(a == c && b == d){
            //We're done!
            return true;
        }else if(c == d){
            //weird corner case
            return hasSolution(a, b, 0, d) || hasSolution(a, b, c, 0);
        }else if(c > d){
            int next = c - d*(c/d);
            if(next < a){
                //we're going to overshoot! 
                // Check if there exists a k such that 
                // a + k*d == c
                return b == d && (c - a)%d == 0;
            }else{
                //recurse!
                c = next;
            }
        }else{
            //No really, c is > d
            int temp;
            temp = a; a = b; b = temp;
            temp = c; c = d; d = temp;
        }
    }
}

原始答案（对OP算法的简要分析）：

这是您的程序的一个非常糟糕的示例：
a=1, b=1, c=999999999, d=1

您的程序将继续执行第一个递归步骤，直到从a到c为止，然后返回true。

您的程序将在\ $ \ Omega（c）\ $时间运行，通常将其视为“指数”，因为它在所需位数上是指数代表输入。另外，您的程序将需要\ $ \ Omega（c）\ $空间，因为递归的第一个分支无法进行尾调用优化，因此每次迭代都将整个堆栈框架推到顶部。因此，您消耗的空间也与实际输入大小成指数关系。将此算法天真地转换为非递归（具有循环和堆栈）将无法解决此问题。

请注意，这仅适用于此输入。我不知道该算法的真正渐近运行时间是多少，因为怪异的输入具有怪异的行为，而且我不清楚真正的最坏情况到底是什么。本质上，您是在二叉树上进行深度优先搜索，其深度可能类似于\ $ O（c / b + d / a）\ $节点。因此，这绝对是空间上最坏的情况（如我的示例所示），但是运行时间尚不清楚。这样一棵树中的节点数可能高达\ $ 2 ^ {depth} \ $，所以也许有一个输入显示了\ $ \ Omega（2 ^ {c + d}）\ $运行时间，（输入大小成倍增加），但我不清楚如何触发（如果可能）。我倾向于认为树中几乎没有太多的节点，因为树的“中间”变薄的速度比侧面要快得多（肯定总是有\ $ O（\ log { （c + d）}）\ $较深。不过，您总是可以通过使答案为“否”来强制算法搜索整棵树（假设@janos的改进会在找到正确答案后终止）。
如果我不得不猜测，类似
a=2, b=2, c=2n+1, d=2n+1
表现出最坏的情况。

我相信递归树会像左右两边一样-大多数分支的大小为\ $ n \ $，接下来的向外分支的大小为\ $ n / 2 \ $，然后是\ $ n / 4 \ $，依此类推（减半），直到达到两个大小为\ $ 1的中间分支\ $。这给了我们大约\ $ 4n \ $个节点，与\ $ n \ $渐近相同，因此我猜想算法“ only”在最坏的情况下在指数时间和空间上运行。

Simon的答案无论如何都要好得多，而且也容易得多分析（尽管在最坏的情况下它仍然是指数）。

#4 楼

使其成为纯递归

将实现转变为纯递归非常简单：

public boolean ablehelper(int a, int b, int c, int d) {
    if (a != c && (b + a) > c) {
        return false;
    }
    if (b != d && (b + a) > d) {
        return false;
    }
    if (a == c && b == d) {
        return true;
    }
    return ablehelper(a + b, b, c, d) || ablehelper(a, a + b, c, d);
}

您可以简化一下：

if (a > c || b > d) {
    return false;
}
if (a == c && b == d) {
    return true;
}
return ablehelper(a + b, b, c, d) || ablehelper(a, a + b, c, d);

递归，但要从另一个方向去

正如西蒙指出的，最好从另一个方向来思考：意识到之前的步骤得出解将具有以下一组值之一：


a = c , b = d - c, c , d - c
a = c - d, b = d , c - d, d

即在第一种情况下，您到达了通过使用(a, a + b)解决方案，在第二种情况下，通过采用(a + b, b)。

朝这个方向思考将有所帮助，因为您无需探索将很多小数加起来的整个空间或可能无法达到正确的配对。这样一来，您将可以更快地找到解决方案：

if (a > c || b > d) {
    return false;
}
if (a == c && b == d) {
    return true;
}
if (c > d) {
    return ablehelper(a, b, c - d, d);
}
return ablehelper(a, b, c, d - c);

请记住，递归解决方案并不是此处的最佳方法。您不可避免地会在StackOverflowError中获得足够大的N，例如，在我的PC上，默认设置为9999足够大。您可以重构为使用循环而不是递归，这也适用于更大的(1, 1, N, 1)。

以递归方式，从另一个方向出发，对类固醇

@Gankro的答案，请注意，当N时，而不是多次对c = X + Y * d进行递归，我们可以一步一步执行相同的操作：(c - d, d)。这样，可以通过以下方式改进实现的最后几行：

if (c > d) {
    return ablehelper(null, a, b, c - d * Math.max(1, c / d - 1), d);
}
return ablehelper(null, a, b, c, d - c * Math.max(1, d / c - 1));

我们不知道(c - d * Y, d)和X，但是Y必须在Y和c / d之间。因此，我们取c / d - 1，这样我们就不会过冲或减去过多。请确保c / d - 1的乘数至少为1。

复杂度

如果我能计算出正确的数值，我将再次发布。现在，我宁愿不说些愚蠢的话。我想说的是，也许最坏的情况是您无法使用快捷方式，而不得不从Math.max和c交替减法，例如使用一组斐波那契数，例如从d到(c, d) = (21, 34)：：

21, 34
21, 13
8, 13
8, 5
3, 5
3, 2
1, 2
1, 1

但是如何基于(1, 1)来表达和估计其复杂性，我不知道...