东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn ACM程序设计 东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn.

Presentation on theme: "东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn ACM程序设计 东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn."— Presentation transcript:

1 东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn
ACM程序设计 东北林业大学 陈宇

2 今天你AC 了吗？

3 第二讲 递归

4 我校的ACM在线评测系统 acm.nefu.edu.cn 课件下载地址： acm.nefu.edu.cn/kj/suanfa02.ppt

5 递归算法的分析 关键：根据递归过程建立递推关系式，然后求解这个递推关系式。
1. 猜测技术:对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。

6 å 扩展递归技术 设n=2k î í ì > + = 1 5 ) 2 ( 7 n T 5 ) ( 4 8 n T + ×´ = L )
- L ) ( 10 3 2 1 5 7 n O n2 T k i = - + ø ö ç è æ å

7 通用分治递推式 ï î í ì < = > n O T ) ( log
大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。 î í ì > + = 1 ) ( n cn b aT c T k ï î í ì < = > k b a n O T ) ( log

8 递归的定义 递归（Recursion）就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。
递归有两个基本要素： ⑴ 边界条件：确定递归到何时终止； ⑵ 递归模式：大问题是如何分解为小问题的。

9 计算阶乘N！ f(n)=n!可以定义为：

10 代码： #include<stdio.h> int f(int n){
return n == 0 ? 1 : f(n-1)*n; } int main(){ printf("%d\n", f(3)); return 0;

11 递归要调用栈来进行！ 皇帝（拥有main函数的栈）：大臣，你给我算一 下f(3). 大臣（拥有f(3)的栈):知府，你给我算一下f(2).

12 县令：（心算）回知府大人，f(1)=1. 知府： （心算）回大人，f(2)=2. 大臣： （心算） 3*f(2)=6，回皇上， f(3)=6

13 运行 计算f(3)=6; 计算f(100000000),没有输出，溢出也应该有数啊！ 是段错误！
段：是指二进制文件内的区域，某种特定类型的信息被保存在里面。

14 追忆2008年亚洲哈尔滨赛区 杨成虎同学的深搜算法就是递归写的，就是不过，因为该算法在递归调用5000次就段错误了，后来改成广搜算法（非递归）的就AC 了，时间多了1个小时，离银牌只差2名，血的教训！ 我们要牢记！

15 蟠桃记 Problem Description

16 Input 输入数据有多组，每组占一行，包含一个正整数n（1<n<30），表示只剩下一个桃子的时候是在第n天发生的。 Output 对于每组输入数据，输出第一天开始吃的时候桃子的总数，每个测试实例占一行。

17 Sample Input 2 4  Sample Output 22

18 分析： 设A0代表第1天的桃子总数，Ai代表吃完后剩下的桃子数，则： A0=2*（A1+1） A1=2*(A2+1) …………….
An-1=2*(An+1) An=1

19 代码：倒推 #include <cstdlib> #include <iostream>
using namespace std; long long f(int n) { if (n==1) return 1; else return 2*(f(n-1)+1); }

20 Fibonacci数列 description
计算Fibonacci数列的值！该数列为 input 有多组数据，输入N(3<=N<=50),N代表该数列的第N项的值。

21 output 输出该数列的第N 项的值。 sample_input 4 5 sample_output 3

22 代码： long long f(int n) { if (n==1||n==2) return 1; else
return f(n-1)+f(n-2); }

23 实际运行： 42 43 44 45 50 35 36 37 38 39 40 41 用了4分钟，计算f(50)

24 献给不懂得优化的同学！ long long data[100]; data[1]=1; data[2]=1;
for(int i=3;i<=50;i++) data[i]=data[i-1]+data[i-2]; while(cin>>n) cout<<data[n]<<endl;

25 Fibonacci Again hdu1021 Problem Description
There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2). 林大OJ 70题

26 Input Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000). Output Print the word "yes" if 3 divide evenly into F(n). Print the word "no" if not.

27 Sample Output no yes Sample Input 1 2 3 4 5

28 思路：先找循环节 先计算前30项，看看 循环节=8

29 用递归计算 int f(int n) { if (n==0) return 1; if (n==1) return 2;
return (f(n-1)+f(n-2))%3; }

30 main函数 while(cin>>n) { t=n%8; if (f(t)==0)
cout<<"yes"<<endl; else cout<<"no"<<endl; }

31 红与黑 hdu 1312 有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

32 输入数据 包括多个数据集合。每个数据集合的第一行是两个整数W 和H，分别表示x 方向
和y 方向瓷砖的数量。W 和H 都不超过20。在接下来的H 行中，每行包括W 个字符。 每个字符表示一块瓷砖的颜色，规则如下：

33 1）‘.’：黑色的瓷砖； 2）‘#’：白色的瓷砖； 当在一行中读入的是两个零时，表示输入结束。

34 输出要求 对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

35 输入样例 6 9 ....#. .....# ...... .#..#. 0 0 结果：45

36 解题思路 这个题目可以描述成给定一点，计算它所在的连通区域的面积。需要考虑的问题包括矩阵的大小，以及从某一点出发向上下左右行走时，可能遇到的三种情况：出了矩阵边界、遇到’.’、遇到’#’。 设f(x, y)为从点(x,y)出发能够走过的黑瓷砖总数，则 f(x, y) = 1 + f(x - 1, y) + f(x + 1, y) + f(x, y - 1) + f(x, y + 1) 这里需要注意，凡是走过的瓷砖不能够被重复走过。可以通过每走过一块瓷砖就将它作标记的方法保证不重复计算任何瓷砖。

37 Main()函数 int w,h; //定义公有变量 长和宽 char z[21][21];

38 int main(int argc, char *argv[])
{ while(cin>>w>>h) if (w==0&&h==0) break; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin>>z[i][j]; if cout<<f(i,j)<<endl; } //system("PAUSE"); return EXIT_SUCCESS;

39 再看递归部分： int f(int i,int j) {
if (i<1||i>h||j<1||j>w) //处理边界 return 0; if (z[i][j]!='#') z[i][j]=‘#’; //这句话是啥意思？ return 1+f(i,j-1)+f(i,j+1)+f(i-1,j)+f(i+1,j); } else

40 Welcome to HDOJ Thank You ~