- 1.递归-汉诺塔
- 问题描述
- 初步分析
- 代码
- 复杂度分析
- 进阶技巧
- 1. n = 1000 n=1000 n=1000时的移动次数:取模
- 1.对加减乘除操作的取模
- 2.大数取模
- 3.阶乘取模
- 2. n = 1000000000000 n=1000000000000 n=1000000000000时的移动次数:快速幂
- 3.问题变形
- 分析
- 2.STL
- 不定长数组vector
- 字符串
- 队列
- 栈
- 非线性结构：红黑树(set,map)
- 1.set
- 预习
我们的目的是要将整个塔移动到另一根桩柱上，每次只能移动一个圆盘，且较大的圆盘在移动过程中不能放置在较小的圆盘上面．问你具体的移动方案.
初步分析用递归的思想分析我们知道，对于最下面的盘子，如果上面的 n − 1 n-1 n−1个盘子能够全部移动到柱 C C C上,我们就只需要将第n个盘子放到 B B B柱上，之后对在 C C C柱子上的 n − 1 n-1 n−1个盘子做相同的操作将其移动到 B B 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 T(n)=2^n-1 T(n)=2n−1,则复杂度为 O ( 2 n ) O(2^n) O(2n).结合归纳法可证明
3.令 T n T_n Tn为 n n n个盘子的移动次数,那么 T n = 2 ∗ T n − 1 + 1 T_n=2*T_{n-1}+1 Tn=2∗Tn−1+1,边界: T 1 = 1 T_1=1 T1=1
令 U n = T n + 1 U_n=T_n+1 Un=Tn+1
则 U n = 2 ∗ T n − 1 + 1 + 1 = 2 ( T n − 1 + 1 ) = 2 U n U_n=2*T_{n-1}+1+1=2(T_{n-1}+1)=2U_n Un=2∗Tn−1+1+1=2(Tn−1+1)=2Un,边界: U 1 = T 1 + 1 = 2 U_1=T_1+1=2 U1=T1+1=2
所以 U n = 2 n U_n=2^n Un=2n,所以 T n = U n − 1 = 2 n − 1 T_n=U_n-1=2^n-1 Tn=Un−1=2n−1
进阶技巧 1. n = 1000 n=1000 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.大数取模
#include3.阶乘取模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; return 0; }
阶乘取模,且模数比较小
x ! % m x! % m x! % m
x ∈ [ 1 , 1 0 1000000 ] , m = 6 x in[1,10^{1000000}],m=6 x∈[1,101000000],m=6
结论: 当 x > = m x >= m x>=m时，全部等于0.
#include2. n = 1000000000000 n=1000000000000 n=1000000000000时的移动次数:快速幂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
2^n
2n
思路:
1.先考虑求解一个这样的序列:
2
1
,
2
2
,
2
4
,
.
.
.
2^1,2^2,2^4,...
21,22,24,...,即数列:
x
i
=
2
2
i
−
1
x_i=2^{2^{i-1}}
xi=22i−1
2.我们发现 x i = 2 2 ∗ 2 i − 2 = 2 2 i − 2 ∗ 2 2 i − 2 = x i − 1 ∗ x i − 1 x_i=2^{2*2^{i-2}}=2^{2^{i-2}}*2^{2^{i-2}}=x_{i-1}*x_{i-1} xi=22∗2i−2=22i−2∗22i−2=xi−1∗xi−1
3.对于 n n n,将其二进制分解得到： n = a 0 2 0 + a 1 2 1 + . . . + a k 2 k , a i ∈ [ 0 , 1 ] n=a_02^{0}+a_12^{1}+...+a_k2^{k}, a_i in [0,1] n=a020+a121+...+ak2k, ai∈[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 2^{n}=2^{a_0*2^{0}+a_12^{1}+...+a_k2^{k}}=2^{a_0*2^{0}}*2^{a_1*2^{1}}*...*2^{a_k*2^{k}} 2n=2a0∗20+a121+...+ak2k=2a0∗20∗2a1∗21∗...∗2ak∗2k
对于等式左边,直接求是 O ( n ) O(n) O(n)的，但是对于等式右边,我们发现它只有 O ( l o g n ) O(logn) O(logn)项的，而且这些项可以用第二个步骤的 x i = x i − 1 ∗ x i − 1 x_i=x_{i-1}*x_{i-1} xi=xi−1∗xi−1来进行转移。
所以我们维护两个东西: A n s = 1 Ans=1 Ans=1代表最终答案, x x x代表第二步中的序列.从低位到高位遍历 n n n的二进制位，当 a i = 1 a_i =1 ai=1,则 A n s ∗ = x Ans *= x Ans∗=x.否则就不乘.然后每一步转移 x = x ∗ x x=x*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
=
3
T
n
−
1
+
2
T_n=T_{n-1}+1+T_{n-1}+1+T_{n-1}=3T_{n-1}+2
Tn=Tn−1+1+Tn−1+1+Tn−1=3Tn−1+2
变形:
求解
T
n
=
3
T
n
−
1
+
1
T_n=3T_{n-1}+1
Tn=3Tn−1+1,
T
1
=
1
T_1=1
T1=1
推广:
求解
T
n
=
a
T
n
−
1
+
b
T_n=aT_{n-1}+b
Tn=aTn−1+b
证明为何 a k − 1 a − 1 frac{a^k-1}{a-1} a−1ak−1为何总是整数?
2.STL 不定长数组vector#include// 涵盖所有头文件,蓝桥杯允许使用 using namespace std; int a[100]; // 定义了一个长度为100的数组 - 定长的 vector 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// 涵盖所有头文件,蓝桥杯允许使用 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栈// 涵盖所有头文件,蓝桥杯允许使用 using namespace std; queue 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// 涵盖所有头文件,蓝桥杯允许使用 using namespace std; stack 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; }
非线性结构：红黑树(set,map)测试:
1.括号匹配
https://www.luogu.com.cn/problem/P1739 ,求和
主要考虑如何使用它
1.set一个自带<去重机制>的有序集合.
#include预习// 涵盖所有头文件,蓝桥杯允许使用 using namespace std; set 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 Q Q次询问,每次询问你整数 x ( x ≤ 1 e 9 ) x(x leq 1e9) x(x≤1e9)出现了多少次.
2.给你n个字符串。然后 Q Q Q次询问,每次询问你字符串 s s s出现了多少次.
3.给你一个 n ∗ m ( n , m ≤ 1 e 5 ) n*m(n,m leq 1e5) n∗m(n,m≤1e5)的矩阵。 Q ( ≤ 1 e 5 ) Q(leq 1e5) Q(≤1e5)次操作.每次操作在位置 ( x , y ) (x,y) (x,y)放置一个苹果.最后问你多少个格子有格子.
