使用打表法找规律

使用打表法找规律

作者：Grey

原文地址：

博客园：使用打表法找规律

CSDN：使用打表法找规律

打表法的使用条件

打表法适合：输入简单，输出也简单（只有一个数），可以暴力把一部分结果打印出来找规律，看下能否找到一个公式来优化代码。

买苹果问题

题目描述见：牛客：买苹果

暴力解法思路

1. 如果是奇数，直接返回 -1，因为 6 和 8 不可能组成奇数

2. 假设有 n 个苹果，最多需要n/8个 8 号袋，假设n/8=m，如果m==0，则最少需要m个 8 号袋子即可，如果m!=0，则看剩下的苹果能否被 被 6 号袋子消化，如果不能消化，则则减少一个 8 号袋子（m--），继续看剩下能否被 6 号袋搞定。

暴力解法的代码如下

    public static int minBags(int n) {
        if ((n & 1) == 1) {
            return -1;
        }

        if (n % 8 == 0) {
            // 全部可以被 8 号袋子分解
            return n / 8;
        }
        int use8 = n / 8;
        int rest = n % 8;
        while (rest != 0) {
            if (rest % 6 == 0) {
                // 分配了 8 号袋子，剩下的分配 6 号袋子，正好分配完。
                return use8 + (rest / 6);
            } else {
                // 分配了 8 号袋子，剩下的分配 6 号袋子，无法分配完，则减少一个 8 号袋子
                if (use8 > 0) {
                    use8--;
                    rest += 8;
                } else {
                    return -1;
                }
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

打印出前几项的结果观察一下

当有0个苹果的时候，最少需要：0个袋子
当有1个苹果的时候，最少需要：-1个袋子
当有2个苹果的时候，最少需要：-1个袋子
当有3个苹果的时候，最少需要：-1个袋子
当有4个苹果的时候，最少需要：-1个袋子
当有5个苹果的时候，最少需要：-1个袋子
当有6个苹果的时候，最少需要：1个袋子
当有7个苹果的时候，最少需要：-1个袋子
当有8个苹果的时候，最少需要：1个袋子
当有9个苹果的时候，最少需要：-1个袋子
当有10个苹果的时候，最少需要：-1个袋子
当有11个苹果的时候，最少需要：-1个袋子
当有12个苹果的时候，最少需要：2个袋子
当有13个苹果的时候，最少需要：-1个袋子
当有14个苹果的时候，最少需要：2个袋子
当有15个苹果的时候，最少需要：-1个袋子
当有16个苹果的时候，最少需要：2个袋子
当有17个苹果的时候，最少需要：-1个袋子
当有18个苹果的时候，最少需要：3个袋子
当有19个苹果的时候，最少需要：-1个袋子
当有20个苹果的时候，最少需要：3个袋子
当有21个苹果的时候，最少需要：-1个袋子
当有22个苹果的时候，最少需要：3个袋子
当有23个苹果的时候，最少需要：-1个袋子
当有24个苹果的时候，最少需要：3个袋子
当有25个苹果的时候，最少需要：-1个袋子
当有26个苹果的时候，最少需要：4个袋子
当有27个苹果的时候，最少需要：-1个袋子
当有28个苹果的时候，最少需要：4个袋子
当有29个苹果的时候，最少需要：-1个袋子
当有30个苹果的时候，最少需要：4个袋子
当有31个苹果的时候，最少需要：-1个袋子
当有32个苹果的时候，最少需要：4个袋子
当有33个苹果的时候，最少需要：-1个袋子
当有34个苹果的时候，最少需要：5个袋子
当有35个苹果的时候，最少需要：-1个袋子
当有36个苹果的时候，最少需要：5个袋子
当有37个苹果的时候，最少需要：-1个袋子
当有38个苹果的时候，最少需要：5个袋子
当有39个苹果的时候，最少需要：-1个袋子
...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

通过观察，可以得到如下结论

奇数个苹果，返回 -1。

n <= 5或者n==10的时候，返回 -1。

n == 6或者n == 8的时候，返回 1。

n % 8 == 0时候，全部用 8 号袋子，即n / 8; 当n%8!=0时，需要n/8+1个袋子。

代码可以优化为

    // 打表方式优化
    public static int minBags2(int n) {
        if (n <= 5 || n == 10 || (n & 1) == 1) {
            return -1;
        }
        if (n == 6 || n == 8) {
            return 1;
        }

        return n % 8 == 0 ? n / 8 : n / 8 + 1;
    }
1
2
3
4
5
6
7
8
9
10
11

牛羊吃草问题

牛客：青草游戏

暴力解法思路

在 n <= 4的情况下，我们可以通过观察得到牛羊的胜败情况

        // 0 羊胜
        // 1 牛胜
        // 2 羊胜
        // 3 牛胜
        // 4 牛胜
        if (n < 5) { // base case
            return (n == 0 || n == 2) ? "yang" : "niu";
        }
1
2
3
4
5
6
7
8

当n >= 5的情况下，我们可以暴力枚举所有情况，

当牛选择吃 1 份的时候，接下来的子过程，是谁赢，如果子过程是牛赢，说明主过程是羊获胜了。
当牛选择吃 4 份的时候，接下来的子过程，是谁赢，如果子过程是牛赢，说明主过程是羊获胜了。
…
当牛选择吃 4^x 份的时候，接下来的子过程，是谁赢，如果子过程是牛赢，说明主过程是羊获胜了。 （注：4^x <= n)。

暴力解法的代码如下：

    public static String winner(int n) {
        // 0 羊
        // 1 牛
        // 2 羊
        // 3 牛
        // 4 牛
        if (n < 5) { // base case
            return (n == 0 || n == 2) ? "yang" : "niu";
        }
        // n >= 5 时
        int base = 1; // 当前先手（牛）决定吃的草数
        // 当前是先手（牛）在选
        while (base <= n) {
            // 当前一共n份草，先手（牛）吃掉的是base份，n - base 是留给后手（羊）的草
            if (winner(n - base).equals("yang")) {
                return "niu";
            }
            if (base > (n >> 2)) { // 防止base*4之后溢出
                break;
            }
            base <<= 2;
        }
        return "yang";
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

打印出前面的一些输出

0 堆草，获胜者是：yang
1 堆草，获胜者是：niu
2 堆草，获胜者是：yang
3 堆草，获胜者是：niu
4 堆草，获胜者是：niu
5 堆草，获胜者是：yang
6 堆草，获胜者是：niu
7 堆草，获胜者是：yang
8 堆草，获胜者是：niu
9 堆草，获胜者是：niu
10 堆草，获胜者是：yang
11 堆草，获胜者是：niu
12 堆草，获胜者是：yang
13 堆草，获胜者是：niu
14 堆草，获胜者是：niu
15 堆草，获胜者是：yang
16 堆草，获胜者是：niu
17 堆草，获胜者是：yang
18 堆草，获胜者是：niu
19 堆草，获胜者是：niu
20 堆草，获胜者是：yang
21 堆草，获胜者是：niu
22 堆草，获胜者是：yang
23 堆草，获胜者是：niu
24 堆草，获胜者是：niu
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

通过观察可知，可以得到结论

n % 5 == 0 || n % 5 == 2情况下，获胜者都是羊，否则获胜者是牛。

优化后的代码如下：

    public static String winner2(int n) {
        if (n % 5 == 0 || n % 5 == 2) {
            return "yang";
        } else {
            return "niu";
        }
    }
1
2
3
4
5
6
7

判断一个数是否可以表示成若干（数量>1）连续正数和的数

题目描述如下

定义一种数：可以表示成若干（数量 > 1）连续正数和的数
比如:
5 = 2 + 3，5 就是这样的数
12 = 3 + 4 + 5，12 就是这样的数
1不是这样的数，因为要求数量大于1个、连续正数和
2 = 1 + 1，2 也不是，因为等号右边不是连续正数
给定一个参数 N，返回是不是可以表示成若干连续正数和的数

按照题目的描述，我们可以把暴力解法写出来，就是枚举 num 是否 可以被
1 + 2 + ... + n
2 + 3 + ... + n
3 + 4 + ... + n
…
上述任何一个式子分解。

暴力解法的代码如下

    public static boolean isMSum1(int num) {
        if (num <= 2) {
            return false;
        }
        int sum = 1;
        for (; sum < num; sum++) {
            int o = sum;
            int i = sum + 1;
            sum += i;
            if (sum > num) {
                return false;
            }
            while (sum < num) {
                i++;
                sum += i;
            }
            if (sum == num) {
                return true;
            }
            sum = o;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

打印出前面若干项的结果

1 : false
2 : false
3 : true
4 : false
5 : true
6 : true
7 : true
8 : false
9 : true
10 : true
11 : true
12 : true
13 : true
14 : true
15 : true
16 : false
17 : true
18 : true
19 : true
20 : true
21 : true
22 : true
23 : true
24 : true
25 : true
26 : true
27 : true
28 : true
29 : true
30 : true
31 : true
32 : false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

观察后发现

num == 1 || num == 2时，为 false。

如果一个数是 2 的某次方，则返回 false，否则则返回 true。

如何判断一个数是不是 2 的某次方呢？

有如下三种方法

num == (num & (-num))
num == (num & (~num + 1))
(n & (num - 1)) == 0
1
2
3

所以，优化后的代码如下

    public static boolean isMSum2(int num) {
        if (num == 1 || num == 2) {
            return false;
        }
        return ((num - 1) & num) != 0;
    }
1
2
3
4
5
6

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云