理论基础
数学归纳法
- 验证P(1)成立
- 证明如果P(k)是正确的，那么P(k+1)也成立
- 联合1，2；证明由P(1)->p(n)成立
递归函数设计的三个重要部分
- 给递归函数应该明确的语义
- 实现边界条件时的程序逻辑
- 假设递归函数调用返回结果是正确的，实现本层函数逻辑
阶乘函数设计exp
1
2
3
4
5
6
7
8
| #include<bits/stdc++.h>
int f(int n){
if(n==1){
return 1;
}
return n*f(n-1);
}
|
例题
HZOJ 184路飞吃桃
路飞买了一堆桃子不知道个数，第一天吃了一半的桃子，还不过瘾，又多吃了一个。以后他每天吃剩下的桃子的一半还多一个，到n天只剩下一个桃子了。路飞想知道一开始买了多少桃子。
太简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<bits/stdc++.h>
int f(int n){
if(n==1){
return 1;
}
return 2*(f(n-1)+1);
}
int main(){
int n;
scanf("%d", &n);
printf("%d\n", f(n));
}
|
HZOJ 186弹簧板
有一个小球掉落在一串连续的弹簧板上，小球落到某一个弹簧板后，会被弹到某一个地点，直到小球被弹到弹簧板以外的地方。
假设有 n 个连续的弹簧板，每个弹簧板占一个单位距离，a[i] 代表代表第 i 个弹簧板会把小球向前弹 a[i] 个距离。比如位置 1 的弹簧能让小球前进 2 个距离到达位置 3 。如果小球落到某个弹簧板后，经过一系列弹跳会被弹出弹簧板，那么小球就能从这个弹簧板弹出来。
现在小球掉到了1 号弹簧板上面，那么这个小球会被弹起多少次，才会弹出弹簧板。 1号弹簧板也算一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
int f(int n,int a[],int i){
if(i>=n){
return 0;
}
return f(n,a,i+a[i])+1;
}
int main(){
int n;
scanf("%d", &n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d", &a[i]);
}
printf("%d\n", f(n,a,0));
return 0;
}
|
HZOJ 235递归实现指数型枚举
从 1−n 这 n 个整数中随机选取任意多个，每种方案里的数从小到大排列，按字典序输出所有可能的选择方案。
思想就是全排列然后分别取段枚举
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
| #include<bits/stdc++.h>
int a[10];
void print(int n){
for(int i=0;i<n;i++){
if(i){
printf(" ");
}
printf("%d", a[i]);
}
printf("\n");
}
void fk(int i,int j,int n){
if(j>n){
return ;
}
for(int k=j;k<=n;k++){
a[i]=k;
print(i+1);
fk(i+1,k+1,n);
}
return ;
}
int main(){
int n;
scanf("%d",&n);
fk(0,1,n);
return 0;
}
|
差不多了，结束今天的算法之旅，明天复现一下L3HCTF(早知道就不去虾大玩了)