第1个回答 2011-08-22
1、 斐波那契数列
【问题描述】
斐波那契数列0,1,1,2,3,5,8,13,21,34,55…从第三项起，每一项都是紧挨着的前两项的和，写出计算斐波那契数列任意一个数据项的递归程序。
【输入格式】
所求的项数
【输出格式】
数据项的值
【输入样例】
10
【输出样例】
34
2、 倒序数
【问题描述】
用递归算法写程序，输入一个非负整数，输出这个数的倒序数。
【输入格式】
一个非负整数
【输出格式】
倒序结果
【输入样例】
123
【输出样例】
321
3、 十进制数转成八进制数
【问题描述】
用递归算法，把任一给定的十进制正整数转换成八进制数。
【输入格式】
一个正整数，表示需要转换的十进制数。
【输出格式】
一个正整数，表示转换之年的八进制数。
【输入样例】
15
【输出样例】
17
4、 求N!的值
【问题描述】
用递归算法，求N！的精确值（N以一般整数输入）。
【输入样例】
10
【输出样例】
10！= 3628800
5、 求最大公约数
【问题描述】
用递归算法求两个正整数M和N的最大公约数。
【输入格式】
两个数，即M和N的值。
【输出格式】
最大公约数。
【输入样例】
8 6
【输出样例】
Gcd=2
6、 背包问题
【问题描述】
简单的背包问题。设有一个背包，可以放入的重量为S。现有N件物品，重量分别为W1，W2，…，Wn（1≤i≤n）,均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为S。找到一组即可。
【输入格式】
第一行是物品总件数和背包的载重量，第二行为各物品的重量。
【输出格式】
各所选物品的序号和重量。
【输入样例】
5 10
1 2 3 4 5
【输出样例】
Number : 1 weight : 1
Number : 4 weight : 4
Number : 5 wright : 5
7、 2的幂次方
【问题描述】
任何一个正整数都可以用2的幂次方表示。例如：
137=27+23+20
同时约定用括号来表示方次，即ab要表示为a(b)。
由此可知，137可表示为
2(7)+2(3)+2(0)
进一步：
7=22+2+20 (21用2表示)
3=2+20
所以，最后137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如：
1315=210+28+25+2+1
所以，最后137可表示为：
2(2(2+2(0))+2)+2(2+2(0))+2(0)
【输入格式】
正整数N（N≤20000）。
【输出格式】
用0，2表示的符合约定的N（在表示中不能有空格）。
【输入样例】
137
【输出样例】
2(2(2)+2+2(0))+2(2+2(0))+2(0)
8、 加法表(NOIP1998)
【问题描述】
著名科学家卢斯为了检查学生对进位制的理解，给出了如下的一张加法表，表中的字母代表数字。例如：
+ L K V E
L L K V E
K K V E KL
V V E KL KK
E E KL KK KV
其含义为:
： L+L=L, L+K=K, L+V=V, L+E=E
K+L=K, K+K=V, K+V=E, K+E=KL
…
E+E=KV
根据这些规则可推导出：L=0，K=1，V=2，E=3
同时可以确定该表表示的是4进制加法。
【输入格式】
第一行表示行数N（N≤9）。
以下N行，每行包括N个字符串，每个字符串间用空格隔开。（字符串仅有一个“+”号，其他都由大写字母组成）。
【输出格式】
第一行是各个字母表示的数。
第二行表示加法运算是几进制的。
若不可能组成可法表，则应输出“error!”。
【输入样例】
3
+M L
M ML M
L M L
【输出样例】
M=1 L=0
2
9、 数的计数
【问题描述】
我们要求找出具有下列性质的数的个数（包含输入的自然数N）：
先输入一个自然数N（N≤1000），然后对自然数按照如下方法进行处理：
② 不作任何处理；
② 在它的左边加上一个自然数，但该自然数不能超过原数（输入的N）的一半；
③ 加上数后，继续按此规则进行处理，直到不能再加自然数为止。
【输入格式】
。
【输出格式】
各所选物品的序号和重量。
【输入样例】
6
【输出样例】
6
满足条件的数为6，16，26，126，36，136（此部分不必输出）
10、集合划分问题
【问题描述】
N个元素的集合 {1，2，3，4，…，N} 可以划分为若干个非空子集。例如：当N=4时，集合 {1，2，3，4} 可以划分为15个不同的非空子集，如下：
{{1}，{2}，{3}，{4}} {{1，2}，{3}，{4}} {{1，3}，{2}，{4}}
{{1，4}，{2}，{3}} {{2，3}，{1}，{4}} {{2，4}，{1}，{3}}
{{3，4}，{1}，{2}} {{1，2}，{3，4}} {{1，3}，{2，4}}
{{1，4}，{2，3}} {{1，2，3}，{4}} {{1，2，4}，{3}}
{{1，3，4}，{2}} {{2，3，4}，{1}} {{1，2，3，4}}
其中：
集合 {{1，2，3，4}} 由1个子集组成；
集合 {{1，2}，{3，4}} {{1，3}，{2，4}} {{1，4}，{2，3}}
{{1，2，3}，{4}} {{1，2，4}，{3}} {{1，3，4}，{2}}
{{2，3，4}，{1}} 由2个子集组成；s(4,2) = 6
集合 {{1，2}，{3}，{4}} {{1，3}，{2}，{4}} {{1，4}，{2}，{3}}
{{2，3}，{1}，{4}} {{2，4}，{1}，{3}} {{3，4}，{1}，{2}}
由3个子集组成； s(4,3)=7
集合 {{1}，{2}，{3}，{4}}由4个子集组成。
给定正整数N和M，计算出N个元素的集合 {1，2，3，4，…，N} 可以划分为多少个不同的由M个非空子集组成的集合。
【输入格式】
一行数据，是元素个数N和非空了集数M。
【输出格式】
计算出的不同的由M个非空子集组成的集合数。
【输入样例】
4 3
【输出样例】
6
【算法分析】
所求的是第二类Stirling数，可推导出如下递归公式：
以s(5,3)为例：
S(5,3)可以由① 往s(4,2)中加一个元素成为s(5,3),共7种；
② 往s(4,3)中加一个元素成为s(5,3),共3*6=18种
则：s(5,3) = 3*s(4,3) + s(4,2) = 25 导出：
s(n,m) = m*s(n-1,m)+s(n-1,m-1)
s(n,n+1) = 0
s(n,0) = 0
s(0,0) = 1
再例：
考虑3个元素的集合，可划分为
① 1个子集的集合：{{1，2，3}}
② 2个子集的集合：{{1，2}，{3}}，{{1，3}，{2}}，{{2，3}，{1}}
③ 3个子集的集合：{{1}，{2}，{3}}
∴F(3,1)=1; F(3,2)=3; F(3,3)=1;
如果要求F(4,2)该怎么办呢？
A.往①里添一个元素{4}，得到{{1，2，3}，{4}}
B.往②里的任意一个子集添一个4，得到
{{1，2，4}，{3}}，{{1，2}，{3，4}}，
{{1，3，4}，{2}}，{{1，3}，{2，4}}，
{{2，3，4}，{1}}，{{2，3}，{1，4}}
∴F(4,2) = F(3,1) + 2*F(3,2) ＝ 1+2*3 ＝ 7
第2个回答 2020-07-05
1.
有5个人坐在一起，问第5个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第3个人，又说比第2个人大2岁。问第2个人，说比第1个人大2岁。最后问第1个人，他说是10岁。请问第5个人多大。显然，这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且每一个人的年龄都比其前1个人的年龄大2。
2.用递归方法求n！
3.用递归方法求斐波那契数列
4.有1*n的一个长方形，用一个1＊1、1＊2、1＊3的骨牌铺满方格。例如当n=3时为1＊3的方格。此时用1＊1，1＊2，1＊3的骨牌铺满方格，共有四种铺法。图4.4.3列出了四种铺法。
5.设s是一个具有n个元素的集合s={a1,a2,…an},现将s集合划分成k个满足下列条件的子集合s1,s2，s3。。。。；
1、si<>空；
2、si∩sj=空；
3、s1∪s2∪s3….
∪sn=s
(1<=i,j<=k,i<>j)
则称s1,s2…sn是集合s的一个划分，它相当于把集合s中的n个元素放入k个无标号的盒子中，使得没有一个盒子为空，试确定n个元素的集合放入k个无标号盒的划分数s(n,k)
6.设有一个背包，可以放入的重量为s。现有n件物品，重量分别为t1
,
t2
,
t3
…
ti
…
tn
，ti
(1≤
i≤n)，均为正整数。从n件物品中挑选若干件，使得放入背包的重量之和正好为s
【输入样例】
【输出样例】
the
number
of
object:5
number:1
weight:1
total
weight=10
number:3
weight:
2
1
6
2
7
5
number:4
weight:7
7.输出n个元素的无重复的全排列。N个元素有n！种不同排列
8.任何一个正整数都可以用2的幂次方表示.例如：137=2^7+2^3+2^0。同时约定次方用括号来表示，即a^b可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)，进一步：7=2^2+2+2^0
(2^1用2表示)；3=2+2^0；所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)。又如：1315=2^10+2^8+2^5+2+1；所以1315最后可表示：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
输入：正整数(n≤20000)
输出：符合约定的n的0，2表示(在表示中不能有空格)
9.。一个正整数的数字的乘积N的定义是：这个整数中非零数字的乘积。例如，整数999的数字乘积为9*9*9，即729。729的数字乘积为7*2*9，即126。126的数字乘积为1*2*6，即12。12的数字乘积为1*2，即2。一个正整数的数字乘积根N是这样得到的：反复取该整数的数字乘积，直到得到一位数字为止。例如，在上面的例子中数字的乘积根是2。
编写一个程序，输入一个正整数（长度不超过200位数字），输出计算其数字乘积根的每一步结果。
10.输入N个字符，然后以倒序输出（用递归实现）
第3个回答 2011-08-22
用递归的方法完成下列问题
1.求数组中的最大数
2.1+2+3+...+n
3.求n个整数的积
4.求n个整数的平均值
5.求n个自然数的最大公约数与最小公倍数
6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.
8.计算xn。 x,n 由键盘输入。将xn写成递归函数计算N允许为正、负数和零 。
这些够简单吧
第4个回答 2011-08-23
整个递归的过程是这样的
ack（m,n）=
我就举例ack(3,4)，此时m=3，n=4
1. 此时 m不等于0 ，n不等于0
所以ack(3,4)：=ack(3-1,ack(3,4-1))
^^^^^
ack(3,4-1):=ack(3-1,ack(3,3-1))
^^^^^^^^
ack(3,3-1):=ack(3-1,ack(3,2-1))
^^^^^^
ack(3,2-1):=ack(3-1,ack(3,1-1))
^^^^^
ack(3,1-1):=ack(3-1,1)
就这么算下去，直到M=0，在一步一步回头
在举个简单点的例子吧
求 ack(1,0)
此时 n=0 所以 ack(1,0)：=ack(0,1)
又 ack(0,1)：=2
所以 ack(1,0)：=2；
你慢慢理解吧。