写一个groups.java 的class 有两个methods:
第一个method是这样的：
1. A recursive and static method groupNoAdj(int start, int[] nums, int target)
that given an array of integers nums, return true if is it possible to choose a group of
some of the integers, such that the group sums to the given target target with this
additional constraint: If a value in the array is chosen to be in the group, the value
immediately following it in the array must not be chosen. (No loops needed.) Notice
that the method has an addition parameter start that you can use to decompose the
original problem into subproblems and it denotes the starting point of the part of the
array you want to analyze.
给了两个例子：
a. groupNoAdj(0,{2,5,10,4},12) return true, 因为{2,10}的总数是12， 并且2,10不相邻。
b. groupNoAdj(0,{2,5,10,4},7) return false, 因为{2,5}的总是虽然是7，但是这两个数在数组中是相邻的
第二个method是：
2. A main method that asks rst for the target value, second for the numbers of elements
in the array, and nally it reads the elements typed by the user on the terminal. When
you have the inputs parameters calls the groupNoAdj method and print out the result.
老师给了个提示：
看初始的数组为{2,5,10,4} 并且这时target = 12. 这可以解决两个问题， 一：{5,10,4}， 这时target = 12; 二， {10,4） 这时target 10= 12-2 使用参数“start” to identify the part of the arrary on where we are working on. 所以初始设置 start =0。
最后出来的程序应该像这样：
Enter the target: 12
Enter the num of elements in the array: 4
Enter the elements:
2
5
10
4
We can make a group that sums to: 12
希望大家给点建议，关于recursive method实在是没有头绪啊。谢谢！
------解决方案--------------------------------------------------------
- Java code
import java.util.*;public class Test{ public static boolean groupNoAdj(int start, int[] nums, int target) { if (start >= nums.length) //当起始位置超过数组个数时，停止递归 { return false; } if (groupNoAdj(start + 1, nums, target)) //递归调用 { return true; } for (int i = start + 2; i < nums.length; i++) //因为不能取当前数的下一个数，所以要加2 { if (nums[start] + nums[i] == target) //只要有一组满足条件就返回true { return true; } } return false; //否则返回false } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("Enter the target: "); int target = scanner.nextInt(); System.out.print("Enter the num of elements in the array: "); int[] nums = new int[scanner.nextInt()]; System.out.println("Enter the elements: "); for (int i = 0; i < nums.length; i++) { nums[i] = scanner.nextInt(); } if (groupNoAdj(0, nums, target)) { System.out.println("We can make a group that sums to: " + target); } else { System.out.println("We can not make a group that sums to: " + target); } }}
------解决方案--------------------------------------------------------
刚才忽视了一个数字不能够连续的条件。
贴上更新的代码。
- Java code
public boolean groupNoAdj(int start, int[] nums, int target) { if(start >= nums.length) return false; if(nums[start] == target){ return true; } else if (nums[start] < target) { if(groupNoAdj(start + 2,nums,target-nums[start])) //start的数字小于需要的，尝试将这个数字添加进，故要跳2位 return true; else return groupNoAdj(start + 1,nums,target); //start的数字小于需要的，由于添加后，无法获得正确的序列，故不添加这个数字，则后一个数字可用 }else{ return groupNoAdj(start + 1,nums,target); } }