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

Question

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

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

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

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

• 如果n 是质数，那么您只能还给一个鸡蛋。

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

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

我的任务是：

a) 提供picnic(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

你必须：

创建一个代表您的不同规则的枚举（其中有 4 个 :p）。让我们承认您将枚举命名为 ERule

创建一个带参数的递归函数

剩余的鸡蛋（最初== n）
米

递归函数的退出条件：

n = m（真）
n < m（假）
没有规则可以应用于 n（错误）

如果不满足退出条件，则只需为每个可应用于当前 n 的规则调用递归函数（在修改后的 n 值上调用它，具体取决于您测试的条件）。结果是所有结果的OR语句。

Answer 2

在递归关系中，我们不必像您在问题中提到的那样定义 class 和方法。这是树递归而不是尾递归。而这个函数让我们想起了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;  
    }
}

Answer 3

这是return给定数组是否可整除的最佳函数

/*样本数据

{3, 3, 6, 36} 3
{4} 2
{3, 4, 3, 6, 36} 3
{6, 12, 24, 36} 12
{} */

public class 可整除 {

public static void main(String[] args) {

    int[] sampleData = { 3, 3, 6, 36 };
    int divisible = 3;

    int result = isDivisible(sampleData, divisible);
    System.out.println(result);

}

static int isDivisible(int[] givenArray, int isDivisible) {

    for (int i = 0; i < givenArray.length; i++) {

        if ((givenArray[i] % isDivisible) != 0) {

            return 0;

        }
    }

    return 1;
}

}

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

Easter egg recursive function on java

java

algorithm

recursion

tail-recursion

recurrence