java经典算法-day2

web小门神 lv.1

发布时间：2022-11-26 18:37:40 379

一、前言

正值金九银十好时节，又到了刷算法题日。xdm，有空的大家一起来呀，空余时间，地铁时间等随时随地皆可，你可以不用实操，你只需要看题思考，完后有空coding就好呀。接下来我要开启我的刷题之旅啦，喜欢的小伙伴欢迎点赞关注哦。

二、题目描述：

题目1：

打印九九乘法表。

题目2：

古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总对数为多少？

三、思路分析：

题1：打印九九乘法表。

首先我们要找九九乘法表的输出进行找规律，九九乘法表的第一行，输出1*1 = 1，就一列；
然后第二行是输出两列，以此类推，我们就固定了第一层循环就只需要i从1-9，总共就九行；
然后就是控制第二层嵌套，很明显，跟着第一层的i，i是几，列数就是几。
所以，很明显第二层j也是从1开始，j最大只能等于i，这样就能保证呈下走楼梯状。所以总结一下，就是一共需要两层循环。
然后就是进行里层不换行打印输出，但是进行新的外一轮循环，根据九九乘法表，是要换行，所以你就在你内层循环外再加上一句换行语句即可。
平常直接打印对不齐，我们只需要在内层打印语句的末端，加上" \t"(\t相当于tab),这样它就可以列对齐了。

题2：古典问题：假如兔子都不死，问每个月的兔子总对数为多少？

首先，看到这题，我们应该要有个思维，那就是找规律，可以自己先尝试枚举几个月出来，看看能否成总数上找到有何规律。

我现来，枚举看看，每个月兔子总对数分别如下。

第1个月兔子总对数为：1
第2个月兔子总对数为：1
第3个月兔子总对数为：2
第4个月兔子总对数为：3
第5个月兔子总对数为：5
第6个月兔子总对数为：8
第7个月兔子总对数为：13
第8个月兔子总对数为：21
第9个月兔子总对数为：34
...

仔细一看这每个月的兔子对数，这不就是典型的斐波那契数列问题啊[1,1,2,3,5,8,13,21,34...]，很明显就是符合斐波那契数列。针对该问题，满足函数f(x+2) = f(x+1)+f(x)。其中x表示当前月份，x+2表示当前月份的第二个月份，所以分析可得，直接一套递归带走。

四、算法实现：

题1AC代码：

/**
 * 输出九九乘法表
 */
for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= i; j++) {
             System.out.print(i + "*" + j + "=" + i*j+ "\t");
        }
          System.out.println();
    }

实际控制台输出：

1*1=1   
2*1=2   2*2=4   
3*1=3   3*2=6   3*3=9   
4*1=4   4*2=8   4*3=12   4*4=16   
5*1=5   5*2=10   5*3=15   5*4=20   5*5=25   
6*1=6   6*2=12   6*3=18   6*4=24   6*5=30   6*6=36   
7*1=7   7*2=14   7*3=21   7*4=28   7*5=35   7*6=42   7*7=49   
8*1=8   8*2=16   8*3=24   8*4=32   8*5=40   8*6=48   8*7=56   8*8=64   
9*1=9   9*2=18   9*3=27   9*4=36   9*5=45   9*6=54   9*7=63   9*8=72   9*9=81

题2AC代码：

无非就是实现这个函数:f(x) = f(x-1)+f(x-2)【其中x>=3】;

/**
 * 斐波那契函数
 */
public static int fbnq(int month) {
    int sum = 0;
    if (0 < month && month < 3) {
        sum = 1;
    }
    if (month >= 3) {
        sum = fbnq(month - 1) + fbnq(month - 2);
    }
    return sum;
}

需要注意的是，由于第一个月和第二个月兔子对数都不变，所以需要单独提前告知sum的值，枚举month=1与month=2的值即可，往后就直接自我递归调用计算。