当前位置:首页 >> 学科竞赛 >>

Recursive Functions计算机竞赛


Recursive Functions A definition that defines an object in terms of itself is said to be recursive. This theoretical mathematical topic serves as an introduction to recursive programming (which is supported by Pascal, but not by most BASICs). It also provides a framework for analyzing algorithms (determining the running time and/or space required) which contain loops or recursive sections. Many expressions may be defined recursively in a very simple and elegant manner. The art of recursive thinking is an important skill. Applications of recursion appear in many areas of mathematics (factorials, compound interest, difference equations, etc.) In this round recursive relationships will be shown not in the context of a programming language but usually in functional notation from mathematics or in an algorithmic description. References Roberts, Eric S. Thinking Recursively, Wiley (1986). Rohl, J.S. Recursion via Pascal, Cambridge University Press (1984). Wirth, Niklaus. Algorithms + Data Structures = Programs, Prentice-Hall (1976), Chapter 3.

Sample Problems Consider the following recursive algorithm for painting a square: 1. Given a square. 2. If the length of a side is less than 2 feet, then stop. 3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square). 4. Paint one of these 4 small squares. 5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares. If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted? In the first pass, we get four squares of side 8. One is painted; three are unpainted. Next, we have 3*4 squares of side 4: three are painted (area=3*42), nine are not. Next, we have 9*4 squares of side 2: nine are painted (area = 9*22), 27 are not. Finally, we have 27*4 squares of side 1: twenty-seven are painted. Therefore, the total painted is 1*82 + 3*42 + 9*22 + 27*12 = 175.

Evaluate f(12, 6), given: f(x,y) = +2 ? f(x-y,y-1) x+y when x>y otherwise

Evaluate the function as follows: f(12, 6) = f(6, 5)+2 = (f (1, 4)+2)+2 = f(1, 4)+4 = (1+4)+4 =9 Working backwards, we get f(0)= 1 f(1) = 2 f(2) = f(f(0))+1 = f(1)+1 = 2+1 = 3 f(3) = f(f(1))+1 = f(2)+1 = 3+1 = 4 f(4) = f(f(2))+1 = f(3)+1 = 4+1 = 5 f(5) = f(f(3))+1 = f(4)+1 = 5+1 = 6 f(6) = f(f(4))+1 = f(5)+1 = 6+1 = 7 Ackerman’s Function is infamous for its potential growth. In fact, we don’t have room here to give a full explanation of the problem. For details, refer to the 1981-82 ACSL All-Star Contest. By evaluating A(1,0), A(1,1), A(1,2) and A(1,3), we see that in general, A(1, x)=2+x. If we evaluate A(2,0), A(2,1), …, we see that in general, A(2,x)=2x+3. To solve our problem, we substitute x=3 and we get an answer of 9.

Find f(6), given:

f(x) =

?

f (f (x-2))+1 2 1

when x>1 when x=1 when x=0

One of the best known recursive functions, Ackerman’s Function, is defined below. Evaluate A(2, 3). A(M,N) =

?

N+1 if M=0 A(M-1, 1) if M?0, N=0 A(M-1, A(M, N-1)) if M?0, N?0

Challenge for the bored: Evaluate A(n, m) in terms of n and m.



相关文章:
计算机基础知识,信息学竞赛
计算机基础知识,信息学竞赛_学科竞赛_初中教育_教育专区。计算机基础知识 第一节 计算机的基本常识 1.1 计算机的产生与发展 计算机的产生是 20 世纪最重要的科学...
计算机类大学生竞赛
计算机类大学生竞赛_学科竞赛_高中教育_教育专区。计算机类大学生竞赛基础目录及时间 大学生程序设计大赛(ACM/ICPC) 关键词:ACM 简介 ACM 参赛方式 ACM 流程 ACM ...
科普趣味知识竞赛——计算机部分
知识竞赛(计算机部分)简单题 1、多媒体计算机是指( C ) A、 具有多种外部设备的计算机 B、 能与多种媒体设备连接的计算机 C、 能处理多种媒体的计算机 D、 ...
计算机技能比赛方案
计算机技能比赛方案_其它_计划/解决方案_实用文档。计算机专业技能大赛方案 计算机专业技能大赛方案一、 活动主题 以学习求进步、以竞技求发展 二、 活动时间 2011 ...
计算机知识技能竞赛资料_图文
计算机知识技能竞赛资料_学科竞赛_小学教育_教育专区。2015 年海淀区中小学生计算机知识技能竞赛复习资料一、客观题(第一套) 在同一台计算机中,内存比外存 ()。 ...
《计算机应用基础》技能竞赛
计算机应用基础》技能竞赛_中职中专_职业教育_教育专区。《计算机应用基础》技能竞赛注意:竞赛结束请安静有序离开,勿关机!竞赛时间为 90 分钟 在 D 盘新建一个...
计算机竞赛试题以及答案
计算机竞赛试题及答案姓名: 班级: 基础知识第一章 1.下列关于个人计算机的叙述中,错误的是___。 A.个人计算机的英文缩写是 PC B.个人计算机又称为微机 C.世界...
2015海曙区中小学生计算机奥赛解题报告
2015海曙区中小学生计算机奥赛解题报告_学科竞赛_小学教育_教育专区。计算机程序设计;信息学竞赛;宁波 2015 海曙区中小学生计算机奥赛解题报告 1. 抗战阅兵 (parade....
计算机技能大赛试题
计算机技能大赛试题_IT认证_资格考试/认证_教育专区。计算机技能大赛试题(高级)试题说明:本试题满分共 100 分,包括理论部分(30 分)和操作部分(70 分) ,考试时 ...
计算机类竞赛题_图文
计算机竞赛题_工学_高等教育_教育专区。数学与计算机学院 上机报告( 2015 / 2016 学年 第 2 学期 )? ? ? 课程名称 课程代码 计算机竞赛专题训练 上机...
更多相关标签: