数的划分javadfs

### 关于Java中使用DFS进行数字划分 #### 使用DFS解决数字划分问题的核心概念 在处理涉及组合优化的问题时，深度优先搜索（DFS）是一种常用的方法。对于特定的数字划分问题，比如将一组数字划分为若干个满足一定条件的小集合，可以采用DFS来遍历所有可能的情况并找到符合条件的结果。 当涉及到具体的应用场景如题目描述中的情况——即把`1,2,...,n`这n个自然数分成两部分使得这两部分具有相同的和、平方和以及立方和时，可以通过构建一棵决策树来进行探索[^4]。每一步选择是否将当前考察到的元素加入第一个子集中还是第二个子集中，并通过递归的方式继续考虑下一个位置上的元素直到完成整个序列的选择过程为止。 为了提高效率，在实际编码过程中还需要引入一些剪枝策略以减少不必要的计算量： - **提前终止**：一旦发现某一分支无法达到目标，则立即停止对该分支更深层次节点的访问； - **记忆化存储**：记录已经遇到过的状态及其对应结果，避免重复运算； 下面给出一段基于上述原理编写的用于解答此类问题的Java代码片段作为参考： ```java import java.util.*; public class NumberPartition { private static boolean[] used; private static int sumA = 0; // 子集 A 的元素之和 private static long squareSumA = 0L; // 子集 A 的元素平方之后再求和 private static long cubeSumA = 0L; // 子集 A 的元素三次方之后再求和 public static void main(String[] args){ Scanner scanner=new Scanner(System.in); List<Integer> numbers= new ArrayList<>(); for(int i=1;i<=16;i++){ numbers.add(i); } used = new boolean[numbers.size()]; dfs(numbers, 0); System.out.println("No solution found."); } private static void dfs(List<Integer> nums,int index){ if(index==nums.size()){ if(check(nums)){ printResult(); System.exit(0); // 找到了合适的分割方案就退出程序 }else{ return ; } } // 尝试不放入任何集合 dfs(nums,index+1); // 放入集合A used[index]=true; Integer num = nums.get(index); sumA +=num; squareSumA+=Math.pow(num,2); cubeSumA+=Math.pow(num,3); dfs(nums,index+1); // 回溯操作 sumA -=num; squareSumA-=Math.pow(num,2); cubeSumA-=Math.pow(num,3); used[index]=false; } /** * 检查目前形成的两个子集是否满足三个约束条件 */ private static boolean check(List<Integer> nums){ double halfSum=(double)(sumOfNums(nums)/2d); double halfSquareSum=(squareSumOfNums(nums))/2d; double halfCubeSum=(cubeSumOfNums(nums))/2d; return Math.abs(sumA-halfSum)<1e-9 && Math.abs(squareSumA-halfSquareSum)<1e-9 && Math.abs(cubeSumA-halfCubeSum)<1e-9; } /** * 计算列表内全部数值加起来后的总和 */ private static int sumOfNums(List<Integer> list){ return (int)list.stream().mapToInt(Integer::intValue).sum(); } /** * 计算列表内全部数值各自取平方后再累加得到的结果 */ private static double squareSumOfNums(List<Integer> list){ return list.stream().mapToDouble(x->Math.pow(x.intValue(),2)).sum(); } /** * 计算列表内全部数值各自取立方后再累加得到的结果 */ private static double cubeSumOfNums(List<Integer> list){ return list.stream().mapToDouble(x->Math.pow(x.intValue(),3)).sum(); } /** * 输出最终结果 */ private static void printResult(){ StringBuilder sbA =new StringBuilder("["); StringBuilder sbB =new StringBuilder("["); for(int i=0 ;i<used.length ;++i){ if(!used[i]){ sbA.append((i+1)+", "); }else{ sbB.append((i+1)+", "); } } String resultA=sbA.substring(0,sbA.length()-2)+"]"; String resultB=sbB.substring(0,sbB.length()-2)+"]"; System.out.printf("Set A:%s\nSet B:%s\n",resultA,resultB); } } ``` 这段代码实现了基本框架下的DFS逻辑，其中包含了必要的辅助函数用来验证所选路径是否符合要求。此外还加入了简单的输入读取功能以便测试不同的数据实例。需要注意的是这里假设输入范围固定为前16个正整数，因此可以根据实际情况调整这部分内容。