java算法经典

### Java算法经典知识点详解 #### 一、兔子繁殖问题（斐波那契数列） **题目解析：** 此题目属于经典的数学问题之一，涉及到斐波那契数列的应用。题目描述了一个理想化的兔子繁殖场景：一对兔子从第三个月开始每个月产一对新兔子，而新生的兔子在第三个月后也开始繁殖。假设所有兔子永不死亡的情况下，计算每个月的兔子总数。 **代码解析：** ```java package cn.com.flywater.FiftyAlgorthm; public class FirstRabbit { public static final int MONTH = 15; public static void main(String[] args) { long f1 = 1L, f2 = 1L; long f; for (int i = 3; i < MONTH; i++) { f = f2; f2 = f1 + f2; f1 = f; System.out.print("第" + i + "个月的兔子对数: "); System.out.println(f2); } } } ``` **关键点：** 1. **变量定义**：`f1` 和 `f2` 分别表示前两个月的兔子数量；`f` 是用于临时存储的变量。 2. **循环结构**：使用 `for` 循环来模拟月份的递增，初始月份数设为3（即兔子开始繁殖的月份）。 3. **斐波那契数列的计算**：通过 `f2 = f1 + f2` 实现了当前月份数量的计算，而 `f1 = f` 则更新前一个月的数量。 4. **输出结果**：打印每个月份的兔子数量。 **扩展知识**： - 斐波那契数列在自然界中有广泛的应用，如植物的生长规律等。 - 除了递归方法外，迭代也是计算斐波那契数列的一种常见方式，本题采用的就是迭代法。 #### 二、101-200之间的素数统计与输出 **题目解析：** 本题目要求找出101至200之间所有的素数并统计个数。素数是只能被1和自身整除的大于1的自然数。 **代码解析：** ```java package cn.com.flywater.FiftyAlgorthm; public class SecondPrimeNumber { public static int count = 0; public static void main(String[] args) { for (int i = 101; i < 200; i++) { boolean b = true; // 默认此数就是素数 for (int j = 2; j <= Math.sqrt(i); j++) { if (i % j == 0) { b = false; // 此数不是素数 break; } } if (b) { count++; System.out.print(i + " "); } } System.out.println("\n素数的个数：" + count); } } ``` **关键点：** 1. **变量定义**：`count` 用于统计素数的数量；`b` 用于标记当前数字是否为素数。 2. **内层循环**：从2遍历到当前数的平方根，这是因为如果一个数 `n` 不是素数，那么它一定有一个小于或等于 `sqrt(n)` 的因子。 3. **输出结果**：打印出所有的素数以及素数的总个数。 **扩展知识**： - 素数在密码学中有重要的应用。 - 检测大素数的方法有更高效的算法，如Miller-Rabin素性测试。 #### 三、“水仙花数”查找 **题目解析：** 本题目要求找出所有“水仙花数”，这类数的特点是个位、十位和百位上的数字立方和等于该数本身。 **代码解析：** ```java package cn.com.flywater.FiftyAlgorthm; public class ThirdNarcissusNum { static int b, bb, bbb; public static void main(String[] args) { for (int num = 101; num < 1000; num++) { ThirdNarcissusNum tnn = new ThirdNarcissusNum(); tnn.f(num); } } public void f(int m) { bbb = m / 100; bb = (m % 100) / 10; b = (m % 100) % 10; if ((bbb * bbb * bbb + bb * bb * bb + b * b * b) == m) { System.out.println(m); } } } ``` **关键点：** 1. **变量定义**：`bbb` 表示百位数，`bb` 表示十位数，`b` 表示个位数。 2. **计算逻辑**：通过除法和取余运算将三位数分解。 3. **条件判断**：如果计算结果等于原数，则打印该数。 **扩展知识**： - “水仙花数”是数学中的有趣现象之一，可以用于编程教学中培养学生对数字的敏感度。 - 类似的数字还有“阿姆斯特朗数”，其定义与“水仙花数”相似，只是不限于三位数。 #### 四、正整数分解质因数 **题目解析：** 本题目要求将一个正整数分解成其所有的质因数。 **代码解析：** ```java package cn.com.flywater.FiftyAlgorthm; import java.util.Scanner; public class FourthPrimeFactor { static int n, k = 2; public static void main(String[] args) { Scanner s = new Scanner(System.in); n = s.nextInt(); System.out.print(n + "="); FourthPrimeFactor fpf = new FourthPrimeFactor(); fpf.f(n); } public void f(int n) { while (k <= n) { if (k == n) { System.out.println(n); break; } else if (n > k && n % k == 0) { System.out.print(k + "*"); n = n / k; f(n); break; } else if (n > k && n % k != 0) { k++; } } } } ``` **关键点：** 1. **变量定义**：`n` 为待分解的正整数；`k` 为当前检查的因子。 2. **循环结构**：使用 `while` 循环进行分解过程，直到 `k` 大于 `n` 或者 `n` 已经完全分解。 3. **分解逻辑**：通过递归调用 `f(n)` 来继续分解剩余的部分。 **扩展知识**： - 质因数分解是数论的基础，广泛应用于各种数学问题中。 - 在实际应用中，优化的算法能够提高分解效率，例如使用轮询法减少不必要的检查次数。