java 使用规则 * 对数字进行递归求和-仅递归

pieyvz9o  于 2023-03-28  发布在  Java
关注(0)|答案(4)|浏览(147)

所以练习是:
仅使用递归(无循环)
查找是否存在等于数组中给定数字的子地面,并遵循规则。
假设我有一个数组,我给予函数一个求和的数字,它必须遵守这个规则:你不能重复相同的数字,你不能在一行中对3个数字求和(不能做i+1和i+2)

int[] a = {5,4,2,1,3};

因此,在本例中:num 8 = true(4+3+1)(5+3)num 11 = false(4+5+2是3,但在一行中是三个)(5+2+1+3也是三个在一行中)
我的尝试是:

public static boolean sumRule(int[] a , int num){
        if (num == 0){
            return true;
        } else {

    return sumRule(a,num,0,a.length);
        }
}

private static boolean sumRule(int[] a, int num, int low,int high){
    if(low >= high || low < 0){
        return false;
    }

    if (a[low] == -1){
        return false;
    }

    if(a[low] == num || num-a[low] == 0 ){
        return true;
    }

    int temp = a[low];
    a[low] = -1;

    return  sumRule(a,num,low,high) || sumRule(a,num-temp,low+3,high) || sumRule(a,num-temp,low+1,high) ;

}

但是当我发送11到这个,它仍然返回true,有人知道我在这里错过了什么吗?
谢啦

6kkfgxo0

6kkfgxo01#

下面是完整的代码答案,下面是解释:
本质上,你需要把这个问题分解成一个递归问题,也就是说,你在每一步都要考虑选择(即是否在求和中使用一个数字),然后递归地计算两个选项。
基础案例:如果num == 0,那么我们知道它是真的。但是如果num!= 0,并且数组的长度为0,那么我们知道它是假的
递归情况:我们检查数组中的第一个数字是否小于或等于num。如果不是,那么我们不能使用它。所以我们使用所有相同的参数进行递归调用,除了数组现在是原始数组减去第一个数字。
如果我们可以使用这个数字(例如a[0] <= num),那么正确的答案可能使用这个数字,也可能不使用它。我们对每种情况进行递归调用,如果任何一个递归调用返回true,则返回true。
连续数规则:这很容易执行。我们添加一个名为'left'的参数,它告诉我们可以从数组的开头连续取的元素的数量。首先,left是2,因为我们最多可以取2个连续的数字。然后,如果我们在求和中使用数组中的第一个数字,我们就向左递减。如果我们不使用数组中的第一个数字,我们将left重置为2。在left变为0的情况下,我们别无选择,只能跳过数组顶部的当前数字。

class Main {
  public static void main(String[] args) {
    int[] a = new int[] {5,4,2,1,3};
    System.out.println(sumRule(a, 8));
    System.out.println(sumRule(a, 11));
  }

  public static boolean sumRule(int[] a , int num){
    if (num == 0){
        return true;
    } else {
      return sumRule(a,num,2);
    }
  }

  private static boolean sumRule(int[] a, int num, int left){
      if (num == 0) {
        return true;
      }

      if (a.length == 0) {
        return false;
      }

      int[] a_new = new int[a.length-1];
      for (int i = 1; i < a.length; i++) a_new[i-1] = a[i];

      if (left == 0) {
        return sumRule(a_new, num, 2);
      }

      boolean using_a0 = false;
      if (a[0] <= num) {
        using_a0 = sumRule(a_new, num-a[0], left-1);
      }

      boolean not_using_a0 = sumRule(a_new, num, 2);

      return (not_using_a0 || using_a0);
  }
}

编辑-上面代码的变体,不复制数组:

class Main {
  public static void main(String[] args) {
    int[] a = new int[] {5,4,2,1,3};
    System.out.println(sumRule(a, 8));
    System.out.println(sumRule(a, 11));
  }

  public static boolean sumRule(int[] a , int num){
    if (num == 0){
        return true;
    } else {
      return sumRuleNoLoop(a,num,2,0);
    }
  }

