Java-Kettle 问题(由裴树定理解决)
最编程
2024-07-18 22:19:28
...
水壶问题
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水?如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升 水。
裴蜀定理(或贝祖定理):
若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。
边界问题的处理:
当x=0或者y=0时,判断y==z或x==y;
当z=0时,直接返回true;
当x+y<z的时候直接返回False。
测试示例:
示例1:
输入: x = 3, y = 5, z = 4
输出: True
示例2:
输入: x = 2, y = 6, z = 5
输出: False
import java.util.*;
public class Kettle {
public static void main(String[] args) {
System.out.println("请输入两个水壶的容量以及需要求的水的升数:");
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
System.out.println(canMeasureWater(a,b,c));;
}
//求最大公约数
public static int euclid(int inte1, int inte2) {
int surplus ;
surplus = inte1%inte2;
while(surplus != 0) {
inte1 = inte2;
inte2 = surplus ;
surplus = inte1%inte2;
}
return inte2;
}
public static boolean canMeasureWater(int x, int y, int z){
// 首先判断约束条件
if(x == 0) return y == z;
if(y == 0) return x == z;
if(z == 0) return true;
if(x+y < z) return false;
int num = euclid(x,y);
if((z%num)!=0) return false;
else return true;
}
}
初学者一枚,如有问题欢迎指正~
上一篇: 蓝桥杯包子凑数(完整的背包、裴树定理、塞瓦维斯特定理)
下一篇: 贝舒定理(贝祖定理)及其证明
推荐阅读
-
Java-Kettle 问题(由裴树定理解决)
-
动态规划算法的两种经典解决方式:最优子结构和DP数组的使用解析-动态规划算法问题 什么叫作最优子结构? 和动态规划有什么关系? 为什么动态规划遍历DP数组的方式有正着遍历,有倒着遍历,有斜着遍历? 最优子结构 最优子结构是某些问题的一种特定的性质,并不是动态规划问题所特有的. 很多问题都具有最优子结构,但是其中大部分不具有重叠子问题,所以不会归为动态规划系列的问题 最优子结构: 可以从子问题的最优结果推导出更大规模问题的最优结果 子问题之间必须相互独立 通过改造问题来优化由于子问题之间不独立而导致的最优子结构失效的情况: 问题: 假设学校有10个班,已知每个班的最高分与最低分差值的最大分数差,需要计算全校学生中的最大分数差 分析: 这样的问题就无法通过这10个班的最大分数差来推导出来,因为这10个班的最大分数差不一定就包含全校学生的最大分数差.比如全校的最大分数差可能是由8班的最高分和6班的最低分的分数差而得.这样就导致子问题之间不是互相独立的 改造问题: 直接进行问题改造 int result = 0; for (Student a : school) { for (Student b : school) { if (a is b) { continue; } result = max(result, |a.score - b.score|) } } return result; 改造问题就是将问题等价转化: 最大分数差就等价于最高分数与最低分数的差 那么就是要求最高和最低分数 求最高分数是具备最优子结构的,求最低分数也是具有最优子结构的 这样就样一个不具备最优子结构的问题转化为具备最优子结构的子问题 借助最优子结构解决最值问题,再解决最大分数差问题 题目: 求一棵二叉树的最大值,假设节点中的值都为非负数 int maxVal(TreeNode root) { if (root == null) { return -1; } int left = maxVal(root.left); int right = maxVal(root.right); return max(root.val, left, right); }