[数据结构与算法]蓝桥杯算法竞赛培训(二) 汉诺塔与STL

1.递归-汉诺塔

问题描述

??我们的目的是要将整个塔移动到另一根桩柱上，每次只能移动一个圆盘，且较大的圆盘在移动过程中不能放置在较小的圆盘上面．问你具体的移动方案.

初步分析

?? 用递归的思想分析我们知道，对于最下面的盘子，如果上面的$n?1$个盘子能够全部移动到柱$C$上,我们就只需要将第n个盘子放到$B$柱上，之后对在$C$柱子上的$n?1$个盘子做相同的操作将其移动到$B$盘上，整个过程就完成了。

代码

void Move (int n , char a , char b , char c){
    if (n == 1) {
        cout << "第" << n << "号盘:" << a << "->" << b << endl;
        return ;
    }
    Move(n - 1 , a , c , b);
    cout << "第" << n << "号盘:" << a << "->" << b << endl;
    Move(n - 1 , c , b , a);
}
int main()
{
    int n;
    while (cin >> n){
        Move(n , 'A' , 'B' , 'C');
    }
    return 0;
}

复杂度分析

1.直接看输出行数，不难得出规律:$T(n)=2^n?1$,则复杂度为$O(2^n)$.结合归纳法可证明

3.令$T_n$为$n$个盘子的移动次数,那么$T_n=2?T_{n?1}+1$,边界:$T_1=1$

令$U_n=T_n+1$

则$U_n=2?T_{n?1}+1+1=2(T_{n?1}+1)=2U_n$,边界:$U_1=T_1+1=2$

所以$U_n=2^n$,所以$T_n=U_n?1=2^n?1$

进阶技巧

1.$n=1000$时的移动次数:取模

??由于该递推式增加的太快了,如果要求具体解很容易爆long long，所以一般题目会要求取模.所以这里顺便给大家展开讲一下取模的技巧

1.对加减乘除操作的取模

// 减法
int sub (int a , int b , int mod){
    return ((a - b) % mod + mod) % mod;
}
int mul (int a , int b , int mod){
    return ((a * b) % mod + mod) % mod;
}
// 除法 不能直接取模，需要求逆元.
int div (int a , int b , int mod){
    // 错误做法
    return ((a / b) % mod + mod) % mod;
}

2.大数取模

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5 +5;
const int mod = 1e9 + 7;
int main()
{
    string a;
    cin >> a;
    int b = 0;
    for (auto x : a){
        int dig = x - '0';
        b = (b * 10 + dig) % mod;
    }
    // b = a;
    cout << b << endl;
    /*
        1234 = ((((1 * 10) + 2)*10 + 3) * 10 + 4)
        对两边同时取模
        1234 % m = ((((1 * 10) + 2)*10 + 3) * 10 + 4) % m
        根据取模的分配率
        = ((((1 * 10) + 2) % m *10 + 3) % m * 10  + 4) % m
        这就是上面循环取模的原理
    */
    return 0;
}

3.阶乘取模

阶乘取模,且模数比较小

$x!\%m$

$x\in [1,10^{1000000}],m=6$

结论: 当$x>=m$时，全部等于0.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5 +5;
const int mod = 1e9 + 7;
int main()
{
    string a;
    cin >> a;
    int m = 666;
    if (a.size() > 3) {
        cout << 0 << endl;
        return 0;
    }
    stringstream b;
    b << a;
    int c;
    b >> c;
    if (c >= 666){
        cout << 0 << endl;
        return 0;
    }
    int ans = 1;
    for (int i = 1 ; i <= c ; i++){
        ans = (ans * i) % m;
    }
    cout << ans << endl;
    return 0;
}

2.$n=1000000000000$时的移动次数:快速幂

目标:求解 $2^n$
思路:
??1.先考虑求解一个这样的序列:$2^1,2^2,2^4,...$,即数列:$x_i=2^{2^{i?1}}$

?? 2.我们发现$x_i=2^{2?2^{i?2}}=2^{2^{i?2}}?2^{2^{i?2}}=x_{i?1}?x_{i?1}$

?? 3.对于$n$,将其二进制分解得到：$n=a_0{2}^0+a_1{2}^1+...+a_k{2}^k,a_i\in [0,1]$

则有:$2^n=2^{a_0?2^0+a_1{2}^1+...+a_k{2}^k}=2^{a_0?2^0}?2^{a_1?2^1}?...?2^{a_k?2^k}$

对于等式左边,直接求是$O(n)$的，但是对于等式右边,我们发现它只有$O(logn)$项的，而且这些项可以用第二个步骤的$x_i=x_{i?1}?x_{i?1}$来进行转移。

所以我们维护两个东西:$Ans=1$代表最终答案,$x$代表第二步中的序列.从低位到高位遍历$n$的二进制位，当$a_i=1$,则$Ans?=x$.否则就不乘.然后每一步转移$x=x?x$,这就是快速幂的过程,代码如下所示.

// 求a^b % mod
int ksm (int a , int b , int mod){
    int ans = 1 , x = a;
    while (b){
        if (b & 1) ans = ans * x % mod;
        b >>= 1; // 除二
        x *= x;
    }
}

