陈留阳
0%

《算法很美》—— 查找与排序（上）

发表于 更新于 分类于

第二章的内容相对第一章来说常规了一些，或者更应该说第一章的内容很是惊艳，毕竟位运算接触的少。而第二章分析算法的复杂度，排序算法的实现，二分查找这些就中规中矩了许多，在意的并不多。但是在例题里有几道感觉特别有意思的题目，思路比较巧，因此决定记下来。

设计一个高效的 pow 函数

题目

设计一个高效的求\(a\)的\(n\)次幂的算法，\(n\)为正整数

思路

这个题最朴素的思路自然是连续乘法，让 a 循环乘 n 次，即：

1
2
3
4
5
6
7
8
9
int pow(int a, int n)
{
    int ret = 1;
    for (int i = 0; i < n; i++)
    {
        ret *= a;
    }
    return ret;
}

教学过程中老师又提出了一种解法。

考虑到如果一个数和自己相乘，结果再和自己相乘，结果再乘，这样每次计算时所得的计算结果就会是原数的1,2,4,8,16,32次方，与连续乘的1,2,3,4,5相比快很多。当然，因为不连续的问题，会导致循环时有可能会跳过期望的 n，则可以将不足 n 的部分拿出单独按照同样的方法求。

任何一个十进制整数都可以被写成是二进制数，因此上述解法一定可以将 n 分解为若干个 2 的次幂相加，因此，该解法是正确无误的：

1
2
3
4
5
6
7
8
9
10
11
12
13
int pow(int a,int n)
{
    if(n==0)
        return 1;
    int res = a;
    int ex = 1;
    while((ex<<1)<=n)
    {
        res = res * res;
        ex <<= 1;
    }
    return res * pow(a, n - ex);
}

只不过，看着这个解法，我总觉得还是有点不对劲。如果把 n 看作是 100，那么该解法相当于是分别求了\(n = 64\)，\(n = 32\)，\(n = 4\)时的情况，并将它们相乘，结果正确无误。

可是，在计算\(n = 64\)时，实际上是算过了\(n = 32\)以及\(n = 4\)的值，只是没有将它们用上而已，如此一来，这个解法应该还有继续优化的空间。

那么，如果可以将这个\(n\)分解开为若干个\(2\)的次幂和的形式，然后在相乘的过程中遇见了这些次幂的情况就乘进结果中，最后再返回，那会不会就让整个过程更快了？

那么，如何将一个\(n\)拆分成若干个\(2\)的次幂和的形式并将其记录下来呢？

实际上，这一步计算机已经帮我们做好了。任意一个正整数数都可以被写成是二进制的形式，而计算机再内部储存数的时候采取的就是二进制。而二进制的每一位都有对应的权值，这些位上的数与它们的权值相乘求和就会得到所表达的二进制数。

也就是说，计算机在内部的二进制表示形式实际上就是我们希望的拆分并记录下的若干个\(2\)的次幂和的形式。

那么，接下来借用一下 位运算的技巧，就可以写出解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
int pow(int a, int n)
{
    int ret = 1;
    for (int power = a; n; n >>= 1)
    {
        if (n & 1)
        {
            ret *= power;
        }
        power *= power;
    }
    return ret;
}

完美！(•̀ᴗ•́)و ̑̑

走楼梯

题目

小明刚刚看完电影《第K级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是\(K\)级!

站在台阶前，他突然又想着一个问题：

如果我每一步只能迈上\(1\)个或\(2\)个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，

也就是说一共要走偶数步。那么，上完\(K\)级台阶，有多少种不同的上法呢？

请你利用计算机的优势，帮助小明寻找答案。

思路

这道题有点斐波那契数列的感觉，但是加了一个条件，即考虑左右交替。

那么首先最朴素的想法就来了，和斐波那契数列一样，最简单的想法，第\(n\)阶偶数的方法数是第\(n-1\)阶奇数方法数与第\(n-2\)阶奇数的方法数之和，奇数同理，那么自然就有了如下的递归解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;
int dfs(int k, int num, int ou)
{
    if (k == 0 && (ou % 2 == 0))
    {
        num++;
        return num;
    }
    else if (k < 0 || (k == 0 && ou % 2))
        return num;
    num = dfs(k - 1, num, ou + 1);
    num = dfs(k - 2, num, ou + 1);
    return num;
}
int main()
{
    int a;
    cin >> a;
    cout << dfs(a, 0, 0) << endl;
    return 0;
}

稍加改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
int dfs(int k, bool even)
{
    if ((k == 1 && even) || k == 2)
    {
        return 1;
    }
    else if (k < 1 || (k == 1 && !even))
    {
        return 0;
    }
    return dfs(k - 1, !even) + dfs(k - 2, !even);
}
int main()
{
    int a;
    cin >> a;
    cout << dfs(a, false) << endl;
}

欸，好像有点眼熟(○´･д･)ﾉ

如果把

return dfs(k - 1, !even) + dfs(k - 2, !even)

单独拿出来的话，不就是

dfs(k,even)=dfs(k - 1, !even) + dfs(k - 2, !even)

了嘛，如果再加上初始条件和记录的数组的话。

all[i][j] = all[i - 1][!j] + all[i - 2][!j]

和斐波那契数列好像哦

Fib[i] = Fib[i-1] + Fib[i - 2]

所以这道题实际上是动态规划🤣，状态转移方程就是之前写下的样子。

改为动态规划后的代码如下：

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
#include <iostream>

using namespace std;

const int maxn = 25;
long long all[maxn][2];

const int Left = 0, Right = 1;
const int Impossible = -1;

int main()
{
    all[1][Left] = 1;
    all[2][Left] = 1;
    all[1][Right] = Impossible;
    all[2][Right] = 1;
    for (int i = 3; i < maxn; i++)
    {
        for (int j = Left; j <= Right; j++)
        {
            if (all[i - 1][!j] != Impossible)
            {
                all[i][j] += all[i - 1][!j];
            }
            if (all[i - 2][!j] != Impossible)
            {
                all[i][j] += all[i - 2][!j];
            }
            if (!all[i][j])
            {
                all[i][j] = Impossible;
            }
        }
    }
    int k;
    cin >> k;
    cout << all[k][Right] << endl;
    return 0;
}

好吧，这是我第一次看出来是动态规划并且推出状态转移方程的题，所以拿出来纪念下(｡◕ˇ∀ˇ◕）。

就写这么多吧，剩下的内容感觉比较简单就不写了。😁