  private static boolean sumRuleNoLoop(int[] a, int num, int left, int startIdx){
      if (num == 0) {
        return true;
      }

      if (startIdx >= a.length) {
        return false;
      }

      if (left == 0) {
        return sumRuleNoLoop(a, num, 2, startIdx+1);
      }

      boolean using_a0 = false;
      if (a[startIdx] <= num) {
        using_a0 = sumRuleNoLoop(a, num-a[startIdx], left-1, startIdx+1);
      }

      boolean not_using_a0 = sumRuleNoLoop(a, num, 2, startIdx+1);

      return (not_using_a0 || using_a0);
  }
}
kr98yfug

kr98yfug2#

你可以添加的第一件事是检查一行中是否有3个数字被添加。用-1替换数组中的数字也会在递归调用中产生意想不到的副作用。下面是我的一些东西。你可以忽略我用来查看所使用的值的index参数。
说明:递归sumRule方法将问题分为两部分:

  • 第一部分取当前索引的值,并与从下一个索引开始的值的总和相加。
  • 第二部分假设,当前值不能用于求和。它只检查从数组的下一个值开始的子集内是否有求和。

在这个方法中,lastIndex会跟踪最后一个值的索引,因此,在第一次调用中,该值是0,第二次调用中是1,依此类推。
(start - lastIndex <= 1 ? consecutive + 1 : 1)是检查consecutive的值是否应该增加。连续= 1意味着,当前值被添加到总和。

public static boolean sumRule(int[] a, int num) {
    if (num == 0) {
      return true;
    } else {
      return sumRule(a, num, 0, 0, 0, 0, "");
    }
  }

  public static boolean sumRule(final int[] a, int num, int sum, int start, int consecutive, int lastIndex,
      String index) {
    if (consecutive == 3) {
      return false;
    }

    if (sum == num) {
      System.out.println(index);
      return true;
    }

    if (start >= a.length) {
      return false;
    }

    return sumRule(a, num, sum + a[start], start + 1, (start - lastIndex <= 1 ? consecutive + 1 : 1), start,
        index + ", " + start) || sumRule(a, num, sum, start + 1, consecutive, lastIndex, index);
  }
vxqlmq5t

vxqlmq5t3#

下面是我的实现。它包含解释不同部分的作用的注解。

public class RecurSum {
    /**
     * Determines whether 'sum' equals 'target'.
     * 
     * @param arr         - its elements are summed
     * @param sum         - sum of some elements in 'arr'
     * @param target      - required value of 'sum'
     * @param index       - index in 'arr'
     * @param consecutive - number of consecutive indexes summed to ensure don't exceed 3
     * @param start       - starting element in 'arr' which is used for back-tracking
     * 
     * @return "true" if 'sum' equals 'target'
     */
    private static boolean sumRule(int[] arr, int sum, int target, int index, int consecutive, int start) {
        if (sum == target) {
            return true;
        }
        else {
            if (index >= arr.length) {
                // if we have reached last element in 'arr' then back-track and start again
                if (start < arr.length) {
                    return sumRule(arr, 0, target, start + 1, 0, start + 1);
                }
                // we have reached last element in 'arr' and cannot back-track
                return false;
            }
            else {
                consecutive++;
                if (consecutive == 3) {
                    // skip 3rd consecutive element (because of the rule)
                    consecutive = 0;
                    return sumRule(arr, sum, target, index + 2, consecutive, start);
                }
                else {
                    if (sum + arr[index] > target) {
                        // recursive call but don't add current element of 'arr'
                        return sumRule(arr, sum, target, index + 1, 0, start);
                    }
                    // recursive call: add current element of 'arr' to 'sum' and proceed to next element
                    return sumRule(arr, sum + arr[index], target, index + 1, consecutive, start);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 2, 1, 3};

        // initial call to recursive method with target = 11 (eleven)
        System.out.println(sumRule(arr, 0, 11, 0, 0, 0));

        // initial call to recursive method with target = 8
        System.out.println(sumRule(arr, 0, 8, 0, 0, 0));
    }
}
deyfvvtc

deyfvvtc4#

public static boolean isSum(int[] a, int index, int sum){

if(sum==0){
    return true;
}

if(index>=a.length-1 || sum<0){
    return false;
}

    return isSum(a,index+3,sum-a[index]-a[index+1]) || isSum(a,index+2,sum-a[index]) || isSum(a,index+1,sum);
}

public static boolean isSum(int[] a, int sum){

    return isSum(a,0,sum);

}

相关问题