萌新卷妹带你从头复习JavaSE-方法2
萌新卷妹带你从头复习JavaSE-方法2
🍦3.1斐波拉契数列
斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。 特别指出：第0项是0，第1项是第一个1。这个数列从第3项开始，每一项都等于前两项之和。
🍁斐波拉契数列的通项公式为：F(N) = F(N - 1) + F(N -2) 🍁起始条件：N = 0，F(0) = 0; N = 1，F(1) = 1; 🍁递归实现：
public class testBlog {
public static int fib1(int n) {
if (n == 0 || n == 1) {
return n;
}
return fib1(n - 1) + fib1(n - 2);
}
public static void main(String[] args) {
//斐波拉契数列
for (int i = 0; i < 13; i++) {
System.out.print(fib1(i) + " ");
}
}
}
但是使用递归实现斐波拉契数列，求后面的项会变得越来越慢，因为会进行大量重复的项的计算。 🍁推荐使用迭代的方法实现：
public class testBlog {
//fib1递归，fib2迭代
public static int fib1(int n) {
if (n == 0 || n == 1) {
return n;
}
return fib1(n - 1) + fib1(n - 2);
}
public static int fib2(int n) {
if (n == 0 || n == 1) {
return n;
}
int f0 = 0;
int f1 = 1;
int fn = 0;
while (n - 1 != 0) {
fn = f0 + f1;
f0 = f1;
f1 = fn;
n--;
}
return fn;
}
public static void main(String[] args) {
//斐波拉契数列
for (int i = 0; i < 13; i++) {
System.out.print(fib1(i) + " ");//递归结果
}
System.out.println();
for (int i = 0; i < 13; i++) {
System.out.print(fib2(i) + " ");//迭代结果
}
}
}
🍦3.2青蛙跳台阶问题
🍧3.2.1题目描述及思路
🍁题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？ 解题思路 1.当n=1的时，很明显青蛙只有一种跳法。 2.当n=2时，青蛙有两种选择，一是每次跳1级台阶，跳两次，二是直接跳两级台阶，一步到位。所以，一共有两种跳法。 3.当n>2时，我们不妨把上n级台阶的跳法记为一个函数f(n)，青蛙在第一次跳的时候有两个选择，即跳一级台阶或跳两级台阶。当青蛙选择第一次跳一级台阶时，跳完后还剩n-1级台阶，在此情况下，跳法的数目为f(n-1)；当青蛙选择第一次跳两级台阶时，跳完后还剩n-2级台阶，在此情况下，跳法数目为f(n-2)。所以，我们可以推出青蛙跳n级台阶的跳法总数为f(n)=f(n-1)+f(n-2)。
到这里我们就能使用求斐波拉契数列的方法来求青蛙跳n级台阶的跳法。
🍁若把条件修改成一次可以跳一级，也可以跳2级...也可以跳上n级呢？ 解题思路 尽管条件改成每次跳的台阶级数不受限，但是换汤不换药，思考的方法是一样的。 1.当n=1或n=2时，青蛙跳台阶跳法次数和没修改条件时是一样的，n=1有一种跳法，n=2有两种跳法。 2.当n>2时，同理我们将青蛙跳n级台阶时的跳法记成函数f(n)。但是青蛙在第一次的选择不仅仅是跳1级和跳2级，它还可以选择跳3,4,5,...,n级。所以青蛙跳一次后还会剩n-1，n-2，n-3，...，2, 1, 0级台阶。 此时，f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(2)+f(1)+1 同理，f(n-1)=f(n-2)+f(n-3)+f(n-4)+...+f(2)+f(1)+1 合并上面两个式子得，f(n)=2*f(n-1) 3.根据2的推论得出一个等比数列，由此我们还可以进一步推导： 🍁推导1：f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(2)+f(1)+1 =1+f(1)+f(2)+...+f(n-2)+f(n-1) =1+2^0^*f(1)+2^1^*f(1)+...+2^n-3^*f(1)+2^n-2^*f(1) =1+(2^0^+2^1^+2^2^+...+2^n-3^+2^n-2^) =1+(2^n-1^-1) =2^n-1^ f(1) = 1，f(2) = 2，f(n)为公比的2的等比数列（n>2） 🍁推导2：f(1) = 2^0^, f(2) = 2^1^, f(3) = 2^2^......, f(n-1) = 2^n-2^, f(n) = 2^n-1^
🍧3.2.2代码演示
public class testBlog {
//frog1递归，frog2迭代
public static int frog1(int n) {
if (n <= 2) {
return n;
}
return frog1(n - 1) + frog1(n - 2);
}
public static int frog2(int n) {
if (n == 1 || n == 2) {
return n;
}
int f1 = 1;
int f2 = 2;
int fn = 0;
while (n - 2 != 0) {
fn = f1 + f2;
f1 = f2;
f2 = fn;
n--;
}
return fn;
}
public static int frogPlus1(int n) {
if (n == 1) {
return n;
}
return 2 * frogPlus1(n - 1);
}
public static int frogPlus2(int n) {
if (n == 1) {
return n;
}
int f1 = 1;
int fn = 0;
while (n - 1 != 0) {
fn = 2 * f1;
f1 = fn;
n--;
}
return fn;
}
public static int frogPlus3(int n) {
return (int)Math.pow(2, n - 1);
}
public static void main(String[] args) {
//青蛙跳台阶
for (int i = 1; i < 13; i++) {
System.out.print(frog1(i) + " ");//青蛙跳台阶递归结果
}
System.out.println();
for (int i = 1; i < 13; i++) {
System.out.print(frog2(i) + " ");//青蛙跳台阶迭代结果
}
System.out.println();
for (int i = 1; i < 13; i++) {
System.out.print(frogPlus1(i) + " ");//青蛙跳台阶变式递归结果
}
System.out.println();
for (int i = 1; i < 13; i++) {
System.out.print(frogPlus2(i) + " ");//青蛙跳台阶变式迭代结果
}
System.out.println();
for (int i = 1; i < 13; i++) {
System.out.print(frogPlus3(i) + " ");//青蛙跳台阶变式结论结果
}
}
}
🍦3.3汉诺塔问题
🍧3.3.1问题描述及思路
Hanoi（汉诺）塔问题。古代有一个梵塔，塔内有3个座A,B,C。开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个先知想把这64个盘子从A座移到C座，但规定每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座。你能帮这位先知实现他的想法吗？要求编程序输出移动盘子的步骤。 🍁解题思路: 这位先知会这样想: 假如有另外一位先知能有办法将上面63个盘子从A座移到B座。那么，问题就解决了。此时先知只须这样做: ① 联系他的好朋友第2个先知将63个盘子从A座移到B座； ② 自己将1个盘子（最底下的、最大的盘子）从A座移到C座； ③ 再让第2个先知将63个盘子从B座移到C座。 第2个先知又想: 如果有人能将62个盘子从一个座移到另一座，我就能将63个盘子从A座移到B座，他是这样做的: ① 联系他的好朋友第3个先知将62个盘子从A座移到C座； ② 自己将1个盘子从A座移到B座； ③ 再让第3个先知将62个盘子从C座移到B座。 …… 以此类推 为了便于理解，我们将盘子数量降低到3个，所以首先分析将A座上3个盘子移到C座上的过程：
① 将A座上2个盘子移到B座上（借助C座）。
② 将A座上1个盘子移到C座上。
③ 将B座上2个盘子移到C座上（借助A座）。
其中第②步可以直接实现。第①步又可用递归方法分解为:
- 将A座上1个盘子从A座移到C座；
- 将A座上1个盘子从A座移到B座；
- 将C座上1个盘子从C座移到B座。
第③步可以分解为:
- 将B座上1个盘子从B座移到A座上；
- 将B座上1个盘子从B座移到C座上；
- 将A座上1个盘子从A座移到C座上。
将以上综合起来，可得到移动3个盘子的步骤为: A→C，A→B，C→B，A→C，B→A，B→C，A→C。 共经历7步。由此可推出: 移动n个盘子要经历(2^n^-1)步。
🍧3.3.2代码演示
🍁由上面的分析可知: 将n个盘子从A座移到C座可以分解为以下3个步骤: ① 将A座上n－1个盘借助C座先移到B座上； ② 把A座上剩下的一个盘移到C座上； ③ 将n－1个盘从B座借助于A座移到C座上。
🍁可以把上面3个步骤分成两类操作: ① 将n－1个盘从一个座移到另一个座上（n＞1）。这就是先知让他的朋友第2个先知做的工作，它是一个递归的过程，即先知将任务层层下放，直到第64个先知为止。 ——hanoi函数 ② 将1个盘子从一个座上移到另一座上。这是先知自己做的工作。 ——move函数
public class testBlog {
public static void move(char m, char n) {
System.out.println(m + "->" + n);
}
public static void hanoi(int num, char a, char b, char c) {
if (num == 1) {
move(a, c);
return;
}
hanoi(num - 1, a, c, b);
move(a, c);
hanoi(num - 1, b, a, c);
}
public static void main(String[] args) {
//Hanoi（汉诺）塔问题。古代有一个梵塔，塔内有3个座A,B,C。
//开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上。
//有一个先知想把这64个盘子从A座移到C座，但规定每次只允许移动一个盘,
//且在移动过程中在3个座上都始终保持大盘在下，小盘在上。
//在移动过程中可以利用B座。你能帮这位先知实现他的想法吗？
//要求编程序输出移动盘子的步骤。
int num = 3;
hanoi(3,'A', 'B', 'C');
}
}
看看3个盘子的汉诺塔程序是怎么移动的：
与我们推演出来的移动顺序一致！
- 点赞
- 收藏
- 关注作者
评论（0）