java - java上的复活节彩蛋递归函数

Question

我在 java 中被分配了一个任务，它涉及一个复活节彩蛋游戏，当我给你 n 个鸡蛋时开始，当你正好剩下 m 个鸡蛋时结束。在游戏的任何阶段，假设你还剩n个鸡蛋，那么你可以还一些鸡蛋，但必须遵守以下规则:

• 如果 n 是偶数，那么你可以恰好还给 n/2 个鸡蛋。

• 如果 n 可以被 3 或 4 整除，那么你可以将 n 的最后两位数字相乘并返回这个许多鸡蛋。

• 如果 n 能被 5 整除，那么你可以还给恰好 m 个鸡蛋。

• 如果n 是质数，那么你可以恰好还给一个鸡蛋。

我必须编写一个名为 picnic 的函数，如果按某种顺序应用规则，我们正好剩下 m 个鸡蛋，该函数将返回 true；否则为假:

public static boolean picnic(int n, int m) { … }

我的任务是:

a) 提供野餐的递归关系(int n, int m)

b) 使用递归关系在 Java 中实现递归函数

c) 开发 picnic(250, 42) 的完整递归调用树

d) 这里的递归模式是什么？ (尾递归与否？树递归还是线性递归？)

e) 这个函数有没有提醒什么算法设计策略？如果有，是哪一个？

我已经完成问题 a) 并以此作为答案:

public class EasterEggs {   
    public static boolean picnic (int n, int m) {
        if (n == m)
        return true;
        else return (picnic(n,m));
    }
}

而且我不确定如何实现递归函数。我尝试了几次，但仍然一无所获。

问题 b 和 c 是我在 atm 遇到的最大问题，我相信我能弄清楚 d 和 e。有人能帮我解决这个问题吗？并可能告诉我如何实现它？

Answer 1

在递归关系中，我们不必像您在问题中提到的那样定义类和方法。这是树递归而不是尾递归。而这个函数让我们想起了Backtracking设计策略。

对于 b) 部分，我的解决方案很简单且蛮力。

public class EasterEggs {   
    public static boolean picnic (int n, int m) {
      if (n == m)
        return true;
      if(n < m)
        return false;

      boolean result = false;

      if(n%2 == 0)
         result = picnic(n-n/2,m);
      if((n%3 == 0 || n%4 == 0) && (result == false))
         result = picnic(n-lastTwoDigitMultiply(n),m);
      if(n%5 == 0 && (result == false))
         result = picnic(n-m,m);
      if(isPrime(n) && (result == false))
         result = picnic(n-1,m);

      return result;  
    }
}