递归及其应用
标签: 机试攻略 - 高分篇
学习人数: 16.1k


高清播放
赞赏支持

定义

递归算法(英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。

 

例:求N!
递归实现代码如下

#include <stdio.h>  
  
int fac(int x) {  
    if (x == 0) return 1;  
    return x * fac(x - 1);  
}  
int main() {  
    int n;  
    scanf("%d", &n);  
    printf("%d\n", fac(n));  
    return 0;  
}  

 

Hanoi塔问题
题目描述:
(n阶Hanoi塔问题)假设有三个分别命名为A、B、C的塔座,在塔座A上插有n(n<20)个直径大小各不相同、依小到大编号为1,2,…,n的圆盘。现要求将A轴上的n个圆盘移至塔座C上并仍按同样顺序叠排,圆盘移动时必须遵循下列规则: 1)每次只能移动一个圆盘; 2)圆盘可以插在A、B、C中的任一塔座上; 3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 请通过编程来打印出移动的步骤.
输入描述:
只有一组输入数据.输入数据N(;表示在开始时A塔座上的盘子数),当输入0时程序结束.
输出描述:
输出移动的步骤.如"A-->C","A-->B"等.每两的步骤之间有三个空格隔开,每输出5个步骤就换行.详细的见Sample Output.
输入样例#:
5
2
0
输出样例#:
A-->C   A-->B   C-->B   A-->C   B-->A   
B-->C   A-->C   A-->B   C-->B   C-->A   
B-->A   C-->B   A-->C   A-->B   C-->B   
A-->C   B-->A   B-->C   A-->C   B-->A   
C-->B   C-->A   B-->A   B-->C   A-->C   
A-->B   C-->B   A-->C   B-->A   B-->C   
A-->C   
A-->B   A-->C   B-->C
题目来源:
DreamJudge 1...

登录查看完整内容


课后作业

练习题目

DreamJudge 1185 全排列


登录后开始许愿

暂无评论,来抢沙发