前面教程汇总

第一讲

算法入门教程（一、模拟）

第二讲

算法入门教程（二、枚举）

递推与递归

递推

与枚举算法思想相比，递推算法能够通过已知的某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止。由此可见，递推算法要比枚举算法聪明，它不会尝试每种可能的方案。

递推算法基础

递推算法可以不断利用已有的信息推导出新的东西，在日常应用中有如下两种递推 算法。

• 顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。
• 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

递归

因为递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可。

递归算法基础

在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3个特点。

• 递归过程一般通过函数或子过程来实现。
• 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。
• 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。

在使用递归算法时，读者应该注意如下4点。

• 递归是在过程或函数中调用自身的过程。
• 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。
• 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。
• 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。

例题与解

例题1：P1255 数楼梯

非常简单的一道递推题，普通计算只能拿到50分，需要用高精度。

题目描述

楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

4
1

样例输出 #1

5
1

提示

• 对于 $60\%$ 的数据，$N\le 50$；
• 对于 $100\%$ 的数据，$1\le N\le 5000$。

C++解（1）

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,f[5010][5010],len;
void plus(int k)
{
	for(int i=1; i<=len; i++)
	    f[k][i]=f[k-1][i]+f[k-2][i];
	for(int i=1; i<=len; i++)
		if(f[k][i]>=10)
		{
			f[k][i+1]+=f[k][i]/10;
			f[k][i]%=10;
			if(f[k][len+1]>0)len++;
		}
}
int main()
{
	cin>>n;
	len = 1;
	f[1][1]=1, f[2][1]=2;
	for(int i = 3; i <= n; i++)
	    plus(i);
	for(int i = len; i >= 1; i--)
	    cout << f[n][i];
	return 0;
}
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

C++解（2）

#include
#define MAXN 5010//高精的位数
using namespace std;
struct Int
{
	int len,s[MAXN];
	Int(){len=1;memset(s,0,sizeof(s));}
	Int(int num){*this=num;
}
Int operator=(const int &num)//开始重载等号,用来赋值
{
	char a[MAXN];
    sprintf(a,"%d",num);//将整数转成Int型
	len=strlen(a);for(int i=len-1;i>=0;--i)
    s[i]=a[len-i-1]-'0';
	return *this;
}
Int operator+(const Int &a)//原理与高精加法一样
{
	Int c;
	c.len=max(len,a.len)+1;
	for(int i=0,x=0;i<c.len;++i)
	{
		c.s[i]=s[i]+a.s[i]+x;
		x=c.s[i]/10;
		c.s[i]=c.s[i]%10;
	}
	if(c.s[c.len-1]==0) --c.len;
	return c;
};
ostream& operator<<(ostream &out,const Int &x)
{
	for(int i=x.len-1;i>=0;--i) cout<<x.s[i];
	return out; 
}
//记得要把这个放在结构体外面
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

Pascal解

var a,b,c:array[0..5001] of longint;
n,i,j,k:longint;
begin
readln(n);
if n=0 then                       //特殊处理，n=0
begin
writeln(0);
halt;
end;
if n=1 then                       //特殊处理，n=1
begin
writeln(1);
halt;
end;
if n=2 then                       //特殊处理，n=2
begin
writeln(2);
halt;
end;
a[1]:=1;
b[1]:=2;
for i:=3 to n do                  //n>=3，高精度加法
begin
k:=0;
for j:=1 to 5000 do
begin
c[j]:=a[j]+b[j]+c[j];
c[j+1]:=c[j+1]+c[j] div 10;       //处理进位
c[j]:=c[j] mod 10;                
end;
a:=b;                             //准备下一次高精
b:=c;
fillchar(c,sizeof(c),0);
end;
k:=5000;
while b[k]=0 do dec(k);
for i:=k downto 1 do write(b[i]); //逆序输出
end.
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

Python解

n = int(input())
a = 1
b = 1
n -= 1
if n > 0:
    while n > 0:
        c = a + b
        a = b
        b = c
        n -= 1
    print(b)
elif n == 0:
#判断边界
	print(a)
else:
    a-=1
    #判断边界
	print(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Java解

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Scanner in = new Scanner(System.in);
		BigInteger b1 = new BigInteger("1");
		BigInteger b2 = new BigInteger("1");
		BigInteger b3 = new BigInteger("2");
		int N = in.nextInt();
		if(N<1) System.out.println(0);
		else if(N<3)System.out.println(1);
		else {
			for(int i=1;i<N;i++) {
				b3 = b1.add(b2);
				b1 = b2;
				b2 = b3;
			}
			System.out.println(b3);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

例题2：P1044 [NOIP2003 普及组] 栈

注：转换为卡特兰数即可。

题目背景

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

题目描述

宁宁考虑的是这样一个问题：一个操作数序列，$1,2,\dots ,n$（图示为 1 到 3 的情况），栈 A 的深度大于 $n$。

现在可以进行两种操作，

1. 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 1 2 3 生成序列 2 3 1 的过程。

（原始状态如上图所示）

你的程序将对给定的 $n$，计算并输出由操作数序列 $1,2,\dots ,n$ 经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 $n$（$1\le n\le 18$）。

输出格式

输出文件只有一行，即可能输出序列的总数目。

样例 #1

样例输入 #1

3
1

样例输出 #1

5
1

提示

【题目来源】

NOIP 2003 普及组第三题

C++解

#include 
using namespace std;

long long f[19] = {0}, sum = 0;

int main()
{
	int n;
	cin >> n;
	f[0] = f[1] = 1;
	for (int k = 2; k <= n; k++)
	{
		for (int i = 0; i <= k - 1; i++)
		{
			f[k] += f[i] * f[k - i - 1];
		}
	}
	cout << f[n];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

C解（最简）

#include 
int main()
{
    long long n, f = 1;
    scanf("%lld",&n);
    for (int i = 1; i <= n; i++) f = f * (4 * i - 2) / (i + 1);
    printf("%lld",f); 
}
1
2
3
4
5
6
7
8

Pascal解

var
  n,i:longint;
  s:int64;
begin
  readln(n);
  s:=1;
  for i:=1 to n do
    s:=s*(n+i) div i;
  s:=s div (n+1);
  writeln(s);
end.
1
2
3
4
5
6
7
8
9
10
11

本文完。关于枚举算法的题还有很多，可以在洛谷上刷。本文由于代码有一些已经加了注释，所以就不在文章里说明了，如果不懂，欢迎在评论区留言。