第一题巧用进制解决天平称重问题。
package 第六章数学问题; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * 6.1 巧用进制解决天平称重问题 * 比如 * 控制台输入 5 * 控制台的结果为 :9-3-1 * 二进制 1028 512 256 128 64 32 16 8 4 2 1 * 5=（1 3）的三进制 逢三进一 先加一 后- 1 * 5=(2 0) 在-1=（1,2）=（2 -1）=（1 -1 -1） 9-3-1 * * @author MZFAITHDREAM * */ public class Test1 { public static void main(String[] args) { // 创建scanner对象的内容 System.out.println("请用户输入整数"); //System.out.println(Integer.toString(1000000, 3)); // 创建S Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); //将数的数字进行 翻转 final String x = Integer.toString(N, 3); // 翻转后转成字符数组，方便进行进位操作 数组的翻转 char []arr = new StringBuilder(x).reverse().toString().toCharArray(); // 容器放处理之后的0 -1 1 // 定义集合 List List<Integer> list = new ArrayList<>(); // 遍历集合中元素 for (int i = 0; i < arr.length; i++) { // 三进制 逢三进一 0 1 2 分情况说明情况 // 2 if (arr[i]=='2') { list.add(0, -1);// -1插在开头 if (i==arr.length-1) { list.add(0, 1);// 最后一个字符，进位 }else { ++arr[i+1]; // 否则，对下一个数字加1 } // 3 }else if (arr[i]==3) { list.add(0, 0); if (i==arr.length-1) { list.add(0, 1); }else { ++arr[i+1]; } }else { // arr[i] - '0' 表达的是字符转数字 list.add(0, arr[i] - '0'); // 为0或1的话，直接插入数组开头， } } // 创建String Builder字符串 StringBuilder sb = new StringBuilder(); for (int i = 0; i < list.size(); i++) { if (list.get(i)==1) { sb.append("+").append((int)Math.pow(3, list.size()-i-1)); } if (list.get(i)==-1) { sb.append("-").append((int)Math.pow(3, list.size()-i-1)); } } System.out.println(sb.substring(1)); } }
第二题经典数学问题：Nim游戏。
package 第六章数学问题; /** * 6.2 经典数学问题：Nim游戏 * @author MZFAITHDREAM * */ public class Test2 { public static void main(String[] args) { // 定义数组 int[] A= {5,4,8}; boolean res=solve(A); System.out.println("输出结果为"); System.out.println(res); } static boolean solve(int [] A) { int res=0; for (int i = 0; i < A.length; i++) { res^=A[i]; } return res !=0; } }
第三题阶梯尼姆博弈。
package 第六章数学问题; import java.util.Arrays; import java.util.Scanner; /** * 6.3 阶梯尼姆博弈 * @author MZFAITHDREAM * */ public class Test3 { /** * * @param args */ public static void main(String[] args) { System.out.println("请输入整数"); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for (int i = 0; i < a.length; i++) { a[i] = sc.nextInt(); } // 排序对数组 Arrays.sort(a); String ans = f(a); System.out.println(ans); } public static String f(int[] a) { int res = 0; if ((a.length & 1) == 0) { for (int i = 1; i < a.length; i += 2) { res ^= a[i] - a[i - 1] - 1; } } else { for (int i = 0; i < a.length; i += 2) { if (i == 0) res ^= a[i] - 1; else res ^= a[i] - a[i - 1] - 1; } } if (res == 0) return "Bob"; else return "G"; } }
第四题 欧几里得算法
package 第六章数学问题; /** * 6.5 欧几里得算法 * @author MZFAITHDREAM * *AX+BY=M */ public class Test4 { public static int gcd(int m,int n) { // 三元运算符 return n==0?m:gcd(n, m%n); } public static void main(String[] args) { // TODO Auto-generated method stub } }
第五题 欧几里得算法的扩展-裴蜀公式
package 第六章数学问题; /** * 6.6 欧几里得算法的扩展-裴蜀公式 * @author MZFAITHDREAM * */ public class Test5 { static long x; static long y; public static void main(String[] args) { try { linearEquation(4, 24, 24); System.out.println(x+" "+y); } catch (Exception e) { System.out.println("无解"); } } public static long ext_gcd(long a,long b){ if(b==0){ x = 1; y = 0; return a; } long res = ext_gcd(b,a%b); long x1 = x; x = y; y = x1 - (a/b)*y; return res; } public static long linearEquation(long a,long b,long m) throws Exception{ long d = ext_gcd(a,b); if(m%d!=0){ throw new Exception("无解"); }else{ long n = m / d; x *= n; y *= n; } return d; } public static long inverseElement(int a,int b) throws Exception{ long d = ext_gcd(a,b); x = (x % b + b) % b; //System.out.println(d+" "+x+" "+y); if(a%b==0){ throw new Exception("无解"); } return d; } public static long inverseElement2(long a, long mo) throws Exception { long d = linearEquation(a, mo, 1);//ax+mo*y=1 x = (x % mo + mo) % mo;//保证x>0 return d; } }
第七题一步之遥。
package 第六章数学问题; /** * 一步之遥 从昏迷中醒来，小明发现自己被关在X星球的废矿车里。 矿车停在平直的废弃的轨道上。 他的面前是两个按钮，分别写着“F”和“B”。 小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。 按F，会前进97米。按B会后退127米。 透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。 他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。 或许，通过多次操作F和B可以办到。 矿车上的动力已经不太足，黄色的警示灯在默默闪烁… 每次进行 F 或 B 操作都会消耗一定的能量。 小明飞快地计算，至少要多少次操作，才能把矿车准确地停在前方1米远的地方。 请填写为了达成目标，最少需要操作的次数。 注意，需要提交的是一个整数，不要填写任何无关内容（比如：解释说明等） */ import java.util.ArrayList; public class Test7 { public static void main(String[] args) { //调用方法 System.out.println(f(17,89)); } public static ArrayList<Integer> list = new ArrayList<Integer>(); public static int f(int a,int b){ if(b>200||list.contains(a)){ return Integer.MAX_VALUE; } list.add(a); if(a==1) return b; return Math.min( f(a+97,b+1) , f(a-127,b+1) ); } }
第八题：求解同余方程的正确姿势
package 第六章数学问题; import java.util.Scanner; /** * 6.8 求解同余方程的正确姿势 * 一维世界的 * @author MZFAITHDREAM * */ public class Test8 { /** * @author MZFAITHDREAM * @param args * x y m n L * ax+by=m */ public static void main(String[] args) { System.out.println("请输入五个变量"); Scanner scanner = new Scanner(System.in); int x = scanner.nextInt();//输入起始位置 A int y = scanner.nextInt();//输入起始位置 B int m = scanner.nextInt();//输入每次能跳多少A int n = scanner.nextInt();// B int l = scanner.nextInt();//输入数轴总长 int[] placex = {x}; //定义数组，记录青蛙的每次位置 int[] placey = {y}; int rest = 0; while(x != y) { x = (x + m)%l; y = (y + n)%l; rest++; //如果相遇，记录跳的次数 placex = swep(placex, x); placey = swep(placey, y); for (int i = 0; i < placey.length; i++) { for (int j = i + 1; j < placey.length; j++) {//判断是否有重合的位置 if(placex[i] == placex[j] && placey[i] == placey[j]) { System.out.println("Impossible"); return; //程序结束 } } } } System.out.println(rest); } public static int[] swep(int[] args, int x) { int[] newArrays = new int[args.length + 1]; for (int i = 0; i < args.length; i++){//不断扩充数组，将每次的新位置都加上去 newArrays[i] = args[i]; } newArrays[args.length] = x; return newArrays; } }
