🍅4.最小公倍数
为什么 1 小时有 60 分钟，而不是 100 分钟呢？这是历史上的习惯导致。
但也并非纯粹的偶然：60 是个优秀的数字，它的因子比较多。
事实上，它是 1 至 6 的每个数字的倍数。即 1,2,3,4,5,6 都是可以除尽 60。
我们希望寻找到能除尽 1 至 nn 的的每个数字的最小整数。
不要小看这个数字，它可能十分大，比如 nn = 100, 则该数为：
69720375229712477164533808935312303556800
输入一个数字 N(N<100)。
题目链接：最小公倍数https://www.lanqiao.cn/problems/292/learning/
这道题很明显考察的是大数，关于大树我在蓝桥真题三中的棋盘放麦子也讲过。用long可以算到大概N=50。但是超过50后就会爆long，所以在Java中需要使用BigInteger这个类。同时使用gcd和lcm公式（这也在蓝桥真题三中讲过）。值得一提的是，大数的考察一般是在国赛，大家视情况是否学习。当然也可以使用数组模拟加法，这也是一个非常不错的方法。
import java.math.BigInteger; import java.util.Scanner; public class 最小公倍数 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); BigInteger a=new BigInteger("1"); BigInteger b=new BigInteger("2"); BigInteger c=new BigInteger("1"); int ans=2; while(ans<=n) { a=lcm(a,b); b=b.add(c); ans++; } System.out.println(a); } static BigInteger gcd(BigInteger a,BigInteger b) { return b.toString().equals("0")?a:gcd(b,a.mod(b)); } static BigInteger lcm(BigInteger a,BigInteger b) { return a.divide(gcd(a,b)).multiply(b); } }
🍭5.最少砝码
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 NN 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
题目链接：最少砝码https://www.lanqiao.cn/problems/1461/learning/
这是2021年的省赛真题，需要运用到贪心思想。我们来分析前几步选择：
1.首先表示1这个数，我们只能用1这个砝码，此时砝码个数为1。这一步很容易思考。
2.这时考虑表示2这个数，我们难道选两个1吗？这就涉及到贪心思想了，为了尽可能表示更大的数，这时候我们选用砝码3，这样3-1=2，3+1=4。我们能同时表示1，2，3，4这四个数，此时砝码有1，3，砝码个数为2。
3.这时我们需要考虑如何表示5这个数。还是利用贪心思想，我们此时能表达的最大数是4，为了表达5且使用更大的砝码，我们选择9这个砝码，因为9-3-1=5。这时候我们能表达的最大数是多少呢？理所当然是1+3+9=13。那么问题来了？[6,12]我们能表达出来吗？
我们尝试一下：
9-3=6;
9-3+1=7;
9-1=8;
9=9;
9+1=10;
9+3-1=11;
9+3=12;
我们发现这个区间的数是可以完全表达出来的，到这我相信你也一个大胆的猜想。我们让初始砝码数count=1，初始可表达最大值ans=1。每当count++，ans的范围将会变为2*ans+1。这里我通过一个简图给大家看看：
我们只需要一直按照这个规律推算ans的值，当ans>=题目要求的N，说明此时的count就是我们的答案。
代码转换：（看着非常简洁，主要是找出规律）
import java.util.Scanner; public class 最少砝码 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); //刚开始的砝码 int count=1; //表示最大称重 int ans=1; while(ans<n) { count++; ans+=(ans+1+ans); } System.out.println(count); } }
🍒6.受伤的皇后
有一个n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：
- 任何两个皇后不在同一行。
- 任何两个皇后不在同一列。
- 如果两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 。
请问一共有多少种摆放方案。
题目链接：受伤的皇后 https://www.lanqiao.cn/problems/552/learning/
这道题目有的同学可能觉得眼熟，别眼熟了。这道题就算力扣原题，几乎一模一样，只是力扣的题目没有行号差值限制，给上链接。吃透N皇后问题，很有必要。
力扣N皇后链接： N皇后https://leetcode-cn.com/problems/n-queens/
代码转换：
import java.util.Arrays; import java.util.Scanner; public class 受伤的皇后 { static int ans=0; static char[][] arr; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); arr=new char[n][n]; for(char[] a:arr) { Arrays.fill(a,'.'); } dfs(n,0); System.out.println(ans); } static void dfs(int n,int row){ if(row==n) { ans++; return; } for(int col=0;col<n;++col) { if(check(n,row,col)) { arr[row][col]='Q'; dfs(n,row+1); arr[row][col]='.'; } } } //row是行，col是列 static boolean check(int n,int row,int col) { //判断列 for(int i=0;i<row;++i){ if(arr[i][col]=='Q') return false; } //判断45度角 int a=1; for(int i=row-1,j=col-1;a<=2&&i>=0&&j>=0;a++,j--,i--) { if(arr[i][j]=='Q') return false; } a=1; for(int i=row-1,j=col+1;a<=2&&i>=0&&j<n;a++,i--,j++) { if(arr[i][j]=='Q') return false; } return true; } }