3.问题变形

??把有 n 个圆盘的塔从左边的桩柱A移动到右边的桩柱B，不允许在A和B之间直接移动，求最短的移动序列．（每一次移动都必须是移动到中间的桩柱或者从中间的桩柱移出．像通常一样，较大的圆盘永远不能放在较小圆盘的上面．）

分析

$T_n=T_{n?1}+1+T_{n?1}+1+T_{n?1}=3T_{n?1}+2$
变形:
求解$T_n=3T_{n?1}+1$,$T_1=1$
推广:
求解$T_n=a{T}_{n?1}+b$

证明为何$\frac{a^k?1}{a?1}$为何总是整数?

2.STL

不定长数组vector

    #include<bits/stdc++.h> // 涵盖所有头文件,蓝桥杯允许使用
    using namespace std;
    int a[100]; // 定义了一个长度为100的数组 - 定长的
    vector<int> b; // 定义了一个长度为0的数组 - 变长的
    int main()
    {
        // vector 有哪些操作呢？
        // 1.获得大小
        cout << b.size() << endl;
        // 在数组末尾添加一个元素
        b.push_back(100);
        // 删去数组末尾一个元素
        b.pop_back();
        // 2.访问,注意下标从0开始的
        cout << b[0] << endl;
        // 访问所有
    
        // 第一种方法:
        for (int i = 0 ; i < 10 ; i++){
            // b[i]
            b.push_back(i);
        }
        // 第二种方法 C++11
        // 分号右边:是我们要循环遍历的《集合》
        // 分号左边:auto 代表我们自动获取右边集合中每个元素的类型
        // 实际运行时会把auto替换成目标类型
        // g 就是将集合中每个数取出来时所临时储存的变量
        // 什么时候用:只需要遍历每个数，而不需要知道每个数的位置时.
        for (auto g : b){
            cout << g << " ";
        }
        cout << endl;
        return 0;
    }

测试:
1.用vector重写约瑟夫环。

字符串

定义:每个元素为字符的数组.

    #include<bits/stdc++.h> // 涵盖所有头文件,蓝桥杯允许使用
    using namespace std;
    int main()
    {
        string a , b;
        cin >> a >> b;
        // 1.字符串拼接
        cout << a + b << endl;
        // 2.字符串大小比较-介绍
        // 3.反转字符串
        // 4.对字符串进行排序
        sort(a.begin() , a.end());
        // 5.对字符串进行翻转
        reverse(a.begin() , a.end());
        // 6.寻找一个子串
    	// 7.访问字符串: back []
    
        return 0;
    }

测试：
回文串判断

队列

    #include<bits/stdc++.h> // 涵盖所有头文件,蓝桥杯允许使用
    using namespace std;
    queue<int> q;
    int main()
    {
        // queue 有哪些操作呢？
        // 1.获得大小
        cout << q.size() << endl;
        // 2.在队尾添加一个元素
        q.push(10);
        // 3.访问,只能从队头(front)访问
        // 访问之前应该要先检查队列是否是空.
        cout << q.front() << endl;
        // 4.出队
        q.pop();
        return 0;
    }

栈

#include<bits/stdc++.h> // 涵盖所有头文件,蓝桥杯允许使用
using namespace std;
stack<int> s;
int main()
{
    // queue 有哪些操作呢？
    // 1.获得大小
    cout << s.size() << endl;
    // 2.访问,只能访问栈顶且访问之前应该要先检查栈是否是空.
    if (s.size() != 0)
        cout << s.top() << endl;
    // 3.在栈中添加一个元素
    s.push(10);
    // 4.弹出栈顶元素
    s.pop();
    return 0;
}

测试:
1.括号匹配
https://www.luogu.com.cn/problem/P1739 ,求和

非线性结构：红黑树(set,map)

主要考虑如何使用它

1.set

一个自带<去重机制>的有序集合.

   #include<bits/stdc++.h> // 涵盖所有头文件,蓝桥杯允许使用
    using namespace std;
    set<int> s;
    int main()
    {
        // 1.插入元素 复杂度:O(logn)
        s.insert(5);
        // 2.获取集合大小 O(1)
        cout << s.size() << endl;
        // 3.删除某个元素 O(logn)
        s.erase(5);
        // 4.查询集合最小值 O(1)
        cout << *s.begin() << endl;
        // 5.查询集合最大值 O(1)
        cout << *s.rbegin() << endl;
        // 6.查询某个值是否存在
        if (s.count(5)) //TODO:
        else
        // 遍历整个集合
        for (auto g : s){
            //
        }
        return 0;
    }
    

预习

multiset:
??一个允许重复值出现的有序集合.

map:
??它的本质就是个数组.只是下标不一定是整数.
map应用:

??1.给你一个长度为n的正整数。然后$Q$次询问,每次询问你整数$x(x\le 1e9)$出现了多少次.

??2.给你n个字符串。然后$Q$次询问,每次询问你字符串$s$出现了多少次.

??3.给你一个$n?m(n,m\le 1e5)$的矩阵。$Q(\le 1e5)$次操作.每次操作在位置$(x,y)$放置一个苹果.最后问你多少个格子有格子.

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